CS计算机代考程序代写 data structure algorithm The University of Michigan

The University of Michigan
Electrical Engineering & Computer Science
EECS 281: Data Structures and Algorithms

Winter 2018

MIDTERM EXAM
Written Portion – ANSWERS
Wednesday February 21, 2018

6:30PM – 8:00PM (90 minutes)

Name: Uniqname:

Student ID:

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 devices are prohibited during the exam.

• Print your name, student ID number, and uniqname LEGIBLY. Sign the Honor Pledge; this
applies to both the written and multiple-choice sections. Your exam will not be graded without
your signature. This must be completed BEFORE TIME IS CALLED.

• 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.

• Turn in both booklets and the Scantron form. We will not accept your exam unless you turn in
all parts. Keep your cheat sheet.

Page 2 of 4 Midterm Exam · Winter 2018

25. Short Answer: Complexity Analysis [8 points total, 4 per blank]

PotatoBot has gotten smarter, and is implementing its own function! It has the initial code started
below. Write each worst-case time complexity for different incomplete expressions (with missing
components designated like 1 ).

void potato(int n) {
for (int i = 1; i < n;¬ ) for (int j = 1;­ ;® ) for (int k = 1;̄ ; k++) cout << "Potato!\n"; } // potato() 1 2 3 4 Complexity i++ j < n j *= 3 k < j Θ(n 2) i *= 2 j < n j++ k < j Θ(n 2 log n) i++ j < i j++ k < n Θ(n3) i *= 2 j < n j *= 2 k < n Θ(n log 2 n) xiaosong Highlight xiaosong Highlight Page 3 of 4 Midterm Exam · Winter 2018 26. Programming: Linear Time Algorithms and the STL [14 points] Implement the STL’s problem_26() function (the name has been changed for this exam) according to its official interface and description, given below. Quoting from http://www.cplusplus.com problem_26()copies elements from the range [first, last) to the range beginning at result, but rotating the order of the elements in such a way that the element pointed to by middle becomes the first element in the resulting range. Complexity: Linear in the distance between first and last: Performs an assignment for each element. For example, if you executed this code: int data[6] = {1, 2, 3, 4, 5, 6}, output[6]; problem_26(data, data+2, data+6, output); You would have this in array output: 3 4 5 6 1 2 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 any STL algorithms/functions. template
OutputIterator problem_26(ForwardIterator first, ForwardIterator middle,

ForwardIterator last, OutputIterator result) {

// One line solution using STL (if allowed to use STL)
// return copy(first, middle, copy(middle, last, result));

// Copy middle to end
for (ForwardIterator mid = middle; mid != last; ++mid, ++result)

*result = *mid;

// Copy beginning to middle
for (; first != middle; ++first, ++result)

*result = *first;

return result;
} // problem_26()

http://www.cplusplus.com

Page 4 of 4 Midterm Exam · Winter 2018

27. Programming: Heap Flattening [18 points]

Given a pointer-based binary heap, flatten it into a singly-linked list. The binary heap passed in (as
a Node *) must be modified directly. DO NOT create or destroy any Nodes. The left child should
appear in the linked list before the right child. An example is shown below:

83

78

4975

66

2019

Each Node is defined as:

struct Node {
int val;
Node *left;
Node *right;

};

Turns into:

83 66 78 19 20 75 49 nullptr

The right pointer within each Node must be used as “next”, the left must be set to nullptr.

Complexity: Θ(n) time, Θ(1) additional space.

Implementation: Use the back of this page as a working area, then rewrite NEATLY on the front.
Limit: 18 lines of code (points deducted if longer). You MAY use anything from the STL.

void linearize(Node *binaryHeap) {

queue myQueue;
myQueue.push(binaryHeap);

while (!myQueue.empty()) {
Node *temp = myQueue.front();
myQueue.pop();
if (temp) {

myQueue.push(temp->left);
myQueue.push(temp->right);
temp->left = nullptr;
temp->right = myQueue.front();

} // if
} // while

} // linearize()

xiaosong
Highlight