代写代考 EECS 281: Data Structures and Algorithms Final Exam Multiple Choice Questio

The University of Michigan Electrical Engineering & Computer Science EECS 281: Data Structures and Algorithms Final Exam Multiple Choice Questions — Additional Practice Solutions —
INSTRUCTIONS: This document contains 120 multiple choice questions and 32 written questions to help you prepare for the final exam. The written questions begin on page 56 (starting with question 121). The multiple choice questions can be roughly broken down into the following categories:
• Questions 1-32: Hash Tables • Questions 33-66: Trees
• Questions 67-82: Graphs

Copyright By PowCoder代写 加微信 powcoder

• Questions 83-110: Algorithm Families
• Questions 111-115: Shortest Path Algorithms • Questions 116-120: Computational Geometry
The written problems are not organized by topic. See page 56 for more details.
1. PropertiesofMaps A B C D E
Which of the following statements is FALSE?
A) The std::map data structure is implemented using a binary search tree under the hood
B) The worst-case time complexity of searching a binary search tree occurs when the nodes are in a stick formation
C) Hash tables are extremely useful because searching for an element always takes Θ(1) time
D) The dictionary ADT can be implemented using a hash table
E) None of the above
2. SettingThingsUp A B C D E Which of the following statements is FALSE?
A) Unlike an std::unordered_set, an std::unordered_map has a value associated with each key
B) An std::unordered_map does not allow for duplicate keys
C) If you want to sort the keys of an std::unordered_map, you can pass its iterators into the
std::sort() function
D) Using operator[] on a nonexistent key in an std::unordered_map causes the key to exist
E) None of the above

Page 2 of 106 EECS 281 Final Exam · Additional Practice Problems
Record your answers in the bubbles next to each question.
3. Random Hashing A B
True or false? The rand() function, which generates random numbers, is great for hashing since it greatly reduces the chances of collision.
A) True B) False
4. Hashing Complexities A B True or false? Both unordered and ordered maps have Θ(1) average search and insert time complexities.
A) True B) False
5. ToHashorNottoHash A B True or false? A hash table is the best data structure to use if you want to keep track of the number of
students who have birthdays on each of the 31 days in January. A) True
6. Horrible Hashing
Which of the following is not a characteristic of a good hash function?
A) The capability to distribute keys evenly in a hash table
B) The capability to keep similar keys close together in a hash table C) The capability to compute a hash for every possible key
D) The capability to compute the same hash for the same key
E) All of the above are characteristics of a good hash function

EECS 281 Final Exam Practice Uniqname: Page 3 of 106
Record your answers in the bubbles next to each question.
7. Compression by Modulo A B C D E
An easy way to compress an integer key into a hash table of size M is to mod it by M (i.e., key mod M ). For which of the following collection of keys is this compression method the most ideal?
A) A list of all scores on a 20-question multiple choice exam, where each question is worth 5 points
B) A collection of “unluckiest numbers” collected in a survey of 500 adults
C) The total number of minutes Dr. P spends with each student during office hours the day a project is due (rounded to the nearest minute)
D) The number of credits each full-time student at the university is taking this semester
E) The collection of student IDs of all students currently enrolled in EECS 281
8. FindingSums A B C D E Given two unsorted arrays of distinct numbers, you want to find all pairs of numbers, one from array 1
and one from array 2, that sum to a given value. For instance, if you are given
arr1[] = {1, 2, 3, 4, 5, 7, 11}
arr2[] = {2, 3, 4, 5, 6, 8, 12}
you would return (1, 8), (3, 6), (4, 5), (5, 4), and (7, 2). What is the average time complexity of doing this if you use the most efficient algorithm?
B) Θ(log(n)) C) Θ(n)
D) Θ(nlog(n)) E) Θ(n2)

Page 4 of 106 EECS 281 Final Exam · Additional Practice Problems
Record your answers in the bubbles next to each question.
9. Symmetric Pairs A B C D E
Two pairs (a, b) and (c, d) are symmetric if b = c and a = d. Suppose you are given an array of pairs, and you want to find all symmetric pairs in the array. The first element of all pairs is distinct. For instance, if you are given the following array
arr1[] = {(14, 23), (11, 2), (52, 83), (49, 38), (38, 49), (2, 11)} you would return {(11, 2), (2, 11)} and {(49, 38), (38, 49)}. What is the average
time complexity of doing this if you use the most efficient algorithm?
B) Θ(log(n)) C) Θ(n)
D) Θ(nlog(n)) E) Θ(n2)
10. Minimum Deletions
You are given an array of n elements where elements may be repeated, and you want to find the minimum number of elements that need to be deleted from the array so that all elements in the array are equal. For instance, if you are given the following array
arr1[] = {3, 6, 8, 6, 2, 7, 6, 3, 1, 3, 6}
you would return 7, as this is the minimum number of deletions required to obtain an array where all elements are the same (in this case, you would get an array with all 6’s). What is the average time complexity of doing this if you use the most efficient algorithm?
B) Θ(log(n)) C) Θ(n)
D) Θ(nlog(n)) E) Θ(n2)

EECS 281 Final Exam Practice Uniqname:
Page 5 of 106
Record your answers in the bubbles next to each question.
Use the code below to answer questions 11-13.
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
7 int main() {
8 unordered_map myMap;
9 myMap.insert(make_pair(“Paoletti”,”Darden”));
10 myMap.insert(make_pair(“Angstadt”,”Darden”));
11 myMap.insert(make_pair(“Paoletti”,”Angstadt”));
12 myMap[“Angstadt”] = “Paoletti”;
13 myMap.insert(make_pair(“Paoletti”, “Garcia”));
14 cout << myMap["Paoletti"] << endl; 15 cout << myMap["Darden"] << endl; 16 myMap.erase("Paoletti"); 17 cout << myMap["Angstadt"] << endl; 18 cout << myMap.size() << endl; 19 } // main() 11. Keeping Track of Professors, Part I What does line 14 print? A) Paoletti B) ) Angstadt E) An empty string 12. Keeping Track of Professors, Part II What does line 17 print? A) Paoletti B) ) Angstadt E) An empty string Page 6 of 106 EECS 281 Final Exam · Additional Practice Problems Record your answers in the bubbles next to each question. Use the code below to answer questions 11-13. 1 #include
2 #include
3 #include
4 #include
5 using namespace std;
7 int main() {
8 unordered_map myMap;
9 myMap.insert(make_pair(“Paoletti”,”Darden”));
10 myMap.insert(make_pair(“Angstadt”,”Darden”));
11 myMap.insert(make_pair(“Paoletti”,”Angstadt”));
12 myMap[“Angstadt”] = “Paoletti”;
13 myMap.insert(make_pair(“Paoletti”, “Garcia”));
14 cout << myMap["Paoletti"] << endl; 15 cout << myMap["Darden"] << endl; 16 myMap.erase("Paoletti"); 17 cout << myMap["Angstadt"] << endl; 18 cout << myMap.size() << endl; 13. Keeping Track of Professors, Part III What does line 18 print? A) 1 B) 2 C) 3 D) 4 E) 7 EECS 281 Final Exam Practice Uniqname: Page 7 of 106 Record your answers in the bubbles next to each question. 14. HighScore,PartI A B C D E The Project 4 autograder just got released! On the first day, eight students submitted. The scores that each of these students received on their first submission are shown in the table below. StudentID 522 883 768 417 130 614 349 265 Score 34.9 56.7 21.4 75.4 61.1 35.7 23.1 45.7 Suppose these students are inserted into a std::map named P4Scores, where StudentIDrepresentsthekeyandScorerepresentsthevalue.Ifit = P4Scores.end(),whatisthe value of (–it)->first?
E) None of the above
15. HighScore,PartII
Suppose you wanted to print out the student ID with the highest score, 417. Which of the following would successfully accomplish this? Select all that apply.
A) Insertingstudent417firstintoastd::unordered_mapnamedP4Scores with Score as the key and Student ID as the value, setting an iterator it to P4Scores.begin(), and printing it->second
B) Insertingstudent417lastintoastd::unordered_mapnamedP4Scores with Score as the key and Student ID as the value, setting an iterator it to P4Scores.end(), and printing (–it)->second
C) Inserting student 417 last into a std::map named P4Scores with Score as the key and Student ID as the value, setting an iterator it to P4Scores.begin(), and printing it->second
D) Inserting student 417 first into a std::map named P4Scores with Score as the key and Student ID as the value, setting an iterator it to P4Scores.end(), and printing (–it)->second
E) Inserting student 417 last into a std::map named P4Scores with Score as the key and Student ID as the value, setting an iterator it to P4Scores.end(), and printing it->second

Page 8 of 106 EECS 281 Final Exam · Additional Practice Problems Record your answers in the bubbles next to each question.
On the Winter 2018 EECS 281 Piazza page, posts can be categorized into three unique groups: questions, notes, and memes. A representation of this is shown below:
16. Mapping Piazza, Part I A B True or false? An enum class can be used to track whether a Piazza post is a question, a note, or a meme.
A) True B) False
17. Mapping Piazza, Part II A B C D E Suppose you implemented the following unordered map that maps the type of each post to the post IDs
that correspond to each of these types (for instance, the key notes maps to [3450,3983,4343]): std::unordered_map> posts;
While searching through Piazza, you discover that post @4753 is a meme. Which of the following successfully appends 4753 to the vector associated with the key memes?
A) posts[“memes”] = 4753;
B) posts[“memes”] = memes.push_back(4753); C) posts[“memes”] = posts.push_back(4753); D) posts[“memes”].push_back(4753);
E) posts[“memes”].second.push_back(4753);

EECS 281 Final Exam Practice Uniqname:
Page 9 of 106
Record your answers in the bubbles next to each question. 18. Mapping Piazza, Part III
True or false? Running the following lines of code would give you an error.
posts.insert(“polls”);
std::cout << posts["polls"] << std::endl; True False For questions 19-22, consider the following code: 1 #include
2 #include
3 #include
4 #include
5 #include