Table of Content

UGC NET Computer Science : June 2012 – Paper 3 (Solved Papers)

 Question 1
The upper bound of computing time of m coloring decision problem is
 A O(nm) B O(nmn) C O(nm) D O(nmmn)
 Question 2
The equivalent grammar corresponding to the grammar G : S ® aA, A ® BB, B ® aBb| Î is
 A S®aA, A®BB, B®aBb B S®a|aA, A®BB|B, B®aBb|ab C S®a|aA, A®BB|B, B®aBb D S®a|aA, A®BB, B®aBb|ab
 Question 3
Which one of the following statements is incorrect ?
 A Cyclometric complexity for a flow graph G is V(G) = E–N+2, where E is the number of edges & N is the number of nodes in the flow graph B Cyclometric complexity for a flow graph G is V(G) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph. C The number of regions corresponds to the cyclomatic complexity. D Cyclometric complexity for a flow graph G is V(G) = P + 1, where P is the number of predicate nodes contained in the flow graph G.
 Question 4
Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true ?
 A Weight (u, v) > 12 B Weight (u, v) <= 12 C Weight (u, v) >= 12 D Weight (u, v) = 12
 Question 5
Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains
 A n states B 2n states C n + 1 states D n + 2 states