CMSY10
The University of Michigan
Electrical Engineering & Computer Science
EECS 281: Data Structures and Algorithms
Winter 2016
MIDTERM EXAM, PRACTICE
Multiple-Choice Portion, KEY 1
Wednesday February 24, 2016
8:30PM – 10:00PM (90 minutes)
INSTRUCTIONS:
• 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 15 multiple-choice questions worth 4 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 only
one correct answer to each question. 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, and nothing written inside of it will be
graded.
• Turn in the written portion exam book and the Scantron answer form. One will not be accepted
without the other.
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 2 of 8 Midterm Exam · Winter 2016
Record your answers to this page on the Scantron sheet
1. Asymptotic complexity
Find one statement that is false.
A log
3
(N) = O(log
2
(N))
B log
2
(N3) = O(log
2
(N2))
C log
2
(3N) = O(log
2
(2N))
D 3N = O(2N)
E 23N = O(22N)
For A-C, use properties of log-functions.
For D, use the property of Big-O notation (dropping constants).
For E, show that limN→∞ 8
N/4N = ∞.
2. Algorithms for linked lists
Consider two singly-linked lists implemented without classes. You are given non-const pointers to
the head and the tail elements (four pointers total). The last element of each list can have its .next
pointer uninitialized and later overwritten. During all operations the head and tail pointers must
remain valid.
Which statement below is false?
A Copying a singly-linked list to a doubly-linked list takes Θ(N) time.
B The first element of each linked list can be deleted in O(1) time.
C The last element of each linked list can be deleted in O(1) time.
D The merger(concatenation) of the two linked lists can be created in O(1) time.
E Reversing a singly-linked list in place can be performed in O(N) time.
In a linked list, deleting an element typically requires knowing its previous element.
Since our list is singly-linked, it would take linear time to find the second last element.
Note that when deleting the last element, the copying trick discussed in class won’t work.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 3 of 8 Midterm Exam · Winter 2016
Record your answers to this page on the Scantron sheet
3. Program analysis
(Please read the description entirely before proceeding further.)
Consider the following piece of code.
int pickOne(vector
// rand() produces a different unsigned every time it is called
return v[rand() % v.size()]; // rand() and v.size() take O(1) time
}
vector
vector
for (unsigned k = 0; k != v.size(); ++k)
newVec[k] = pickOne(v);
return newVec;
}
Assume that the claims in the comments are correct. Which one of the following is a correct and
tight bound on the asymptotic runtime of function myRandomSample() including all calls to
pickOne()?
A O(N2)
B Θ(N)
C Ω(N)
D Θ(N logN)
E O(NN)
Note: we are not using move semantics from C++11 (so you don’t need to know what it is)
OPTIONAL: improve the asymtotic complexity of this code in two different ways —
(a) by adding one character,
(b) by adding one C++ keyword.
Each call to pickOne() involves copying a vector, which takes linear time. This can be improved
by passing the vector by reference in pickOne() (add an & after vector
the function (add inline before int pickOne and compile with -O3).
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 4 of 8 Midterm Exam · Winter 2016
Record your answers to this page on the Scantron sheet
4. Linear-time algorithms with sorted ranges
The following function claims to compute set-union of two sorted ranges in linear time.
template
OutputIterator set_what(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2) {
if (*first1 < *first2)
++first1;
else if (*first2 < *first1)
++first2;
else {
*result++ = *first1++;
++first2;
} // else
} // while
return result;
}
Which of the following best describes its actual performance?
A It computes what it claims, but may take longer than linear time.
B Iterators may go out of range on some inputs, and the function may crash.
C It computes set-difference.
D It computes set-intersection in linear time.
E None of the above.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 5 of 8 Midterm Exam · Winter 2016
Record your answers to this page on the Scantron sheet
5. The Standard Template Library: containers and iterators
STL iterators are used with container classes and are conceptually similar to pointers to specific
elements stored in the container.
One of the statements below is true. Which one?
A An iterator typically holds an address (pointer), and operator++ applied to the iterator always
increases that address.
B When iterator it goes out of scope in a program, it gets destructed, which automatically invokes
delete it;.
C For a valid STL container myC, when the expression myC.end() - myC.begin() is well-
defined, it returns the same value as myC.size().
D When a container goes out of scope, all iterators that point to it are automatically modified.
E For a valid STL container myC, the iterator returned by myC.end() refers to the last valid
element in myC.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 6 of 8 Midterm Exam · Winter 2016
Record your answers to this page on the Scantron sheet
6. Memory allocation & ownership, and container data structures
Recall that the concept of memory ownership is used to prevent memory leaks
(memory that has not been deallocated but is not pointed to) and crashes due to double delete calls.
Which of the following statements is false?
A This piece of C++ code may lead to a crash or memory corruption:
int *p, *r; p = r = new int; delete p; delete r;
B If a member of a class is a pointer that owns memory, then the destructor of that class must
always use the delete[] operator on that pointer.
C If a pointer or an iterator is the only legal way to access a chunk of memory,
then it must be the direct owner of that chunk of memory.
D If a member of a class is a pointer that owns memory, then the copy-constructor
of the class must invoke operator new in some way.
E Memory allocated with new int[10] must be deallocated with delete[].
B is false because sometimes one must use a different operator — delete without brackets.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 7 of 8 Midterm Exam · Winter 2016
Record your answers to this page on the Scantron sheet
7. 2D Maze Search
Consider a space station that has a single level (consisting of walls, floors, and exits), the level has
dimensions are N ×M , and it has multiple (E > 1) exits. Your robot friend is to be programmed to
count the exits reachable from your current location and it should use the fastest algorithm available.
Which one of the asymptotic worst-case complexity bounds below is both correct and tight?
A O(N +M)
B O(NM)
C O(ENM)
D O(ENM)
E O(NEME)
Use either a queue-based or stack-based algorithm to search the entire maze (in the worst-case) and
record the number of exits seen.
8. Binary search
Consider an array of N C++ strings, each string with exactly M characters. No additional information
is available about individual strings, but the array lists strings in a dictionary order (lexicographically
increasing). We wish to find one particular string without building additional data structures. Which
expression below represents most accurately the complexity of binary search on such an array?
A O(logN)
B O(logM)
C O(M logN)
D O(N logM)
E O(logM + logN)
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 8 of 8 Midterm Exam · Winter 2016
Record your answers to this page on the Scantron sheet
9. Algorithm design
Consider struct Segment {double xMin, xMax;}; and a vector
task is to determine if any two segments in the input vector intersect (allowed operators for doubles
are assignment, comparisons and copy-construction). Assuming a fastest possible algorithm, what
will its worst-case asymptotic complexity be in terms of N = vector
A N
B N log(N)
C N(log(N))2
D N2
E N2 log(N)
CLARIFICATION : If an algorithm finds two intersecting segments, it can report “some segments
intersect” and stop.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099