Data Structures and Algorithms Multiple Choice Questions - Set 5

41.       A complete graph can have ...............
(A) n2 spanning trees
(B) nn-2 spanning trees
(C) nn+1 spanning trees
(D) nn spanning trees
Answer: B
42.       Access time of a binary search tree may go worse in terms of time complexity upto ..............
(A) Ο(n2)
(B) Ο(n log n)
(C) Ο(n)
(D) Ο(1)
Answer: C
43.       A desirable choice for the partitioning element in quick sort is
(A) First element of the list
(B) Last element of the list
(C) Randomly chosen element of the list
(D) Median of the list
Answer: A
44.       lg (n!) = .................
(A) O(n)
(B) O(lg n)
(C) O(n2)
(D) O(n lg n)
Answer: D
log n! ≥ n/2logn/2
≥ n/2(logn-log2)
≥ n/2 (log n-1)
≤ n log n
= O(n log n)
45.       Binary search tree has best case run-time complexity of Ο(log n). What could the worst case?
(A) Ο(n)
(B) Ο(n2)
(C) Ο(n3)
(D) None of these
Answer: A
46.       The total number of elements that can be stored in a string without increasing its current amount of allocated memory is called its:
(A) Size
(B) Length
(C) Capacity
(D) Maximum size
Answer: C
47.       Graph traversal is different from a tree traversal, because:
(A) trees are not connected.
(B) graphs may have loops.
(C) trees have root.
(D) None of these
Answer: C
48.       The result of evaluating the following postfix expression is
5, 7, 9, *, +, 4, 9, 3, /, +, -
(A) 50
(B) 65
(C) 61
(D) 70
Answer: C
49.       Find the odd out:
(A) Prim's Minimal Spanning Tree Algorithm
(B) Kruskal's Minimal Spanning Tree Algorithm
(C) Floyd-Warshall's All pair shortest path Algorithm
(D) Dijkstra's Minimal Spanning Tree Algorithm
Answer: C
Floyd-Warshall's All pair shortest path Algorithm uses dynamic programming approach. All other mentioned algorithms use greedy programming approach
50.    Which data structure allows deleting data elements from the front and adding at the back?
(A) Stack
(B) Queue
(C) Binary-search tree
(D) Map
Answer: B

Post a Comment