__UGC NET Previous Year Papers__

__Computer Science – Paper II __

__June-2008 __

**1. **Which of the following does **not** define a tree?

**(A)** A tree is a connected acyclic graph.

**(B)** A tree is a connected graph with n-1 edges where ’n’ is the number of vertices in the graph.

**(C)** A tree is an acyclic graph with n-1 edges where ’n’ is the number of vertices in the graph.

**(D)** A tree is a graph with no cycles.

**Ans: (D)**

**2. ** The complexity of Kruskal’s minimum spanning tree algorithm on a graph with ‘n’ nodes and ‘e’ edges is :

**(A)** O(n)

**(B)** O(n log n)

**(C)** O(e log n)

**(D)** O(e)

**Ans: (C)**

**3. ** If a code is t-error correcting, the minimum Hamming distance is equal to:

**(A)** 2t+1

**(B)** 2t

**(C)** 2t-1

**(D)** t-1

**Ans: (A)**

**4. ** The set of positive integers under the operation of ordinary multiplication is:

**(A)** not a monoid

**(B)** not a group

**(C)** a group

**(D)** an Abelian group

**Ans: (D)**

**5. ** In a set of 8 positive integers, there always exists a pair of numbers having the same remainder when divided by:

**(A)** 7

**(B)** 11

**(C)** 13

**(D)** 15

**Ans: (A)**

**6. ** An example of a tautology is:

**(A)** x v y

**(B)** x v (~y)

**(C)** x v (~x)

**(D)** (x=>y)˄(x<=y)

**Ans: (C)**

**7. ** Among the logic families RTL, TTL, ECL and CMOS, the fastest family is:

**(A)** ECL

**(B)** CMOS

**(C)** TTL

**(D)** RTL

**Ans: (A)**

**8. ** The octal equivalent of the hexadecimal number FF is:

**(A)** 100

**(B)** 150

**(C)** 377

**(D)** 737

**Ans: (C)**

**9. ** The characteristic equation of a T flip flop is given by:

**(A)** Q_{N+1}=TQ_{N}

**(B)** Q_{N+1}=T+Q_{N}

**(C)** Q_{N+1}=T⊕Q_{N}

**(D)** Q_{N+1}=T+Q_{N}

**Ans: (C)**

**10. ** The idempotent law in Boolean algebra says that:

**(A)** ~(~x)=x

**(B)** x+x=x

**(C)** x+xy=x

**(D)** x(x+y)=x

**Ans: (B)**