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(nmmn)
B
O(nm)
C
O(nmn)
D
O(nm)
Question 2
The equivalent grammar corresponding to the grammar G : S ® aA, A ® BB, B ® aBb| Î is
A
S®a|aA, A®BB|B, B®aBb
B
S®a|aA, A®BB|B, B®aBb|ab
C
S®aA, A®BB, 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) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph.
B
The number of regions corresponds to the cyclomatic complexity.
C
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
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

Pages: Page 1, Page 2, Page 3, Page 4, Page 5, Page 6, Page 7, Page 8, Page 9, Page 10, Page 11, Page 12, Page 13, Page 14, Page 15