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®aA, A®BB, B®aBb
C
S®a|aA, A®BB|B, B®aBb|ab
D
S®a|aA, A®BB, B®aBb|ab
Question 3
Which one of the following statements is incorrect ?
A
The number of regions corresponds to the cyclomatic complexity.
B
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
C
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.
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