UGC NET CS 2008-june-Paper-2

 Question 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.
Data-Structures       Trees
Question 1 Explanation:
→ An undirected graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. A graph that is not connected is disconnected. An undirected graph G is said to be disconnected if there exist two nodes in G such that no path in G has those nodes as endpoints.
→ An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite.
→ A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).
→ All first 3 options are correctly defining tree without any loss of information, whereas "A tree is a graph with no cycles." is not always correct as it can be bipartite.
Hence D does not define a tree.
 Question 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)
Algorithms       Minimum-Spanning-Tree
Question 2 Explanation:
MST-KRUSKAL(G,w)
1. A=∅
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v)∈G.E, taken in nondecreasing order by weight
6. if FIND-SET(u)≠FIND-SET(v)
7. A=A∪{(u,v)}
8. UNION(u,v)
9. return A
Analysis:
The running time of Kruskal’s algorithm for a graph G=(V,E) depends on how we implement the disjoint-set data structure.
→ Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(ElgE). (We will account for the cost of the |V| MAKE-SET operations in the for loop of lines 2–3 in a moment.)
→ The for loop of lines 5–8 performs O(E) FIND-SET and UNION operations on the disjoint-set forest.
→ Along with the |V| MAKE-SET operations, these take a total of O((V+E)α(V)) time, where α is the very slowly growing function.
→ Because we assume that G is connected, we have |E|>=|V|-1, and so the disjoint-set operations take O(Eα(V)) time.
→ Moreover, since α |V|=O(lg V)=O(lg E), the total running time of Kruskal’s algorithm is O(ElgE)
→ Observing that |E|<|V|2 , we have lg |E|=O(lg V), and so we can restate the running time of Kruskal’s algorithm as O(E lg V)
 Question 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
Digital-Logic-Design       Number-Systems
Question 3 Explanation:

 Question 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
Engineering-Mathematics       Set-Theory
Question 4 Explanation:
The set of positive integers under the operation of ordinary multiplication is a monoid but not a group.
 Question 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
Engineering-Mathematics       Combinatorics
Question 5 Explanation:
Given data,
-- Set of positive integers=8
-- A pair of numbers having the same remainder when divided by=?
Step-1: This problem, we can use pigeonhole principle.
Pigeonhole Principle: If there are ‘X’ positive integers to be placed in ‘Y’ possible remainder where Y < X, then there is at least one possible remainder which receives more than one positive integer.
Option-A: Total number of possible remainders, divided by 7 is 0,1,2,3,4,5,6.
These numbers are less than 8 only.
Option-B,C and D: Total number of possible remainders,
divided by 11, 13, 15 is greater than 8
 Question 6
An example of a tautology is :
 A x v y B x v (~y) C x v (~x) D (x=>y) v (x<=y)
Engineering-Mathematics       Propositional-Logic
Question 6 Explanation:

 Question 7
Among the logic families RTL, TTL, ECL and CMOS, the fastest family is :
 A ECL B CMOS C TTL D RTL
Digital-Logic-Design       Logic-Families
Question 7 Explanation:
Emitter Coupled Logic (ECL):
The storage time is eliminated as the transistors are used in difference amplifier mode and are never driven into saturation.
1. Fastest among all logic families
2. Lowest propagation delay.
Complementary metal oxide semiconductor(CMOS):
The power dissipation is usually 10nW per gate depending upon the power supply voltage, output load etc.
1. Lowest power dissipation
2. Excellent noise immunity
3. High packing density
4. Wide range of supply voltage
5. Highest fan out among all logic families
Transistor Transistor Logic:
→ TTL devices consume substantially more power than equivalent CMOS devices at rest, but power consumption does not increase with clock speed as rapidly as for CMOS devices.
 Question 8
The octal equivalent of the hexadecimal number FF is :
 A 100 B 150 C 377 D 737
Digital-Logic-Design       Number-Systems
Question 8 Explanation:
Step-1: Convert FF into binary number
(FF)16 = (1111 1111)2
Step-2: Divide binary number into 3 segments from LSB(Least significant bit).

 Question 9
The characteristic equation of a T flip flop is given by :
 A QN+1 = TQN B QN+1 = T+QN C QN+1 = T ⊕ QN D QN+1=T'QN
Digital-Logic-Design       Sequential-Circuits
Question 9 Explanation:
T-Flip flop Truth Table:

 Question 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
Digital-Logic-Design       Boolean-Algebra
Question 10 Explanation:
Idempotent law:
The idempotence in the context of elements of algebras that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from idem + potence (same + power).
(i). X + X=X
(ii). X ∧ X=X
According to boolean algebra

 Question 11
What is the effect of the following C code ?
for(int i=1; i≤5; i=i+½)
printf(“%d,”,i);
 A It prints 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, and stops B It prints 1, 2, 3, 4, 5, and stops C It prints 1, 2, 3, 4, 5, and repeats forever D It prints 1, 1, 1, 1, 1, and repeats forever
Programming       Control-Statement
Question 11 Explanation:
According to integer datatype, fraction values we are not considering. So,it will always become
1. Iteration-1: for(int i=1; i≤5; i=i+½) /*condition TRUE, then we are printing value but incrementing by 0. It means, i=1+0 */
So, ‘i’ value always become 1 only. The given condition always TRUE and will print infinite times.
 Question 12
Consider the following declaration in C :
char a[ ];
char *p;
Which of the following statement is not a valid statement ?
 A p=a; B p=a+2; C a=p; D p=&a[2];
Programming       Pointers
Question 12 Explanation:
According to pointer value assigning declarations,
p=a; /*It is correct declaration */
p=p+2; /*It is correct declaration */
p=&a[2]; /*It is correct declaration */
a=p; /* It is incorrect declaration */
There are 12 questions to complete.

Register Now