Midterm (DSA) Practice

We have T(n) in O(n^2) with T a function for the worst-case time complexity of algorithm A. Do we have T(n) in Theta(n^2)?

A) No, T is not necessarily bound from below by n^2.

B) Yes, because an upper bound for the worst-case gives a lower bound.

We perform heapsort. Which of the following can be an intermediate result after performing some but not all iterations?

A) [8,7,6,5,4,3,2,1,10,9]

B) [7,3,4,2,1,6,5,8,9,10]

C) [8,6,5,3,4,1,2,7,9,10]

D) [7,6,4,5,3,2,1,8,9,10]

We perform the procedure partition which is used in quicksort. The resulting array is [2, 3, 1, 4, 5, 8, 7, 9, 10]. Which are all keys that could have been the pivot?

A) 4, 5, 9, 10

B) 4, 5, 8, 9, 10

C) 4, 5, 8, 10

D) 5, 9, 10

What is the advantage of implementing a min-priority queue using a heap?

A) Adding and deleting are equally expensive.

B) Adding and deleting are both faster than if we use an array.

C) Removal is in constant time.

D) Adding is in constant time.

We consider quicksort with the auxiliary procedure for partition. Suppose that partition splits the array always in a 11-to-1 proportional split, so one part has length 1/12 and the other part has length 11/12. Then we have the following:


A) The recurrence for the running time of quicksort is T(n)= T(n/12) + T(11n/12) + cn with c a constant, and quicksort runs hence in O(n log n) time.

B) The recurrence for the running time of quicksort is T(n) = T(n/12) + T(11n/12) + cn with c a constant, and quicksort runs hence in O(n2) time.

C) The recurrence for the running time of quicksort is T(n) = 12T(n/12) + cn with c a constant, and quicksort runs hence in O(n log n) time.

D) The recurrence for the running time of quicksort is T(n) = 2T(n/2) +cn with c a constant, and quicksort runs hence in O(n log n) time.

What is a reason to use insertion sort as subroutine in bucket sort?

A) It performs relatively well on lists.

B) It has a good worst-case time complexity.

C) It performs relatively well on small inputs.

D) It has a good best-case time complexity.

Consider the pseudocode for partition. How can we optimize it a bit?

A) Start the for-loop with indices i and j both on the index before the first element of A that is larger than the pivot.

B) Start the for-loop with indices i and j both on the first element of A that is larger than the pivot.

C) Start the for-loop with index i on the first element of A that is larger than the pivot, and index j one before.

D) Start the for-loop with index j on the first element of A that is larger than the pivot, and index i one before.

Which of the following statements are true? 1) Heapsort is a divide-and-conquer algorithm. 2) Insertion sort can be faster than merge sort. 3) Heapsort is asymptotically optimal. 4) Bucket sort needs additional memory.

What is the result of adding the key 8 to the max-heap [9, 7, 4, 6, 5, 1, 3, 0, 0, 0 ] with heapsize 7?

A) [9, 8, 4, 7, 5, 1, 3, 6, 0, 0]

B) [8, 7, 4, 6, 5, 1, 3, 9, 0, 0]

C) [9, 7, 8, 6, 5, 1, 3, 4, 0, 0]

D) [8, 7, 4, 6, 5, 1, 9, 0, 0, 0]

Which of the following arrays is a max-heap?

A) [7,6,4,3,1,5,2]

B) [7,6,5,4,3,2,1]

C) [7,3,6,1,2,5,4]

D) [7,6,4,5,3,1,2]

E) [7,3,1,2,6,4,5]

F) [1,2,3,4,5,6,7]

Which of the following recurrence equations with T(0) = 1 gives T(n) in Theta(n^2)?

A) T(n) = T(n-1) + n

B) T(n) = T(n-1) + 1

C) T(n) = 2T(n/2) + n

D) T(n) = T(n-1)

What is the best-case time complexity of selection sort?

A) O(n) because we just check whether the array is ordered.

B) O(n log(n)) because that is the best-case for comparison-based sorting.

C) O(1) because we find immediately the smallest elements of the unordered part.

D) O(n^2) because we always have to completely traverse the unordered part.

We apply heapsort to an array where all n elements are the same. What is its performance in this case?

A) n log(n) because half of the nodes are already max-heaps.

B) n because in the for-loop we perform n times elementary time work

C) n because we can build a max-heap in linear time

D) n log(n) because in the for-loop we execute n times MaxHeapify.

We apply ExtractMax to a max-heap; the result is output 10 and the max-heap [6,3,5,2,1]. Which of the following could have been the input?

A) [10,3,6,2,1,5]

B) [10,5,6,2,1,3]

C) [10,6,5,2,3,1]

D) [10,5,1,2,3,6]

E) [10,6,5,3,2,1]

We perform the bottom-up procedure for building a max-heap. What is the result of performing (only) the first iteration of the for-loop on input A = [8, 1, 6, 4, 3, 7, 9]?

A) [9,1,6,4,3,7,8]

B) [8,4,9,1,3,7,6]

C) [8,1,9,4,3,7,6]

D) [9,1,8,4,3,7,6]

It is possible that an algorithm for MaxHeapify in Theta(1) will be found.

We perform quicksort on an input-array A consisting of n zeroes. What happens?

A) We get the best-case n log(n) performance.

B) We get the expected n log(n) performance.

C) We get a quadratic worst-case performance.

D) We get the best-case linear performance.

Consider the pseudocode for partition. What is a drawback?

A) If the array is sorted, we swap every element with itself.

B) We have to traverse the array completely.

C) It contains a for-loop.

D) We use two indices.

We perform the bottom-up heap construction on the array [1,2,3,4,5,6,7]. What is the result?

A) [7,6,5,4,2,1,3]

B) [7,5,6,4,2,1,3]

C) [7,5,6,2,4,1,3]

D) [7,6,5,4,3,2,1]