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)

Answer: (C)

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: (C)

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

Answer: (B)

36. Number of binary trees formed with 5 nodes is

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