The University of Michigan
Electrical Engineering & Computer Science
EECS 281: Data Structures and Algorithms
Winter 2018
MIDTERM EXAM
Multiple Choice Portion
KEY 1 – ANSWERS
Wednesday February 21, 2018
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 only). All electronic devices are prohibited during the exam.
• Record your NAME, STUDENT ID number and exam KEY number on the Scantron
form. This must be completed BEFORE TIME IS CALLED. There will be a penalty if
this is filled out incorrectly, or if you wait until after time is called to fill it out.
• 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. There is no partial credit.
• Record your choices for all multiple choice questions on the Scantron form. This must be
completed BEFORE TIME IS CALLED. Use a number 2 pencil, not a pen. Fill in the circle
completely. NOTHING written inside this multiple choice booklet will be graded.
• 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.
• Turn in both booklets and the Scantron form. We will not accept your exam unless you turn in
all parts. Keep your cheat sheet.
• When asked about memory complexity, consider all possible sources (stack and heap).
Page 2 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
1. Measuring Runtime
When measuring runtime, an algorithm which you analytically determined to be Θ(n2) appears to be
running in Θ(n) time. In which scenario could this not be possible?
A) The implemented algorithm differs from the one analyzed
B The test inputs exposed worst-case behavior
C) The complexity analysis was incorrect
D) The input sizes tested were too small
2. Complexity Analysis
Which one of the following statements is true?
A) sin(n) is O(cos(n))
B) 2n + 3k is O(2k + 3k)
C) 2n+k is O(2n + 2k)
D log2 n is O(
√
n)
E) 23n is O(22n)
3. Master Theorem
Suppose that you are given only part of a recurrence relation for a recursive function, which you are
told is directly solvable by the Master Theorem:
T (n) = T (?) + 3n
Which one of the following must be true?
A) T (n)→ Θ(1)
B T (n)→ Θ(n)
C) T (n)→ Θ(n log n)
D) T (n)→ Θ(n(log n)2)
E) T (n)→ Θ(n2)
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
xiaosong
Highlight
Page 3 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
4. Code Complexity
What is the recurrence relation for the following function? Is this solvable by the Master Theorem?
void bar(int n) {
if (n == 0)
return;
bar(n / 3);
int modulo = 0;
for (int i = 0; i < sqrt(n); ++i)
for (int j = i; j < n; j += sqrt(n))
modulo += j % 2;
bar(n / 3);
cout << modulo;
} // bar()
A) T (n) = T (n/3) + n, yes
B) T (n) = T (n/3) + n1/2, no
C) T (n) = 2T (n/3) + n1/2, no
D T (n) = 2T (n/3) + n, yes
E) T (n) = T (n/3) + n1/2, yes
5. Sorting Using Stacks
What is the worst-case time complexity for sorting a std::stack using only stacks and stack
operations?
A) Θ(n)
B) Θ(n log n)
C Θ(n2)
D) Θ(n3)
E) Θ(n!)
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
j 最多是一个sqrt
xiaosong
Highlight
Page 4 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
6. Resize/Reserve
Suppose you are given a program that stores its primary data in an instance of std::vector.
The program executes correctly for small test datasets, but runs out of memory while reading large
datasets. What is a possible solution to overcome this problem?
I. Use .resize() with the exact number of elements, then use .push_back().
II. Use .resize() with the exact number of elements, then use .operator[]().
III. Use .reserve() with the exact number of elements, then use .push_back().
IV. Use .reserve() with the exact number of elements, then use .operator[]().
A) Only (I)
B) Only (II)
C) Either (I) or (III)
D Either (II) or (III)
E) All four choices have a chance to solve the problem.
7. Three Largest
Given an unsorted array of integers of size n, what would be the tightest worst-case time complexity
to find the three largest elements in the array, in the most efficient way possible?
A) Θ(1)
B) Θ(log n)
C Θ(n)
D) Θ(n log n)
E) Θ(n3)
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
Page 5 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
8. Valid Access
The following code has undefined behavior. Which one of the indicated lines is directly related to
this undefined behavior?
#include
#include
using namespace std;
int main () {
vector
¬ for (int i = 1; i < 10; ++i)
myvector.push_back(i);
myvector.resize(5);
® myvector.resize(8, 100);
myvector.resize(9)
myvector.reserve(10);
¯ myvector[9] = 10;
° for (size_t i = 0; i < myvector.size(); ++i)
cout << myvector[i] << ' ';
cout << '\n';
return 0;
} // main()
A) 1
B) 2
C) 3
D 4
E) 5
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
Page 6 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
9. Using the STL
Consider the following code that uses several standard library functions and objects.
#include
#include
#include
using namespace std;
int main() {
int myints[] = {32, 71, 12, 45, 26, 80, 53, 33};
vector
sort(vec.begin(), vec.begin() + 4, less
reverse(vec.begin(), vec.end());
for (auto val : vec)
cout << val << ' ';
cout << '\n';
return 0;
} // main()
What does the above code output?
A 53 80 26 71 45 32 12
B) 33 53 80 26 71 45 32 12
C) 12 32 45 71 26 80 53
D) 71 45 32 12 26 80 53 33
E) This code produces undefined output
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
xiaosong
Highlight
Page 7 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
10. Mystery Container 1
Consider the following segment of code. The variable uds (unknown data structure) is instantiated
to be an instance of an unspecified standard library container type.
uds.push(3);
uds.push(8);
uds.push(7);
cout << uds.top() << ", ";
uds.pop();
uds.push(5);
uds.push(9);
uds.push(2);
cout << uds.top() << ", ";
uds.pop();
cout << uds.top();
uds.pop();
If the output of this code is “7, 2, 9”, what is a valid type for uds?
A) std::deque
B std::stack
C) std::queue
D) std::priority_queue
E) None of the above
11. Mystery Container 2
Using the same code, if the output is “8, 9, 7”, what is a valid type for uds?
A) std::deque
B) std::stack
C) std::queue
D std::priority_queue
E) None of the above
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
Page 8 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
12. One Left Out
Consider an unsorted array of size n− 1 containing unique numbers in the range 1 to n. One number
from 1 to n is missing from the array. What is the worst-case time and additional memory complexity
of finding the missing number, if you want to do so in the most efficient way?
A) Θ(log n) time, Θ(1) additional memory
B Θ(n) time, Θ(1) additional memory
C) Θ(n) time, Θ(n) additional memory
D) Θ(n log n) time, Θ(1) additional memory
E) Θ(n2) time, Θ(n) additional memory
13. Keeping the Heap
Consider a max-heap-ordered complete binary tree represented as the following array:
{9, 8, 7, 6, 5, 4, 3, 2}. Perform the following operations using algorithms for binary
heaps discussed in lecture. Ensure that the heap property is restored at the end of every individual
operation.
I. Update element with value 2 to have value 10
II. Update element with value 9 to have value 1
III. Remove the max element from the heap
What does the contents of the array after all three operations have all been completed?
A {8, 6, 7, 1, 5, 4, 3}
B) {8, 1, 7, 6, 5, 4, 3}
C) {8, 7, 6, 4, 3, 1, 5}
D) {8, 7, 4, 6, 5, 3, 1}
E) None of the above
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
使用的是先计算sum，然后减去的方式
Page 9 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
14. Heapify
Consider the following unsorted array: {3, 7, 45, 76, 1, 8, 31, 98}.
Perform an Θ(n) heapify operation to turn this data into a valid max-heap. What is the contents of
the array after the heapify operation?
A) {98, 45, 76, 1, 8, 31, 3, 7}
B {98, 76, 45, 7, 1, 8, 31, 3}
C) {98, 76, 45, 1, 8, 31, 7, 3}
D) {98, 76, 45, 1, 8, 31, 3, 7}
E) {98, 45, 76, 8, 31, 1, 3, 7}
15. Pushing the Heap
Given an empty min-heap priority queue, you push the following values in order:
3, 1, 4, 2, 8, 0, 7, 6
What would the underlying array structure look like after one value was popped off the heap?
A [1, 2, 4, 3, 8, 6, 7]
B) [1, 2, 3, 4, 6, 7, 8]
C) [1, 4, 2, 3, 8, 6, 7]
D) [1, 4, 2, 6, 7, 3, 8]
E) [1, 2, 4, 8, 3, 6, 7]
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
Page 10 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
16. Which Sort?
Consider the array {14, 6, 49, 10, 38, 23, 18, 12, 40, 6}. A snapshot is taken
during execution of a sorting algorithm. If the snapshot of the array is {6, 10, 14, 18, 12,
23, 38, 6, 40, 49}, which one of the following sorts is currently being run on this array?
A Bubble Sort
B) Selection Sort
C) Insertion Sort
D) Quicksort
E) Mergesort
17. Sorting in Line
A local supermarket wishes to develop a new method to serve customers: customers with the fewest
number of items will be served first. Customers with equal numbers of items are served in arrival
order. If you can only look at number of items, which one of the following sorts would not allow the
supermarket to accomplish these goals?
A) Bubble Sort
B Selection Sort
C) Insertion Sort
D) Mergesort
E) All of the above sorts will satisfy the supermarket’s requirements
18. Elementary Sorts
Which one of the following is true?
A) Bubble Sort can be implemented to be either adaptive or stable, but not both
B) Insertion Sort is fast on nearly sorted arrays, but requires Θ(n) auxiliary space
C) Using binary search within an Insertion Sort will increase the speed, but the sort will no longer
be stable
D) Selection Sort performs only Θ(n) comparisons on an already sorted array
E None of the above are true
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
并不改变后半部分的相对位置
后面部分整体都不变
会有一个piviot在中间
有local的大小关系
which sort is not stable
still stable, but time compelxity won’t change cause still need to move
n^2
Page 11 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
19. Partitioning
Consider the following implementation of partition from the Quicksort algorithm (the same code
given in lecture). Note that the last element in the array is chosen as the pivot.
int partition(int a[], int left, int right) {
int pivot = –right;
while (true) {
while (a[left] < a[pivot])
++left;
while (left < right && a[right - 1] >= a[pivot])
–right;
if (left >= right)
break;
swap(a[left], a[right – 1]);
} // while
swap(a[left], a[pivot]);
return left;
} // partition()
Let int[] myarr = {4, 14, 9, 1, 2, 5, 3, 8, 6}. What is the contents of myarr
after one call to partition(myarr, 0, 9)?
A) {4, 3, 5, 1, 2, 6, 14, 9, 8}
B) {4, 3, 5, 1, 2, 9, 14, 8, 6}
C) {4, 3, 1, 5, 2, 6, 14, 8, 9}
D {4, 3, 5, 1, 2, 6, 14, 8, 9}
E) {4, 3, 5, 2, 1, 6, 14, 9, 8}
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
Page 12 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
20. Quicksort and Mergesort
Which one of the following statements is true about sorting arrays?
A Our mergesort requires Θ(n) auxiliary space
B) Quicksort is stable, while merge sort is not
C) Mergesort and Quicksort have the same worst case time complexity
D) Quicksort cannot be performed in-place
E) The best case time complexity of Quicksort is Θ(n)
21. Best Pivot
You are using quicksort to sort the following 10 elements in increasing order:
int arr[] = {74, 53, 46, 50, 20, 35, 30, 25, 45};
Which one of the following elements would be the best choice for the pivot?
A) 74
B) 46
C) 35
D) 30
E 45
22. String Comparison
When would one use std::equal() instead of == when comparing strings?
A) When the comparison should not be case sensitive
B) When using C-strings
C) It does not matter since they behave the same way
D) To check for a matching prefix
E More than one of the above
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti
xiaosong
Highlight
Page 13 of ?? Midterm Exam · Winter 2018
Record your answers to this page on the Scantron sheet
23. String Fingerprinting
You are given the Rabin-Karp fingerprints of two non-empty strings. The original strings are
unknown, but the fingerprints are the same. Which of the following are valid conclusions?
A) The strings are definitely the same
B) The strings are definitely different
C) The strings definitely have the same length
D) More than one of A, B, C
E None of A, B, C
24. Sorting Strings
What is the worst-case time complexity of sort() on a vector of N strings, each of length M
characters?
A) Θ(N ∗ logN)
B) Θ(M ∗ logN)
C Θ(M ∗N ∗ logN)
D) Θ(M2 ∗N ∗ logN)
E) Θ(N ∗ log(MN))
University of Michigan EECS 281 : Data Structures and Algorithms Angstadt/Darden/Paoletti