Q1: We do sorting to:
(A) keep elements in random positions
(B) keep the algorithm run in linear order
(C) keep the algorithm run in (log n) order
(D) keep elements in increasing or decreasing order
Answer: (D) keep elements in increasing or decreasing order
Q2: Heaps can be stored in arrays without using any pointers; this is due to the ___ nature of the binary tree:
(A) left-complete
(B) right-complete
(C) tree nodes
(D) tree leaves
Answer: (A) left-complete
Q3: Sieve Technique can be applied to the selection problem?
(A) True
(B) False
Answer: (A) True
Q4: A heap is a left-complete binary tree that conforms to:
(A) increasing order only
(B) decreasing order only
(C) heap order
(D) (log n) order
Answer: (C) heap order
Q5: A (an) ___ is a left-complete binary tree that conforms to the heap order:
(A) heap
(B) binary tree
(C) binary search tree
(D) array
Answer: (A) heap
Q6: Divide-and-conquer refers to breaking the problem into a small number of:
(A) pivot
(B) Sieve
(C) smaller sub problems
(D) Selection
Answer: (C) smaller sub problems
Q7: In Sieve Technique we do not know which item is of interest:
(A) True
(B) False
Answer: (A) True
Q8: The recurrence relation of Tower of Hanoi is T(n) = {1 if n=1, 2T(n-1) if n>1}. To move a tower of 5 rings from one peg to another, how many ring moves are required?
(A) 16
(B) 10
(C) 32
(D) 31
Answer: (D) 31
Q9: In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent ___ series in the analysis:
(A) linear
(B) arithmetic
(C) geometric
(D) exponent
Answer: (C) geometric
Q10: For the heap sort, access to nodes involves simple ___ operations:
(A) arithmetic
(B) binary
(C) algebraic
(D) logarithmic
Answer: (B) binary
Q11: How much time does Merge Sort take for an array of numbers?
(A) T(n^2)
(B) T(n)
(C) T(log n)
(D) T(n log n)
Answer: (D) T(n log n)
Q12: One of the clever aspects of heaps is that they can be stored in arrays without using any:
(A) pointers
(B) constants
(C) variables
(D) functions
Answer: (A) pointers
Q13: Counting sort is suitable to sort the elements in range 1 to k when:
(A) K is large
(B) K is small
(C) K may be large or small
(D) None
Answer: (B) K is small
Q14: Which may be a stable sort?
(A) Merge Sort
(B) Insertion Sort
(C) Both above
(D) None of the above
Answer: (C) Both above
Q15: Quick sort is based on divide-and-conquer paradigm; we divide the problem based on:
(A) Number of inputs
(B) Arrangement of elements
(C) Pivot element
(D) Size of elements
Answer: (C) Pivot element