## MCQs Data Structure|UGC-NET|GATE|Data Structures

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

View/Hide Ans | |

Explanation | |

32. | 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. |

View/Hide Ans | |

Explanation | |

33. | 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 |

View/Hide Ans | |

Explanation | |

34. | Number of binary trees formed with 5 nodes are |

A. | 32 |

B. | 36 |

C. | 120 |

D. | 42 |

View/Hide Ans | |

Explanation | |

35. | 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 |

View/Hide Ans | |

Explanation | |

36. | Cyclometric complexity of a flow graph G with n vertices and e edges is |

A. | V(G) = e+n–2 |

B. | V(G) = e–n+2 |

C. | V(G) = e+n+2 |

D. | V(G) = e–n–2 |

View/Hide Ans | |

Explanation | |

37. | For a B-tree of height h and degree t, the total CPU time used to insert a node is |

A. | O(h log t) |

B. | O(t log h) |

C. | O(t2h) |

D. | O(th) |

View/Hide Ans | |

Explanation | |

38. | The time complexity to build a heap with a list of n numbers is |

A. | O(log n) |

B. | O(n) |

C. | O(n logn) |

D. | O(n2) |

View/Hide Ans | |

Explanation | |

39. | The value of postfix expression : 8 3 4 + – 3 8 2 / + * 2 $ 3 + is |

A. | 17 |

B. | 131 |

C. | 64 |

D. | 52 |

View/Hide Ans | |

Explanation | |

40. | Consider the following statements for priority queue : S1 : It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations. S2 : The elements of a priority queue may be complex structures that are ordered on one or several fields. Which of the following is correct? |

A. | Both S1 and S2 are incorrect. |

B. | S1 is correct and S2 is incorrect. |

C. | S1 is incorrect and S2 is correct. |

D. | Both S1 and S2 are correct. |

View/Hide Ans | |

Explanation |

Author Does Not claim of any answer these answers are as per expert opinion