31. The upper
bound of computing time of m coloring decision problem is

(A) O(nm)

(B) O(n

^{m})
(C) O(nm

^{n})
(D) O(n

^{m}m^{n})
Answer: C

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

Answer: D

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.

Answer: B

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

Answer: C

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) 2

^{n}states
Answer: B

36. Number of
binary trees formed with 5 nodes are

(A) 32

(B) 36

(C) 120

(D) 42

Answer: D

37. Are we
building the right product?

This statement refers to

(A) Verification

(B) Validation

(C) Testing

(D) Software quality assurance

Answer: B

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

Answer: A

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

Answer: C

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

Answer: B

## 0 Comments