Q1: 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
Q2: Sieve Technique can be applied to the selection problem?
(A) True
(B) False
Answer: (A) True
Q3: 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
Q4: 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
Q5: 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
Q6: In Sieve Technique we do not know which item is of interest:
(A) True
(B) False
Answer: (A) True
Q7: 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
Q8: 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
Q9: For the heap sort, access to nodes involves simple ___ operations.
(A) arithmetic
(B) binary
(C) algebraic
(D) logarithmic
Answer: (A) arithmetic
Q10: For the sieve technique we solve the problem:
(A) recursively
(B) mathematically
(C) precisely
(D) accurately
Answer: (A) recursively
Q11: The sieve technique works in:
(A) phases
(B) numbers
(C) integers
(D) routines
Answer: (A) phases
Q12: Slow sorting algorithms run in:
(A) T(n^2)
(B) T(n)
(C) T(log n)
(D) T(n log n)
Answer: (A) T(n^2)
Q13: In the analysis of Selection algorithm, we make a number of passes; it could be as many as:
(A) T(n)
(B) T(n / 2)
(C) log n
(D) n / 2 + n / 4
Answer: (B) T(n / 2)
Q14: The sieve technique is a special case, where the number of subproblems is just:
(A) 5
(B) many
(C) 1
(D) few
Answer: (C) 1
Q15: In which order can we sort?
(A) increasing order only
(B) decreasing order only
(C) increasing order or decreasing order
(D) both at the same time
Answer: (C) increasing order or decreasing order
Q16: Analysis of Selection algorithm ends up with:
(A) T(n)
(B) T(1 / 1 + n)
(C) T(n / 2)
(D) T((n / 2) + n)
Answer: (D) T((n / 2) + n)
Q17: The analysis of Selection algorithm shows the total running time is indeed ___ in n:
(A) arithmetic
(B) geometric
(C) linear
(D) orthogonal
Answer: (C) linear
Q18: How many elements do we eliminate in each time for the Analysis of Selection algorithm?
(A) n / 2 elements
(B) (n / 2) + n elements
(C) n / 4 elements
(D) 2 n elements
Answer: (A) n / 2 elements
Q19: For heap sort, we store the tree nodes in:
(A) level-order traversal
(B) in-order traversal
(C) pre-order traversal
(D) post-order traversal
Answer: (A) level-order traversal
Q20: One clever aspect of heaps is that they can be stored in arrays without using any:
(A) pointers
(B) constants
(C) variables
(D) functions
Answer: (A) pointers
Q21: 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)
Q22: The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of:
(A) divide-and-conquer
(B) decrease and conquer
(C) greedy nature
(D) 2-dimension Maxima
Answer: (A) divide-and-conquer
Q23: The number of nodes in a complete binary tree of height h is:
(A) 2^(h+1) – 1
(B) 2*(h+1) – 1
(C) 2*(h+1)
(D) ((h+1)^2) – 1
Answer: (A) 2^(h+1) – 1
Q24: Sieve Technique applies to problems where we are interested in finding a single item from a larger set of:
(A) n items
(B) phases
(C) pointers
(D) constant
Answer: (A) n items
Q25: Memorization is:
(A) To store previous results for future use
(B) To avoid unnecessary repetitions by writing down recursive results
(C) To make the process accurate
(D) None of the above
Answer: (B) To avoid unnecessary repetitions by writing down recursive results
Q26: Which sorting algorithm is faster:
(A) O(n^2)
(B) O(n log n)
(C) O(n+k)
(D) O(n^3)
Answer: (B) O(n log n)
Q27: Quick sort is stable & in place:
(A) Not stable but in place
(B) Stable but not in place
(C) Sometimes stable & sometimes in place
Answer: (A) Not stable but in place
Q28: One example of an in-place but not stable algorithm is:
(A) Merge Sort
(B) Quick Sort
(C) Continuation Sort
(D) Bubble Sort
Answer: (B) Quick Sort
Q29: In Quick Sort, constants hidden in T(n log n) are:
(A) Large
(B) Medium
(C) Small
(D) Not Known
Answer: (C) Small
Q30: Continuation sort is suitable to sort elements in range 1 to k when:
(A) K is large
(B) K is not known
(C) K may be small or large
(D) K is small
Answer: (D) K is small
Q31: In stable sorting algorithm, if duplicate elements remain in the same relative position after sorting:
(A) One array is used
(B) More than one array is required
(C) Duplicating elements not handled
Answer: (A) One array is used
Q32: Which may be a stable sort?
(A) Merge
(B) Insertion
(C) Both above
(D) None
Answer: (C) Both above
Q33: An in-place sorting algorithm is one that uses ___ arrays for storage:
(A) Two-dimensional
(B) More than one
(C) No additional array
(D) None of the above
Answer: (C) No additional array
Q34: We do sorting to:
(A) keep elements in random positions
(B) keep algorithm run in linear order
(C) keep algorithm run in (log n) order
(D) keep elements in increasing or decreasing order
Answer: (D) keep elements in increasing or decreasing order