Pr
ac
tic
eThe University of MichiganElectrical Engineering & Computer ScienceEECS 281: Data Structures and AlgorithmsFall 2021
PRACTICE MIDTERM EXAM
KEY 1
Thursday, October 21, 2021
7:00PM Start Time (140 minutes)
Uniqname: Student ID:
Name:
Uniqname of person to your left:
Uniqname of person to your right:
Honor Pledge:
“I have neither given nor received unauthorized aid on this examination,
nor have I concealed any violations of the Honor Code.”
Signature:
INSTRUCTIONS:
• The exam is closed book and notes except for one 8.5″x11″ sheet of handwritten notes (one side
only) . All electronic device use is prohibited during the exam (calculators, phones, laptops, etc.).
• Print your name, student ID number, and uniqname LEGIBLY. Sign the Honor Pledge; this pledge
applies to both the written and multiple choice sections. Your exam will not be graded without your
signature.
• Record the UNIQNAME of the students to both your left and right. Write down nullptr if you
are at the end of a row and there is no one on a given side.
• Record your UNIQNAME at the top of each odd-numbered page in the space provided. This will
allow us to identify your exam if pages become separated during grading.
• This exam booklet contains BOTH the multiple choice and written portions of the exam.
Instructions for each portion are provided at the beginning of their respective sections.
• DO NOT detach any pages from this booklet.
• There should be 20 pages in this book; if you are missing any pages, please let an instructor know.
Pr
ac
tic
ePage 2 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiMultiple Choice Portion [60 points]
MULTIPLE CHOICE INSTRUCTIONS:
• Select only ONE answer per multiple choice question.
• There are 24 multiple choice questions worth 2.5 points each.
• Record your choices for all multiple choice questions using the circles in the boxed area next to
each question. Use a number 2 pencil, not a pen (so that you may change your answer). Fill the
circle completely. There is no partial credit for multiple-choice questions. Make sure you bubble
in the correct letter. See the example below for how to select your answer.
• 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.
• When asked about memory complexity, consider all possible sources (stack and heap).
• The term “heap” as a data structure refers to a binary heap, unless explicitly stated otherwise.
• The term “binary search tree” refers to a standard implementation that does not self-balance, unless
explicitly stated otherwise.
Pr
ac
tic
eEECS 281 Practice Midterm Exam · Fall 2021 Uniqname: Page 3 of 20Record your answers in the bubbles next to each question.1. Master Theorem A B C D E
Which of the following recurrence relations can one solve by applying the Master Theorem?
A) T (n) = 1
2
T (n
4
) + Θ(n)
B) T (n) = T (n
2
) + Θ(nlog2 4)
C) T (n) = 4T (n− 1) + Θ(1)
D) T (n) = 4T (n
2
) + 2T (n
4
) + Θ(n2)
E) None of the above.
2. Measuring Runtime A B C D E
Consider the following function:1 int func(double m, double n) {
2 int c = 0;
3 while (m > n) {
4 m = m/2;
5 for (int i = 1; i < n; i*=3;)
6 ++c;
7 } // while
8
9 return c;
10 } // func
What best characterizes the running time of a call to this function?
A) O(n logm)
B) O(m
n
log n)
C) O((log m
n
) · (log n))
D) O(mn log(mn))
E) O(mn · (logm) · (log n))
Pr
ac
tic
ePage 4 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiRecord your answers in the bubbles next to each question.3. Math Foundations A B C D E
Which of the following is NOT true regarding logarithms?
A) log2(n) = O(log3(n))
B) log3(n) = O(log2(n))
C) log2(n!) = O(n log2(n))
D) log2(n) = Θ(log3(n))
E) All of the above are true
4. Complexity Analysis A B C D E
If f(n) = O(g(n)), and f(n) = Ω(h(n)) and f(n), g(n), and h(n) are strictly increasing functions,
which of the following MUST be true?
A) g(n) = O(h(n))
B) g(n) = Θ(h(n))
C) g(n) = Ω(h(n))
D) g(n) = Θ(f(n))
E) None of the above
Pr
ac
tic
eEECS 281 Practice Midterm Exam · Fall 2021 Uniqname: Page 5 of 20Record your answers in the bubbles next to each question.5. Recursion A B C D E
Consider the following recurrence relation:
T (n) =
{
c0, n = 1
nT (n− 1) + c, n > 1.
What is the complexity of T (n)?
A) Θ(n log n)
B) Θ(n2)
C) Θ(n3)
D) Θ(cn)
E) Θ(n!)
6. Queues A B C D
What is the best possible space complexity for a function printing out the contents of a std::queue of
size n in order, such that the contents and order of the queue are the same before and after the function
is called and executed? This means the auxiliary, or additional, space required to make this occur, not
the space taken up by the data that was in the queue to begin with. You can assume that the queue is
passed by reference.
A) O(1)
B) O(n)
C) O(n2)
D) O(n3)
Pr
ac
tic
ePage 6 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiRecord your answers in the bubbles next to each question.7. Code Analysis A B C D E
NOTE: Same code as next page, different question
Consider an array data of size n which contains 0s and 1s. Each element of this array containing 0
appears before all those elements containing 1. For example, [0, 0, 0, 0, 1] is such an array.
1 int myFunction(int data[], int length) {
2 int mid = 0, left = 0; int right = length – 1;
3 if (data[0] == 1)
4 return 0;
5 else if (data[length – 1] == 0)
6 return length;
7 else {
8 bool isFound = false;
9 while (!isFound) {
10 mid = left + (right – left) / 2;
11 if (data[mid] == 0)
12 left = mid + 1;
13 else {
14 if (data[mid – 1] == 0)
15 isFound = true;
16 else
17 right = mid – 1;
18 } // else
19 } // while
20 return mid;
21 } // else
22 } // myFunction()
In general, what does the function return when it is given such an array?
A) Number of 0’s in data[]
B) Number of 1’s in data[]
C) (Number of 0’s in data[]) + 1
D) (Number of 1’s in data[]) + 1
E) (Number of 1’s in data[]) – 1
Pr
ac
tic
eEECS 281 Practice Midterm Exam · Fall 2021 Uniqname: Page 7 of 20Record your answers in the bubbles next to each question.8. Complexity of Code A B C D E
NOTE: Same code as previous page, different question
Consider an array data of size n which contains 0s and 1s. Each element of this array containing 0
appears before all those elements containing 1. For example, [0, 0, 0, 0, 1] is such an array.
1 int myFunction(int data[], int length) {
2 int mid = 0, left = 0; int right = length – 1;
3 if (data[0] == 1)
4 return 0;
5 else if (data[length – 1] == 0)
6 return length;
7 else {
8 bool isFound = false;
9 while (!isFound) {
10 mid = left + (right – left) / 2;
11 if (data[mid] == 0)
12 left = mid + 1;
13 else {
14 if (data[mid – 1] == 0)
15 isFound = true;
16 else
17 right = mid – 1;
18 } // else
19 } // while
20 return mid;
21 } // else
22 } // myFunction()
What is the complexity of the above algorithm?
A) Θ(1)
B) Θ(log(log n))
C) Θ(log n)
D) Θ(n)
E) Θ(n log n)
Pr
ac
tic
ePage 8 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiRecord your answers in the bubbles next to each question.9. Heaps and Heapsort A B C D E
Which of the following is TRUE about binary heaps and heapsort?
A) Finding the maximum element in a min heap tree has a complexity of Θ(log n)
B) Turning a random set of elements into a heap has a complexity of Θ(log n)
C) If the priority of one element in a heap changes, fixing the heap requires a minimum of Θ(n)
operations
D) The worst-case time complexity of heapsort is Θ(n2)
E) Heapsort can be implemented with O(1) additional space
10. Binary Heaps A B C D
Which of the following represents a valid binary heap?
A)
6
4
52
3
21
B)
5
3
2
1
C)
2
47
9
D)
9
5
4
1
21
Pr
ac
tic
eEECS 281 Practice Midterm Exam · Fall 2021 Uniqname: Page 9 of 20Record your answers in the bubbles next to each question.11. Heaps A B C D E
Suppose that we wanted to add a function popRandom() to our priority queues in Project 2. When
implementing it with the binary heap, we could generate a random index, swap values between that index
and the last element of the data vector, and call the vector’s pop_back() function. What else would
we have to do to preserve the binary heap property? Choose the answer with the smallest worst-case
complexity.
A) Call update_priorities().
B) Call fixDown() followed by fixUp(), both on the random index.
C) Call fixDown(), starting at the root of the heap.
D) Call fixUp(), starting at the last element of the heap.
E) Call exactly one of fixUp() or fixDown(), depending on the values swapped.
12. Reversing an Array A B C D
You are asked to reverse the order of an arbitrary array of length n in constant memory. Your code
skeleton looks like:
1 for (…) {
2 std::swap(array[i], array[n – i – 1]);
3 }
What belongs in the for loop header?
A) for (size_t i = 0; i < n; ++i) B) for (size_t i = 0; i < (n / 2); ++i) C) for (size_t i = n; i >= 0; –i)
D) None of the above
Pr
ac
tic
ePage 10 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiRecord your answers in the bubbles next to each question.13. Linked Lists 1 A B C D
Which of the following is a reason that you would use a doubly linked list over a vector?
A) You need random access
B) You need perform binary search on a data set
C) You need to sort a large number of characters
D) You’re given a pointer to an element and need to insert an element right in front of it
14. Linked Lists 2 A B C D
For which operation does a doubly linked list outperform a singly linked list? Assume the worst case,
and that neither version of the linked list contains a tail pointer.
A) Accessing element at random index
B) Appending an element to the end
C) Deleting an element given a pointer to the node that contains the element
D) Swapping two elements that are not next to each other, given pointers to the two nodes
Pr
ac
tic
eEECS 281 Practice Midterm Exam · Fall 2021 Uniqname: Page 11 of 20Record your answers in the bubbles next to each question.15. Array-based Containers A B C D
Suppose we implement a vector with an underlying dynamic array and a special push_back()method.
This push_back() method works normally when the array is not full. When the array fills up, the
push_back() method creates a new dynamic array with space for 100 more elements than the old
array, copies the elements from the old array to the new array, and then deletes the old array. What is the
amortized complexity of this special push_back() operation?
A) O(1)
B) O(log n)
C) O(
√
n)
D) O(n)
16. Container Data Structures A B C D
Which data structure is best for implementing a sorted container that supports binary search?
A) Stack
B) Vector
C) Linked List
D) Binary Heap
Pr
ac
tic
ePage 12 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiRecord your answers in the bubbles next to each question.17. Contiguous Containers A B C D
Which of the following statements about native (C-style) array and std::vector is TRUE?
A) A vector can store references while a native array cannot.
B) It is valid for a function to return a vector declared on its own stack, but invalid to return an array
declared on its own stack
C) Since a vector stores data on the heap, you must always explicitly destroy them using the
delete operator
D) A vector may be multi-dimensional, an array cannot
18. The STL A B C D
Which of the following statements is TRUE?
A) If you define a class with a std::vector member variable, you must define the Big Three (copy
constructor, assignment operator, destructor) for the class because vectors use dynamic memory
B) STL container classes (such as std::vector) may only contain objects, not primitive types
C) To use a std::priority_queue
11 }
Given an array of Student objects of size n (where n is very large), what would be the best possible
worst-case time complexity to sort this array by class standing?
A) Θ(n)
B) Θ(n log n)
C) Θ(n2)
D) Θ(n3)
E) None of the above
24. Elementary Sorts A B
Executing a selection sort algorithm on a singly linked list has an asymptotically worse average-case time
complexity than executing a selection sort on an array with random access.
A) True
B) False
Pr
ac
tic
ePage 16 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiWritten Portion [40 points]
WRITTEN PORTION INSTRUCTIONS:
• There are two questions in this section, with the following point distribution:
Question 25 20 points
Question 26 20 points
• Please write your solution legibly in the space provided. Solutions that are difficult to read may
receive fewer points.
• Use the back of the question page to work out solutions for each problem and then rewrite your
final answer in the space provided.
• The directions for each problem will specify which STL algorithms/functions may be used in your
solution.
• Solutions that exceed the allowed line count will lose one (1) point per line over the limit.
• Partial credit will be awarded for partial solutions.
• Errors in program logic or syntax may result in a reduced score.
• Be sure to consider all possible sources of memory (stack and heap) and time complexity.
Pr
ac
tic
eEECS 281 Practice Midterm Exam · Fall 2021 Uniqname: Page 17 of 2025. Programming: Linear-time Algorithms and the STL [20 Points]Implement STL’s unique_copy() function according to its official interface and description.
template
OutputIterator unique_copy(ForwardIterator first, ForwardIterator last,
OutputIterator result);
Quoting from http://www.sgi.com/tech/stl/unique_copy.html:
unique_copy() copies elements from the range [first, last) to a range beginning
with result, except that in a consecutive group of duplicate elements only the first one is
copied. The return value is the end of the range to which the elements are copied.
Complexity: Linear. For elements in the ranges, exactly last – first applications of
operator==() and at most last – first assignments.
For example, if you executed this code:
int data[6] = {1, 3, 3, 1, 1, 0}, output[6];
unique_copy(data, data + 6, output);
You would have this in array output:
1 3 1 0
Implementation: Use the back of this page as a working area, then rewrite neatly on the front. Limit:
15 lines of code (points deducted if longer). You may NOT use other STL algorithms/functions.
template
OutputIterator unique_copy(ForwardIterator first, ForwardIterator last,
OutputIterator result) {
Pr
ac
tic
ePage 18 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiThis page is intentionally left blank.You may use this page as working space.
Pr
ac
tic
eEECS 281 Practice Midterm Exam · Fall 2021 Uniqname: Page 19 of 2026. Programming: Finding Max Elements [20 Points]Suppose you are given an array of int, size n and a number k. Return the k largest elements Outputdoes not need to be sorted. You can assume that k < n.
Requirements: Your solution must be faster than O(n log n) time. You may use up to O(n) auxiliary
space.
Implementation: Use the back of this page as a working area, then rewrite neatly on the front. Limit:
15 lines of code (points deducted if longer). You may use any C, C++, or STL function/algorithm that
you wish.
vector
Pr
ac
tic
ePage 20 of 20 EECS 281 Practice Midterm Exam · Fall 2021 · Darden, Derezinski, Garcia, PaolettiThis page is intentionally left blank.You may use this page as working space.