The University of Michigan Electrical Engineering & Computer Science EECS 281: Data Structures and Algorithms Fall 2021
FINAL EXAM
Wednesday, December 15, 2021 8:00AM (140 minutes)
Uniqname: Student ID: Name:
Copyright By PowCoder代写 加微信 powcoder
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:
• Theexamisclosedbookandnotesexceptforone8.5″x11″sheetofhandwrittennotes(bothsides). All electronic device use is prohibited during the exam (calculators, phones, laptops, etc.).
• Printyourname,studentIDnumber,anduniqnameLEGIBLY.SigntheHonorPledge;thispledge 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 22 pages in this book; if you are missing any pages, please let an instructor know.
Page 2 of 22 EECS 281 Final Practice Exam 2 · Fall 2021 · Darden, Derezinski, Garcia, Paoletti Multiple 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).
EECS 281 Final Practice Exam 2 · Fall 2021 Uniqname: Page 3 of 22
Record your answers in the bubbles next to each question.
1. Hashing FUN-ctions A B C D E
Which of the following statements is/are TRUE about a hash table that uses open addressing?
I. A hash function could map multiple keys to the same integer value
II. Theaveragenumberofprobestofindanelementinthehashtablemaychangewhentheloadfactor increases
III. Somekeysmayrehashtothesamebucketwhenthesizeofahashtable’sunderlyingarrayincreases
B) I and II only
C) I and III only
D) I, II, and III
E) None of the above
2. ChooseWisely
Which of the following methods has the best time complexity for optimally solving the fractional Knapsack problem?
A) Brute Force
C) Dynamic Programming with a 1-dimensional memo D) Dynamic Programming with a 2-dimensional memo E) Branch and Bound
3. MSTsonaPlane
Let G = (V, E) be a sparse, simple, connected graph containing EXACTLY one cycle with C vertices. If you are given the sum of all edge weights in G and a sorted array of the edge weights in the cycle, what is the best possible time complexity of calculating the total weight of the minimum spanning tree of G?
Page 4 of 22 EECS 281 Final Practice Exam 2 · Fall 2021 · Darden, Derezinski, Garcia, Paoletti
C) Θ(min(C,E−C)) D) Θ(E log(C))
E) Θ(E log(E))
EECS 281 Final Practice Exam 2 · Fall 2021 Uniqname: Page 5 of 22
Record your answers in the bubbles next to each question.
4. NameThatProbe! A B C D E
Consider the following hashing function and hash table. If the contents of the hash table were produced by inserting Elk, Ant, It, Is, Elf, and Elm in this order (with no other operations), which collision resolution method does the hash table use? Hint: ‘A’ words hash to 0, ‘E’ words hash to 4, and ‘I’ words hash to 8.
1 2 3 4 5 6
int hash_1(string s) { if (s.empty())
return 0; else
return s.front() – ‘A’; } // hash_1()
A) Linear probing (i.e., (hash_1(s) + i) mod 10)
B) Quadratic probing (i.e., (hash_1(s) + i2) mod 10) C) Cubic probing (i.e., (hash_1(s) + i3) mod 10)
D) Separate chaining
E) None of the above
5. The Truth About Knapsacks
Which of the following claims about solving the 0-1 Knapsack problem is TRUE?
0123456789
A) The brute force solution for solving the 0-1 Knapsack problem has a lower space complexity than the top-down dynamic programming solution
B) The best runtime complexity of a greedy approximation is Θ(MN2), where M is the capacity of the knapsack, and N is the number of available items
C) Branchandboundisnotapplicabletosolvingthe0-1Knapsackproblembecausethereisnoknown approximation that underestimates total value for use in pruning
D) Thereisnobottom-updynamicprogrammingsolutionforthe0-1Knapsackproblembecausethere are no overlapping subproblems
E) Divide and conquer can be used to optimally solve the 0-1 Knapsack problem in worst-case O(N log N ) time, where N is the number of available items
Page 6 of 22 EECS 281 Final Practice Exam 2 · Fall 2021 · Darden, Derezinski, Garcia, Paoletti
Record your answers in the bubbles next to each question.
6. HashtotheRescue A B C D E
For which of the following tasks would the use of a hash-based container (e.g., unordered_map or unordered_set) improve the average-case asymptotic runtime complexity (compared to using a container that does not employ hashing)? You may assume that only STL-provided containers are used.
A) Counting how many times each lower-case letter appears in a newspaper article B) Finding the kth smallest item in a vector
C) Printing out the first word that appears twice in a text file
D) Printing out all words greater than “apple” and less than “grape” in a document E) More than one of the above
7. BST Construction Zone
Which of the following statements about constructing a binary search tree is FALSE?
A) Given a sorted range of n elements, the optimal algorithm can construct a binary search tree in Θ(n) time
B) Inserting n elements in sorted order would require Θ(2n) space if the binary search tree is implemented using a vector
C) Given a sequence of n elements, randomizing the insertion order of these elements will guarantee that the maximum depth of the resulting BST is strictly less than n
D) If n elements are inserted in sorted order into a pointer-based binary search tree, then the total time complexity of deleting all of the elements in the order of insertion is Θ(n)
E) Givenasequenceofndistinctelements,itispossibleformultipleinsertionordersoftheseelements to produce the same binary search tree
8. Backtracking A B C D E For which of the following problems is backtracking most applicable?
A) Finding the shortest path between two vertices in a graph
B) Finding a solution to a puzzle where all rows and columns must be filled with unique numbers,
given some starting subset of cells with fixed values
C) Finding a given element of a recursively defined integer sequence
EECS 281 Final Practice Exam 2 · Fall 2021 Uniqname: Page 7 of 22 D) Finding the combination of indivisible items with given values and weights that maximizes total
value within a certain weight capacity
E) Finding the fewest number of coins that can be dispensed for a given amount of change
Page 8 of 22 EECS 281 Final Practice Exam 2 · Fall 2021 · Darden, Derezinski, Garcia, Paoletti
Record your answers in the bubbles next to each question.
9. Ultrasuperdynamic Programming A B C D E
Solutions A and B show valid functions that compute the nth Fibonacci number (starting with the 0th number in the sequence: 0, 1, 1, 2, 3, 5, 8. . .). Which of the following statements is TRUE?
1 2 3 4 5 6 7 8 9
10 11 12 13
Solution A
int fibonacci_A(int n) { if(n<=1)
Solution B
1 int helper(int n,
2 vector
3 if(n<=1)
4 return n;
5 else if (table[n] != 0)
6 return table[n];
8 table[n] = helper(n - 1, table) 9 + helper(n - 2, table);
// fibonacci_A()
13 int fibonacci_B(int n) {
14 vector
int last1 = 0;
int last2 = 1; for(inti=0;i
return false; else
return helper(root->left, lower, root->value) && helper(root->right, root->value, upper);
} // helper()
bool mystery_function(TreeNode* root) { return helper(root, INT_MIN, INT_MAX);
} // mystery_function()
If given the root node of a tree, what does mystery_function() do?
A) The function returns true if and only if all values in the tree are between INT_MIN and INT_MAX
B) The function returns true if and only if all left children in the tree have values that are one less than the value of their parent
C) The function returns true if and only if the tree is balanced
D) The function returns true if and only if there are no duplicate values in the tree
E) The function returns true if and only if the tree is a valid binary search tree
EECS 281 Final Practice Exam 2 · Fall 2021 Uniqname: Page 17 of 22 Written Portion [40 points]
WRITTEN PORTION INSTRUCTIONS:
• Please write your code 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.
Page 18 of 22 EECS 281 Final Practice Exam 2 · Fall 2021 · Darden, Derezinski, Garcia, Paoletti
This page is intentionally left blank. You may use this page as working space.
EECS 281 Final Practice Exam 2 · Fall 2021 Uniqname: Page 19 of 22 25. Dynamic Programming: Zero-Sum Game [18 Points]
Write a function that, given a vector of integers, returns true if the vector contains a contiguous subsequence that sums to 0 and false otherwise. Note that your function should return false for an empty vector.
For example, if vector
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com