Untitled
The University of Michigan
Electrical Engineering & Computer Science
EECS 281: Data Structures and Algorithms
Fall 2017
MIDTERM EXAM
Multiple Choice Portion
KEY 1 – ANSWERS
Wednesday October 25, 2017
6:30PM – 8:00PM (90 minutes)
INSTRUCTIONS:
• Select only ONE answer per question.
• The exam is closed book and notes except for one 8.5”x11” sheet of handwritten notes (one
side can be used). All electronic device use is prohibited during the exam (calculators, phones,
laptops, etc.).
• Record your NAME, STUDENT ID number and exam KEY number on the Scantron
form. There will be a penalty for incorrectly filling out the form.
• There is no need to record your section number, all Scantrons will go into one pile.
• There are 24 multiple-choice questions worth 2.5 points each.
• Record your choices for all multiple choice questions on the computer-graded (Scantron)
answer form. Use a number 2 pencil, not a pen. Fill the circle completely. There is no partial
credit for multiple-choice questions.
• There is no penalty for wrong answers: it is to your benefit to record an answer to each multiple-
choice question, even if you’re not sure what the correct answer is.
• The questions vary in difficulty — try not to spend too much time on any one question. Use
your time wisely.
• This multiple-choice book will NOT be turned in; NOTHING written inside will be graded.
• Turn in the written portion exam book and the Scantron answer form. One will not be accepted
without the other. Keep your notes sheet and multiple-choice book.
• When asked about memory complexity, consider all possible sources (stack and heap).
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 2 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
1. The Need for Speed
You’ve “finished” writing code for project 3, and decide to run it for the first time on one of the small
spec tests. Good news – it runs correctly and seems to be blistering fast! When you plot out runtimes
for the spec test inputs, you seem to see an Θ(n) relationship although you correctly implemented a
Θ(n log n) algorithm. What could be the reason for this?
A) Θ(n log n) algorithms are also always Θ(n)
B The spec tests were too small for the actual relationship to be revealed.
C) The spec tests were too large for the actual relationship to be revealed.
D) The program used to collect the time data changed your Θ(n log n) algorithm into an Θ(n)
algorithm.
2. Using the Master Theorem
Which of the following recurrence relations can one solve by applying the Master Theorem?
A) T (n) = nT (n/2) +Θ(n2)
B T (n) = T (n/10) +Θ(
√
n)
C) T (n) = 4T (n/6) + 2T (n/4) +Θ(n2)
D) T (n) = 2T (n− 2) +Θ(n100)
E) None of the above choices can be solved using the Master Theorem
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 3 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
3. Complexity Analysis
What is the runtime complexity of the following program?
void liberation(int s) {
for (int i = s; i > 0; i /= 2)
std::cout << "there's a fine line" << std::endl;
} // liberation()
void aquemini(int k) {
if (k <= 1)
return;
liberation(k);
aquemini(k - 1);
} // aquemini()
void spottie(int n) {
std::vector
for (auto &x : ottie)
aquemini(x);
if (n > 281)
liberation(n);
else
aquemini(n – 1);
} // spottie()
int main() {
int n = 0;
std::cin >> n;
spottie(n);
return 0;
} // main()
A) Θ(n log n)
B) Θ(n2)
C Θ(n2 log n)
D) Θ(n3)
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 4 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
4. Apply the Master Theorem
What is the time complexity of the following recurrence relation?
T (n) = 2T (4n/16) +Θ(
√
n)
A Θ(
√
n log n)
B) Θ(
√
n)
C) Θ(n.25)
D) None of the above choices
5. Substitution
Consider the recurrence relation T (n) = T (n − 2) + 3n. If we solve this recurrence using the
substitution process, which of the following is a valid first step in the expansion?
A) T (n) = T (n− 2) + 3n = T (n− 4) + 32n = T (n− 6) + 33n = …
B) T (n) = T (n− 2) + 3n = T (n− 4) + 3n + 3n = T (n− 6) + 3n + 3n + 3n = …
C T (n) = T (n− 2) + 3n = T (n− 4) + 3n + 3n−2 = T (n− 6) + 3n + 3n−2 + 3n−4 = …
D) T (n) = T (n−2)+3n = T (n−2)+T (n−4)+3n = T (n−2)+T (n−4)+T (n−6)+3n = …
6. Hey, you! Get outta my queue!
What is the time complexity to remove the most recently added element in a std::queue of size
n?
A) Θ(1)
B Θ(n)
C) Θ(n log n)
D) Θ(n2)
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 5 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
7. Recurrence Relation
Given the function below, calculate the recurrence relation. Assume that bar(n) runs in log n time.
void foo(int n){
if (n == 1)
return;
foo(n / 4);
int k = n * n;
for (int i = 0; i < k; ++i)
for (int j = 0; j < n; ++j)
bar(n);
for (int i = 0; i < n; ++i)
foo(n / 2);
bar(k);
} // foo()
A T (n) = T (n/4) + n3 log n+ nT (n/2) + 2 log n
B) T (n) = T (n/4) + n3 log n+ nT (n/2)
C) T (n) = T (n/4) + n3 + nT (n/2) + log n
D) T (n) = T (n/4) + n2 log n+ nT (n/2) + 2 log n
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 6 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
8. The Unknown Container Library
Suppose you are given an STL container (of unknown type) that is initially empty. The following
functions are called:
container.push(-2);
container.push(8);
container.push(-1);
container.push(3);
container.push(4);
container.pop();
container.pop();
Suppose you were told that the largest element remaining in the container is 8. Based on this
information, the unknown STL container must be:
A) A stack or a max-priority-queue
B) A stack or a queue
C) A min-priority-queue or a max-priority-queue
D A stack or a min-priority-queue
E) A queue or a min-priority-queue
9. Using a Deque
Which of the following containers can be implemented efficiently using a std::deque<> as the
underlying container?
A) Stack
B) Queue
C) Priority queue
D All of the above
E) None of answer choices (A), (B), (C) or (D)
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 7 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
10. Watch your PQs and Functors
What does the following code output?
struct CustomComparator {
bool operator()(const int lhs, const int rhs) const {
// std::abs(x) returns the absolute value of x
return (std::abs(lhs – 281) > std::abs(rhs – 281));
}
};
int main() {
std::priority_queue
myPQ.push(0);
myPQ.push(100);
myPQ.push(200);
myPQ.push(300);
myPQ.push(400);
while (!myPQ.empty()) {
std::cout << myPQ.top() << " ";
myPQ.pop();
} // while
std::cout << std::endl;
return 0;
} // main()
A) 0 100 200 300 400
B) 400 300 200 100 0
C) 0 100 400 200 300
D 300 200 400 100 0
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 8 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
11. A Zero-Sum Problem
Suppose you are given a sorted array of n integers, and told that there are two distinct values whose
sum is 0. What is the worst-case complexity of the best possible algorithm to return the indices of
these values? For example, given {−3,−2, 0, 1, 2, 4}, you would return the indices corresponding to
the values -2 and 2.
A) Θ(1)
B) Θ(log n)
C Θ(n)
D) Θ(n log n)
E) Θ(n2)
12. The Upper Lower Bound
What is the worst-case time complexity of std::lower_bound(), given that the container is
sorted and contains n elements?
A) Θ(1)
B) Θ(n)
C Θ(log n)
D) Θ(n log n)
13. Adaptability
One way to classify sorting algorithms is adaptive or non-adaptive. What is an advantage of a NON-
adaptive sorting algorithm?
A) It can change its sequence of operations based on the input.
B It may be simpler to implement than an adaptive algorithm.
C) It is always faster than an adaptive algorithm.
D) It sometimes performs less work, depending on the order of the data.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 9 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
14. Size and Resize
Unless specified otherwise, a new vector is created with size 0. Whenever there is not enough room
to .push() a new value, the size doubles (minimum size is 1). The .size() of a vector is the
number of elements that can safely be accessed via the [] operator, and the .capacity() is the
size of the underlying dynamic memory. What is the output of the following code?
vector
for (int i = 1; i <= 8; ++i)
vec.push_back(i);
vec.resize(3 + vec.back());
vec.reserve(13 + vec.front());
cout << vec.size() << " " << vec.capacity() << endl;
A) 11 16
B) 14 16
C) 11 11
D) 14 14
E 11 14
15. Bucket Sort
What is the primary drawback of bucket-sort?
A) It has best-case Θ(n log n) runtime.
B) It has worst-case Θ(n2) runtime.
C It can only be used in certain specialized cases.
D) It is nondeterministic.
E) Buckets can only hold one item.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 10 of 13 Midterm Exam · Fall 2017
Record your answers to this page on the Scantron sheet
16. A Complete Reversal
Below is some code for reversing a vector.
vector
stack
for (size_t i = 0; i < v.size(); ++i) s.push(v[i]); for (size_t i = 0; i < v.size(); ++i) { v[i] = s.top(); s.pop(); } // for Assuming that n = v.size(), what is TRUE about this code? A) The algorithm runs in Θ(n2) time B) The memory complexity is Θ(1) C The memory complexity is Θ(n) D) The stack should be replaced by a queue in order to properly reverse the items inside the vector 17. Pivot! Suppose our implementation of Quicksort always chooses the first element of the array as the pivot. If we use this implementation on an n-element array of distinct values, how many different orderings of the values would cause this algorithm to perform on the order of n2 comparisons of data values? A) 2n B 2n−1 C) n2 D) n! E) None of the above choices University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti Downloaded by Xiao Song ( ) lOMoARcPSD|3188099 Page 11 of 13 Midterm Exam · Fall 2017 Record your answers to this page on the Scantron sheet 18. Quicksort Which of the following statements about Quicksort is TRUE? A) The quicksort algorithm, as defined in class, is stable. B) Quicksort cannot be done in-place. C) In the average case, the time complexity is Θ(n log n) and space complexity is Θ(n) in stack frames. D If the pivot was always chosen (in constant time) to be the median and the array values were distinct, then the worst-case time complexity would be Θ(n log n). E) Quicksort cannot be implemented using iteration instead of recursion. 19. Sorting a Linked List Which of the following sorting algorithms can sort a singly-linked list in-place with a worst-case time complexity of Θ(n log n)? A) Quicksort B Mergesort C) Heapsort D) A singly-linked list cannot be sorted in-place E) The worst-case time complexity is always Θ(n2) 20. Leaf Height You are given a binary max-heap containing n nodes, and the tree height is h. The maximum difference of depth between any two leaf nodes in the tree represntation of this max-heap is: A) h B) log n C) n/h D 1 E) 0 University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti Downloaded by Xiao Song ( ) lOMoARcPSD|3188099 Page 12 of 13 Midterm Exam · Fall 2017 Record your answers to this page on the Scantron sheet 21. Binary Heaps Operations Suppose we have the max-heap represented below: 95 75 2049 78 6619 And then carry out the following operations: 1. Pop the top value 2. Push the value 83 Which diagram represents the state of the heap after these two operations have completed? A) 83 78 4975 66 2019 B 83 78 7549 66 2019 C) 83 75 2049 78 6619 D) 83 66 7549 78 2019 University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti Downloaded by Xiao Song ( ) lOMoARcPSD|3188099 Page 13 of 13 Midterm Exam · Fall 2017 Record your answers to this page on the Scantron sheet 22. Valid Heap Which of the following is NOT an array representation of a valid binary min-heap? The “top” of the heap is the first value shown. A) [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 17 ] B [ 2, 4, 5, 1, 6, 7, 9, 3, 14, 10, 15, 17, 8 ] C) [ 1, 2, 5, 3, 6, 7, 9, 4, 14, 10, 15, 17, 8 ] D) [ 1, 2, 5, 3, 6, 7, 9, 4, 8, 10, 15, 17, 14 ] E) All of the above choices are valid min-heaps. 23. Strings and Sequences If you are searching for string needle in string haystack (variable names, not actual contents) and using brute-force string searching, what would the average-case and worst-case time complexity be? length needle and length haystack are the lengths of each string. A Θ(length haystack), Θ(length needle ∗ length haystack) B) Θ(length needle), Θ(length needle+ length haystack) C) Θ(length haystack), Θ(length haystack2) D) Θ(length needle), Θ(length haystack) 24. Rabin Fingerprints If the fingerprints of two strings differ, do the strings themselves differ? A) Never B) Only if the strings are of different lengths C) Only if the strings are the same length D Always University of Michigan EECS 281 : Data Structures and Algorithms Darden/Markov/Paoletti Downloaded by Xiao Song ( ) lOMoARcPSD|3188099