VERSION 1 COMPSCI 220
THE UNIVERSITY OF AUCKLAND
SECOND SEMESTER, 2020
Campus: City
COMPUTER SCIENCE
Algorithms and Data Structures
(Time allowed: 50 minutes)
NOTE: There are 20 marks available in this test, which is worth 15% of your overall course mark.
FIRST: Enter your name and student ID into the Teleform sheet provided.
THEN: Attempt all questions and tick your answers on the Teleform sheet.
All questions have ONE correct answer and equal value.
DO NOT tick two answers as correct for the same question.
Keep your question book. Writing on it will not be marked.
Use of calculators is NOT permitted.
Good luck!
Page 1 of 8
VERSION 1 COMPSCI 220
1. The running time for the following code fragment is Θ(f(n)). What is f(n)?
for (int i = 0; i < n; i++)
for (int j = i− 10; j < i; j++)
for (int k = 1; k < n; k = 4 ∗ k)
System.out.println(i);
end for
end for
end for
A. n3
B. n2 log n
C. n log log n
D. n log n
E. n2
2. On which list does Quickselect achieve the minimum number of comparisons when finding the 2nd
order statistic?
A. [4, 1, 2, 6, 7]
B. All of the listed lists.
C. [2, 5, 6, 7, 1]
D. [4, 2, 1, 6, 7]
E. [5, 3, 2, 8, 12]
3. Choose the strongest true statement: Selection sort makes at least as many comparisons as insertion
sort
A. on every input
B. on reverse sorted input
C. on average for uniformly random input
D. for input with fewer inversions than average
E. in the worst case
4. Which of the following is NOT a property of mergesort?
A. Θ(n log n) worst-case sorting time.
B. Linear merge time.
C. In-place sorting.
D. Particularly good for sorting linked lists.
E. Θ(n log n) average-case sorting time.
Page 2 of 8
VERSION 1 COMPSCI 220
5. Which of the following statements about Treesort and BST is FALSE?
A. Insertion order 4,3,2,1 creates a BST of height 3.
B. Treesort on a list with n elements takes time in Θ(n log n) in the worst case.
C. Deleting an element of a BST can make the tree unbalanced.
D. A BST can be built using the quicksort algorithm.
E. The sorted list can be recovered from a BST by reading the keys according to an
inorder traversal.
6. Let T be a decision tree of a comparison based sorting algorithm for an input of n distinct elements.
Which of the following statements about T is FALSE?
A. Every node is connected to exactly two nodes on the next level.
B. T has n! leaves.
C. T is a binary tree.
D. The height of T is at least log2(n).
E. Every leaf corresponds to a possible final sorted list on n elements.
7. How many inversions are in the permutation 53412?
A. 10
B. 2
C. 8
D. 5
E. 3
8. The running time for the following code fragment is Θ(f(n)). What is f(n)?
for (int i = 1; i ≤ n; i = 2 ∗ i){
for (int j = 1; j ≤ i; j = 2 ∗ j){
// Do something elementary
}
}
A. log n log log n
B. log n
C. n log n
D. (log n)2
E. log logn
Page 3 of 8
VERSION 1 COMPSCI 220
9. Which of the following statements about f(n) = 5n3 log5 n + 20n
2 + 15n(log30 n)
2 is FALSE?
A. f(n) is Ω(n2 log n).
B. f(n) is Ω(n3 log n).
C. f(n) is Ω(n3).
D. f(n) is Ω(n3(log n)2).
E. f(n) is Ω(n(log n)2).
10. Which of the following statements about Heapsort is FALSE?
A. The idea of Heapsort is to build a binary heap and then delete elements of the highest
priority one-by-one until the heap is empty.
B. Consider an array heap implementation [9, 6, 8, 5, 4, 3]. After inserting a node with
key 10 the array will become [9, 6, 10, 5, 4, 3, 8].
C. Deleting all n elements of a heap takes time in Θ(n log n).
D. Heapifying is more efficient than building a binary heap by inserting nodes one-by-
one.
E. An array implementation of Heapsort moves the highest priority element in the heap,
after deletion, to the end of the active part of the array.
11. Which of these is NOT in Ω(n log n)?
A. n3/4(lnn)5
B. 0.001n2/ lg n
C.
√
n3 log10 n
D. n2(2− cos(n))
E. 17n lnn
12. The recurrence T (n) = 2T (n/2) + 1, T (1) = 0 has a solution that is in Θ(f(n)). What is f(n)?
A. n2
B. n
C. log n
D. 2n
E. n log n
Page 4 of 8
VERSION 1 COMPSCI 220
13. Which of the following lists can be used as an input list for Quickselect:
r = [1, 2, 3, 4, 5, 6], s = [6, 2, 3, 4, 1], t = [9, 6, 4, 2, 1, 0]
A. r and t.
B. All of them.
C. Only r.
D. Only s.
E. None of them.
14. A certain algorithm processes a list of size n by first inspecting each element, splitting the list into
2 sublists of equal size, then recursively processing the sublists. It gives rise to a recurrence for the
running time T (n) that looks like T (n) =***. What is ***?
A. T (n/2) + 1
B. 2T (n/2) + n
C. 2T (n/2) + 1
D. T (n/2) + n2
E. T (n/2) + n
15. Suppose that our best implementation of Algorithm A runs in time 10−10n2 nanoseconds and our
best implementation of Algorithm B runs in time 1010n nanoseconds. Choose the best answer.
A. Algorithm B is better than Algorithm A
B. Algorithm B is better than Algorithm A for inputs of size less than 1020
C. Algorithm B and Algorithm A are not comparable
D. Algorithm A is better than Algorithm B
E. Algorithm A is better than Algorithm B for inputs of size less than 1020
16. Which of the following trees is a binary heap?
A. B, D
B. B, C
C. A
D. B,C,D
E. B
Page 5 of 8
VERSION 1 COMPSCI 220
17. Which of the following inputs makes selection sort perform the largest number of comparisons?
A. all other choices result in the same number of comparisons
B. 5, 4, 3, 2, 1
C. 3, 5, 4, 1, 2
D. 2, 3, 5, 4, 1
E. 1, 2, 3, 4, 5
18. Which of the following trees is a BST?
A. B, C, D
B. A
C. B, D
D. B, C
E. C, D
19. Consider array-based quick sort Q, and array-based merge sort M , and suppose that both are being
run on random input data. Which of the following statements is true?
A. Q is faster than M because Q makes fewer comparisons than M
B. Q is faster than M even though Q makes more comparisons than M
C. Q is slower than M because Q makes more comparisons than M
D. Q is slower than M even though Q makes fewer comparisons than M
E. Q is asymptotically faster than M
20. An implementation of insertion sort spent 1 second to sort a list of 106 random records. How long
will it take to sort 107 random records?
A. 100 seconds
B. 600 seconds
C. 10 seconds
D. 60 seconds
E. 1000 seconds
Page 6 of 8
VERSION 1 COMPSCI 220
Working page 1
Page 7 of 8
VERSION 1 COMPSCI 220
Working page 2
Page 8 of 8






















































































































































































学霸联盟