# UGC NET Computer Science Paper III June 2012 - Part 4

31.       The upper bound of computing time of m coloring decision problem is
(A) O(nm)
(B) O(nm)
(C) O(nmn)
(D) O(nmmn)
32.       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®aBb|ab
(C) S®a|aA, A®BB|B, B®aBb
(D) S®a|aA, A®BB|B, B®aBb|ab
33.       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) = N–E+2, where E is the number of edges and N is the number of nodes in the flow graph.
(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.
34.       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
35.       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) n + 1 states
(C) n + 2 states
(D) 2n states
36.       Number of binary trees formed with 5 nodes are
(A) 32
(B) 36
(C) 120
(D) 42
37.       Are we building the right product?
This statement refers to
(A) Verification
(B) Validation
(C) Testing
(D) Software quality assurance
38.       The following postfix expression is evaluated using a stack
823^/23* + 51* –
The top two elements of the stack after first * is evaluated
(A) 6, 1
(B) 5, 7
(C) 3, 2
(D) 1, 5
39.       The following CFG
S®aB|bA, A®a|as|bAA, B®b|bs|aBB
generates strings of terminals that have
(A) odd number of a’s and odd number of b’s
(B) even number of a’s and even number of b’s
(C) equal number of a’s and b’s
(D) not equal number of a’s and b’s
40.    Consider the following pseudo-code :
If (A > B) and (C > D) then
A = A + 1
B = B + 1
Endif
The cyclomatic complexity of the pseudo-code is
(A) 2
(B) 3
(C) 4
(D) 5