# 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
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)
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
44.       lg (n!) = .................
(A) O(n)
(B) O(lg n)
(C) O(n2)
(D) O(n lg n)
Explanation:
n!=n(n-1)(n-2).......3X2X1
≥(n/2)n/2
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
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
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
48.       The result of evaluating the following postfix expression is
5, 7, 9, *, +, 4, 9, 3, /, +, -
(A) 50
(B) 65
(C) 61
(D) 70
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