代写代考 EECS 281: Data Structures and Algorithms Final Exam Multiple Choice Questio – cscodehelp代写 – INTERVIEW&CODEHELP

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

• 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

6 #include
7 using namespace std;
9 int main() {
10 unordered_map> foods;
11 foods[“cabbage”] = make_pair(“vegetable”, 1);
12 foods[“banana”] = make_pair(“fruit”, 2);
13 foods[“donut”] = make_pair(“dessert”, 3);
14 foods[“apple”] = make_pair(“fruit”, 4);
15 foods[“eggplant”] = make_pair(“vegetable”, 5);
16 vector vec;
17 for (auto x : foods)
18 vec.push_back(x.first);
19 cout << vec.front() << endl; 20 return 0; 19. Categorizing Food, Part I What is the type of x on line 17? B) pair
C) pair
D) pair> E) pair, string>

Page 10 of 106 EECS 281 Final Exam · Additional Practice Problems
Record your answers in the bubbles next to each question. 20. Categorizing Food, Part II
What does line 19 print?
C) cabbage
D) vegetable
E) Impossible to determine
21. Categorizing Food, Part III
Suppose line 10 were replaced with the following line:
map> foods;
What does line 19 print now?
C) cabbage
D) vegetable
E) Impossible to determine
22. Categorizing Food, Part IV
Which of the following lines of code prints out 1? Use the original code without the replacement made in question 21.
A) cout << foods[0] << endl; B) cout << foods["cabbage"] << endl; C) cout << foods["cabbage"].second << endl; D) cout << foods["cabbage"].second.second << endl; E) None of the above EECS 281 Final Exam Practice Uniqname: Page 11 of 106 Record your answers in the bubbles next to each question. 23. Open Addressing Which of the following collision resolution methods is not a form of open addressing? A) Separate Chaining B) Linear Probing C) Quadratic Probing D) Double Hashing E) All of the above use open addressing 24. Maintaining the Load Which of the following statements is FALSE? A) The load factor α of a hash table can exceed 1 B) As α increases, the performance of separate chaining does not deteriorate as quickly as the performances of open addressing methods C) The time complexities of searching and removing are both Θ(α) for a hash table that uses separate chaining to resolve collisions D) If α is less than 0.5, linear probing is better than double hashing at preventing keys in a hash table from clustering together E) More than one of the above 25. Problematic Quadratics A B C D E Which of the following is NOT a disadvantage of using quadratic probing to resolve collisions? A) Two elements that hash to the same position will still have the same probe sequence, regardless of how far they land from their hashed location B) Quadratic probing may insert keys into positions of a hash table that are far from the index that they normally hash to C) Depending on the size of the hash table involved, it is possible for quadratic probing to never consider specific indices while searching for an open position D) The performance of quadratic probing can deteriorate dramatically as the load factor increases E) None of the above Page 12 of 106 EECS 281 Final Exam · Additional Practice Problems Record your answers in the bubbles next to each question. 26. LoadFactor A B C D E A hash table of size 100 has 40 empty elements and 25 deleted elements. What is its load factor? A) 0.25 B) 0.35 C) 0.60 D) 0.65 E) 0.75 27. Linear Probing Suppose you have a hash table of size M = 10 that uses the hash function H(n) = 3n + 7 and the compression function C(n) = n mod M. Linear probing is used to resolve collisions. You enter the followingnineelementsintothishashtableinthefollowingorder:{10, 8, 18, 17, 4, 20, 6, 3, 16}. No resizing is done. After all collisions are resolved, which index of the hash table remains empty? E) None of the above 28. Quadratic Probing Suppose you have a hash table of size M = 7 that uses the hash function H(n) = n and the compression function C(n) = n mod M. Quadratic probing is used to resolve collisions. You enter the following six elements into this hash table in the following order: {24, 11, 17, 21, 10, 4}. No resizing is done. After all collisions are resolved, which index of the hash table remains empty? E) None of the above EECS 281 Final Exam Practice Uniqname: Page 13 of 106 Record your answers in the bubbles next to each question. 29. TrackingtheHash A B C D E A hash table of size 10 uses open addressing with a hash function H(k) = k, compression function C(k) = k mod 10, and linear probing. After entering six values into an empty hash table, the state of the table is as shown below. Which of the following insertion orders is possible? 0123456789 62 43 24 82 76 53 A) 76, 62, 24, 82, 43, 53 B) 24, 62, 43, 82, 53, 76 C) 76, 24, 62, 43, 82, 53 D) 62, 76, 53, 43, 24, 82 E) None of the above 30. Who’s Teaching Class? Suppose you are using a hash function where each string is hashed to an integer representing its first letter. The integer each letter hashes to is shown in the table below: abcdefghijklmn 0 1 2 3 4 5 6 7 8 9 10 11 12 13 opqrstuvwxyz 14 15 16 17 18 19 20 21 22 23 24 25 The compression function C(x) = x mod M is used, where M represents the size of the hash table. You are using a hash table of size M. If the strings "paoletti" and "darden" collide in this hash table, which of the following is not a possible value of M ? E) None of the above Page 14 of 106 EECS 281 Final Exam · Additional Practice Problems Record your answers in the bubbles next to each question. 31. When Planets Collide A B C D E Suppose you are using a hash function where each string is hashed to an integer representing its first letter. The integer each letter hashes to is shown in the table below: abcdefghijklmn 0 1 2 3 4 5 6 7 8 9 10 11 12 13 opqrstuvwxyz 14 15 16 17 18 19 20 21 22 23 24 25 You have a hash table of size 10, and you insert the planets of the solar system (with the sun) into this hash table in the following order: 2. "mercury" 3. "venus" 4. "earth" 6. "jupiter" 7. "saturn" 8. "uranus" 9. "neptune" Collisions are resolved using the double hashing formula t(key) + i × (q − (t(key) mod q)) where t(key) is the integer that a key hashes to, i is the number of collisions that have occurred so far with that key, and q is 7. Compression is done using the formula C(n) = n mod M, where M is 10 (the size of the hash table). No resizing is done. After all collisions are resolved, which index of the hash table remains empty? E) None of the above EECS 281 Final Exam Practice Uniqname: Page 15 of 106 Record your answers in the bubbles next to each question. 32. Grocery Shopping A B C D E Suppose you have a hash table of size M = 13 that uses the same hash function as mentioned previously. You enter the following foods as keys into this hash table in the following order: 1. "apples" 2. "almonds" 3. "avocados" 4. "asparagus" Collisions are resolved using the double hashing formula: t(key) + i × (q − (t(key) mod q)) After all collisions are resolved, you notice that the key "asparagus" ended up at index 7. Knowing this, what is a possible value of q? A) 3 B) 5 C) 7 D) 9 E) 11 33. Binary Tree Arrays What is the worst-case memory complexity of implementing a binary tree using an array? A) Θ(log(n)) B) Θ(n) C) Θ(nlog(n)) D) Θ(n2) Page 16 of 106 EECS 281 Final Exam · Additional Practice Problems Record your answers in the bubbles next to each question. 34. Tree Terminology Consider the following tree below: Which of the following nodes is NOT an internal node? E) All of the above are internal nodes 35. WastedSpace If you used an array to represent a binary tree, where the root is at index 1 and the left and right children of the node at index n are 2n and 2n + 1 respectively, which of the following indices would be filled in the case of a rightward-facing stick (i.e., a stick where nodes only have right children)? A) 2 B) 17 C) 31 D) 49 E) 64 EECS 281 Final Exam Practice Uniqname: Page 17 of 106 Record your answers in the bubbles next to each question. 36. Binary Search Sticks A B C D E Suppose that you want to insert 12 distinct elements into a binary search tree. How many worst-case trees are possible for these 12 elements? B) 2,047 (211 − 1) C) 2,048 (211 ) D) 4,095 (212 − 1) E) 4,096 (212 ) 37. Worst-Case Trees For which of the following element insertion orders is the resulting binary search tree a worst-case tree? A) 51, 13, 38, 41, 49, 46, 47, 22, 53, 8 B) 53, 8, 51, 13, 22, 49, 47, 38, 41, 46 C) 51, 53, 8, 46, 49, 38, 41, 13, 47, 22 D) 8, 13, 46, 41, 47, 53, 51, 38, 22, 49 E) None of the above 38. BarkingUptheWrongTree Which of the following statements is TRUE? A) The inorder successor of the root node can have two children B) The array-based binary tree implementation is most efficient for trees that have fewer nodes C) The worst-case time complexity of inserting an element into a pointer-based binary tree is better than the worst-case time complexity of inserting a 程序代写 CS代考加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com

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

Published by admin

Leave a Reply Cancel reply