CS 111 Operating Systems Final Exam
Instructions
The exam window is from Friday, June 11 at 8:00 AM to Saturday, June 12 at 7:59 AM (all times are in San Diego time). From the moment you begin the exam, you will have 180 minutes to complete it. However, Saturday, June 12 at 7:59 AM San Diego time is a hard deadline, so be sure to start as early as possible.
No collaboration whatsoever during the exam! The exam is open book, open internet, and open notes, but no Chegg or any similar services! If you are caught cheating on the exam, you will receive an F in the course.
Copyright By PowCoder代写 加微信 powcoder
For each of the exam problems, you have to click the “Submit” button to submit your response, and you have unlimited attempts without penalty. However, you will not know if your answer is correct! Ed will tell you whether or not you have submitted, but we will grade the correctness of your responses after the exam. Each of the 80 total problems on the exam is worth exactly 1 point. There is no global “Submit” button: as long as you’ve clicked the “Submit” button for each individual question, your answers are submitted.
For the sake of fairness for all students, including those who take the exam earlier in the window, you will not be able to ask any questions! Instead, after you �nish the exam, you can mention any questions that you felt were ambiguous via the following Google Form:
https://forms.gle/ZZ1c2eiYNaMRPepi9
Then, after the exam, we will review the responses to this question to determine if we need to adjust the grading in any way. Please open the form now so you don’t lose access to it if you run out of time on the exam.
Week 1: C++ Review
This section has 5 questions (below). You may need to scroll down to see them.
Report ambiguous questions: https://forms.gle/ZZ1c2eiYNaMRPepi9 Question 1 Submitted Jun 1st 2021 at 1:15:33 pm
Problem 1.1: What will be printed by this program?
int main() { int x = 3; int y = 7;
int* z = &y; (*z) = (*z) + y;
y = y + x;
cout << y; }
Question 2 Submitted Jun 1st 2021 at 1:15:37 pm
Problem 1.2: True/False: The code snippet in Problem 1.1 will result in a memory leak.
True False
Question 3 Submitted Jun 1st 2021 at 1:15:41 pm
Problem 1.3: In the code snippet in Problem 1.1, which of the following will be stored in the Heap?
Select all that apply.
The object z points to None of the above
Question 4 Submitted Jun 1st 2021 at 1:15:48 pm
Problem 1.4: What is the tightest worst-case Big-O time complexity of the following code snippet?
for(int i = 1; i < n; i *= 2) {
cout << "i: for(int j =
for(int k = cout <<
" << i << endl;
1; j < n/2; ++j) {
"i + j: " << (i+j) << endl; 1; k < n; k *= 2) {
"i + k: " << (i+k) << endl;
O(log n) O(n)
O(n log n) O(n2)
None of the above
Question 5 Submitted Jun 1st 2021 at 1:15:58 pm
Problem 1.5: What is the tightest worst-case Big-O time complexity of the following code snippet, which utilizes the C++ STL's list class (which is implemented as a Doubly Linked List) and max_element function (which iterates over the elements in the given range and returns the
maximum value)?
int main() {
list
for(int i = 1; i <= n/2; ++i) {
my_list.push_back(i); }
for(int i = n/2 + 1; i <= n; ++i) { my_list.push_front(i);
while(!my_list.empty()) {
auto curr = max_element(my_list.begin(), my_list.end()); cout << *curr << endl;
my_list.erase(curr);
return 0; }
O(log n) O(n)
O(n log n) O(n2)
O(n2 log n) O(n3)
None of the above
Week 2: Trees and BSTs
This section has 7 questions (below). You may need to scroll down to see them.
Report ambiguous questions: https://forms.gle/ZZ1c2eiYNaMRPepi9 Question 1 Submitted Jun 7th 2021 at 1:41:56 pm
Problem 2.1: You are given a BinaryTree class consisting of Node objects that are de�ned as follows:
class Node { public:
Node* left_child; Node* right_child; char symbol;
You are writing a recursive function to print the symbols of all of the Node objects via a post-order
traversal in which you recurse down the left child before recursing down the right child:
void print_postorder(Node* & curr) { // YOUR CODE HERE
Rearrange the following lines of code such that they would implement the function correctly.
Note: You will need to use all of the lines of code.
Drag from here Drop blocks here
if(curr == nullptr) {
print_postorder(curr->left_child);
print_postorder(curr->right_child);
cout << curr->symbol << endl;
Question 2 Submitted Jun 1st 2021 at 1:31:36 pm
Problem 2.2: Which of the following are valid Binary Search Trees? Select all that apply.
None of the above
Question 3 Submitted Jun 1st 2021 at 1:31:40 pm
Problem 2.3: True/False: The right-most node in a Binary Search Tree does not have a successor.
Note: The "right-most node" is the node you reach by starting at the root and traversing down right-child pointers as far as possible.
True False
Question 4 Submitted Jun 1st 2021 at 1:31:44 pm
Problem 2.4: True/False: In a Binary Search Tree, if node x and node y are both children of node z, it
is impossible for y to be the successor of x. True
Question 5 Submitted Jun 1st 2021 at 1:33:20 pm
Problem 2.5: You are given the following Binary Search Tree:
You attempt to �nd the successor of node H using the successor algorithm discussed in this course. Which nodes will you visit, and in what order?
Note: Include both H and its successor in your answer.
Note: Order them such that the top item in your answer is the �rst node to be visited and the bottom item in your answer is the last node to be visited.
Note: You will not necessarily include all elements in your answer.
Drag from here
T X G L E A C
Question 6
Problem 2.6: You are given the following Binary Search Tree:
Drop blocks here
Submitted Jun 5th 2021 at 7:18:51 am
You attempt to �nd the successor of node L using the successor algorithm discussed in this course. Which nodes will you visit, and in what order?
Note: Include both L and its successor in your answer.
Note: Order them such that the top item in your answer is the �rst node to be visited and the bottom item in your answer is the last node to be visited.
Note: You will not necessarily include all elements in your answer.
Drag from here
Drop blocks here
H A G X C J E T
Question 7
Submitted Jun 5th 2021 at 7:33:55 am
Problem 2.7: You are given the following Binary Search Tree:
After removing node M using the remove algorithm discussed in this course, what is the output of a level-order traversal of the resulting tree?
Note: Order them such that the top item in your answer is the �rst node to be visited and the bottom item in your answer is the last node to be visited.
H E T A G K X C J L
Week 3: Self-Balancing BSTs
This section has 10 questions (below). You may need to scroll down to see them.
Report ambiguous questions: https://forms.gle/ZZ1c2eiYNaMRPepi9 Question 1 Submitted Jun 5th 2021 at 10:15:41 am
Problem 3.1: True/False: In practice, we expect the height of a Red- to be less than the height of an AVL Tree containing the same elements.
True False
Question 2 Submitted Jun 5th 2021 at 10:15:47 am
Problem 3.2: True/False: In practice, we expect the height of a Red- to be less than the
height of a Randomized Search Tree containing the same elements. True
Question 3 Submitted Jun 5th 2021 at 10:16:01 am
Problem 3.3: True/False: The tightest worst-case Big-O time complexity to insert an element into a regular (non-self-balancing) Binary Search Tree is larger than the tightest worst-case Big-O time complexity to insert an element into a Randomized Search Tree.
Example: O(n) would be "larger" than O(1).
True False
Question 4 Submitted Jun 5th 2021 at 10:16:24 am
Problem 3.4: What is the minimum possible number of black nodes in a Red- with 7 nodes?
Note: Don't worry about whether or not there exists an insertion order to produce such a tree. Assume you can design the tree as you wish, as long as it's a valid Red- .
Question 5 Submitted Jun 5th 2021 at 10:16:28 am
Problem 3.5: What is the maximum possible number of black nodes in a Red- with 9
Note: Don't worry about whether or not there exists an insertion order to produce such a tree. Assume you can design the tree as you wish, as long as it's a valid Red- .
Question 6 Submitted Jun 5th 2021 at 10:16:37 am
Problem 3.6: What is the maximum possible height of an AVL Tree with 8 nodes?
Note: De�ne the height of a tree to be the number of edges in the longest path from the root to a leaf.
Note: Don't worry about whether or not there exists an insertion order to produce such a tree. Assume you can design the tree as you wish, as long as it's a valid AVL Tree.
Question 7 Submitted Jun 5th 2021 at 10:17:17 am Problem 3.7: You are given the following AVL Tree:
After inserting P, what is the output of a level-order traversal of the resulting tree?
Note: Order them such that the top item in your answer is the �rst node to be visited and the bottom item
in your answer is the last node to be visited.
Submitted Jun 5th 2021 at 10:19:00 am
Question 8
Problem 3.8: You are given the following AVL Tree:
After inserting D, what is the output of a level-order traversal of the resulting tree?
Note: Order them such that the top item in your answer is the �rst node to be visited and the bottom item in your answer is the last node to be visited.
J E M C G K T A D X
Question 9
Problem 3.9: You are given the following Red- :
After inserting 2, what is the output of a level-order traversal of the resulting tree?
Note: Order them such that the top item in your answer is the �rst node to be visited and the bottom item in your answer is the last node to be visited.
Submitted Jun 5th 2021 at 10:20:34 am
Question 10
Problem 3.10: You are given the following Red- :
After inserting 4, how many nodes will be recolored during the insertion algorithm? 3
Submitted Jun 5th 2021 at 10:20:38 am
Week 4: Lexicons
This section has 10 questions (below). You may need to scroll down to see them.
Report ambiguous questions: https://forms.gle/ZZ1c2eiYNaMRPepi9 Question 1 Submitted Jun 5th 2021 at 11:11:05 am
Problem 4.1: True/False: After inserting n unique words, each of length k and each beginning with a di�erent letter, into both a and a Ternary Search Tree (both initially empty), the number of nodes in the resulting is larger than the number of nodes in the resulting Ternary Search Tree.
Note: Unique words can share letters, but the overall words must be di�erent.
True False
Question 2 Submitted Jun 5th 2021 at 11:11:11 am
Problem 4.2: True/False: After inserting words into a that was initially empty,
assuming you never remove any words, all word nodes in the will be leaves. True
Question 3 Submitted Jun 5th 2021 at 11:11:27 am
Problem 4.3: You insert the following words, in this exact order, into a that is initially
CLASSES COMMUTER COMPANY COMPUTER LAST
How many nodes are in the resulting ?
Question 4 Submitted Jun 7th 2021 at 1:45:50 pm
Problem 4.4: You are given the following Ternary Search Tree:
Which of the following words exist in the Ternary Search Tree? Select all that apply. CAR
CARB CARBD CARD CARDB CARDRY
CARE CARRY CARRT CART
Question 5 Submitted Jun 5th 2021 at 11:11:54 am
Problem 4.5: You are given the following Ternary Search Tree:
How many new nodes would be created if you were to insert the word CHART ? 4
Question 6 Submitted Jun 5th 2021 at 11:12:19 am
Problem 4.6: You are given the following Ternary Search Tree:
Assuming no words have ever been removed (i.e., the Ternary Search Tree was created only using insert operations), which of the following statements are true? Select all that apply.
TOAST must have been inserted before MAP CLAW must have been inserted before CLAWS CATS must have been inserted before CLASS CLASS must have been inserted before MAP
None of the above
Question 7 Submitted Jun 5th 2021 at 11:12:35 am
Problem 4.7: You are given the following Ternary Search Tree:
Assuming no words have ever been removed (i.e., the Ternary Search Tree was created only using insert operations), which of the following statements are true? Select all that apply.
WORD must have been inserted before WATT WORDS must have been inserted before WORST WORD must have been inserted before TON ZOO must have been inserted before TON
None of the above
Question 8 Submitted Jun 5th 2021 at 11:12:46 am
Problem 4.8: What is the minimum possible number of nodes in a containing 7 unique
words of length 5?
Note: Unique words can share letters, but the overall words must be di�erent.
Question 9 Submitted Jun 5th 2021 at 11:12:48 am
Problem 4.9: Assuming no remove operations have ever been performed, what is the maximum
possible height of a containing 7 words of length 5?
Note: De�ne the height of a tree to be the number of edges in the longest path from the root to a leaf.
Question 10 Submitted Jun 5th 2021 at 11:12:51 am
Problem 4.10: Assuming no remove operations have ever been performed, what is the maximum
possible height of a Ternary Search Tree containing 7 words of length 5?
Note: De�ne the height of a tree to be the number of edges in the longest path from the root to a leaf.
Week 5: Hashing Data Structures
This section has 10 questions (below). You may need to scroll down to see them.
Report ambiguous questions: https://forms.gle/ZZ1c2eiYNaMRPepi9 Question 1 Submitted Jun 5th 2021 at 2:23:17 pm
Problem 5.1: You are given a hash table with the following backing array, where ? denotes that a given cell contains an element (regardless of what that element actually is):
0123456789 ????
What is the probability of having at least 1 collision within the next 3 insertions using linear probing as the collision resolution strategy?
Enter your answer as a decimal rounded to 3 decimal places. For example, if you believe the answer is 12.35% , enter your answer as 0.124 .
Note: Any �lled slots encountered during the probing step of linear probing do not count as collisions: only the initial "hashed to an already-�lled slot" event.
Question 2 Submitted Jun 5th 2021 at 2:23:19 pm
Problem 5.2: You are given a hash table with the following backing array, where ? denotes that a
given cell contains an element (regardless of what that element actually is):
0123456789 ????
What is the probability of having at least 1 collision within the next 3 insertions using separate chaining as the collision resolution strategy?
Enter your answer as a decimal rounded to 3 decimal places. For example, if you believe the answer is 12.35% , enter your answer as 0.124 .
Question 3 Submitted Jun 5th 2021 at 2:23:34 pm
Problem 5.3: You are given a hash table with the following backing array, where ? denotes that a
given cell contains an element (regardless of what that element actually is):
0123456789 ????
Using a hash function of h(x) = 4x+3, and using linear probing as the collision resolution strategy, if you try to insert the element 5, which index of the backing array will it insert into?
Question 4 Submitted Jun 5th 2021 at 2:23:56 pm
Problem 5.4: You are given a hash table with the following backing array, where ? denotes that a
given cell contains an element (regardless of what that element actually is):
0123456789 ????
Using a hash function of h(x) = 4x+3, and using separate chaining as the collision resolution strategy, if you try to insert the element 5, which index of the backing array will it insert into?
Question 5 Submitted Jun 5th 2021 at 2:24:06 pm
Problem 5.5: True/False: Given a hash table with a backing array of length 10, if you were to use the
hash function h(x) = 4x, some of the indices of the backing array will never be �lled. True
Question 6 Submitted Jun 5th 2021 at 2:24:16 pm
Problem 5.6: Which of the following are valid hash functions? Select all that apply.
Note: Assume time() returns the current system time. Note: Assume randint() returns a random positive integer.
h(x)= time()
h(x) = (2x+3) % 7
h(x) = x + randint() h(x) = (5x+7) % 3x None of the above
Question 7 Submitted Jun 5th 2021 at 2:25:43 pm Problem 5.7: You are given the following Bloom Filter:
0123456789 TFFTTFTFTT
The Bloom Filter uses the following hash functions:
h1 (x) = x + 13 h2 (x) = 5x h3 (x) = 2x + 7
Which of the following de�nitely are not in the Bloom Filter? Select all that apply. 2
All of the above might appear in the Bloom Filter
Question 8 Submitted Jun 5th 2021 at 2:25:47 pm Problem 5.7: You are given the following Bloom Filter:
0123456789 TFFTTFTFTT
The Bloom Filter uses the following hash functions:
h1 (x) = x + 13 h2 (x) = 5x h3 (x) = 2x + 7
Which of the following de�nitely are in the Bloom Filter? Select all that apply. 1
None of the above
Question 9 Submitted Jun 5th 2021 at 2:25:53 pm
Problem 5.9: You are given the following Count- :
The Count- uses the following hash functions:
h1 (x) = x + 13 h2 (x) = 5x h3 (x) = 2x + 7
What is the maximum possible count of the number 1? 0
Question 10 Submitted Jun 5th 2021 at 2:25:56 pm
Problem 5.10: You are given the following Count- :
The Count- uses the following hash functions:
h1 (x) = x + 13 h2 (x) = 5x h3 (x) = 2x + 7
What is the maximum possible count of the number 13? 0
Week 6: Fast String Searching
This section has 10 questions (below). You may need to scroll down to see them.
Report ambiguous questions: https://forms.gle/ZZ1c2eiYNaMRPepi9 Question 1 Submitted Jun 5th 2021 at 2:43:18 pm
Problem 6.1: True/False: Given a string s that has length k, where k does not include the null termination symbol ( $ ), the Burrows- of s is guaranteed to be longer than the Su�x Array of s.
True False
Question 2 Submitted Jun 5th 2021 at 2:43:22 pm
Problem 6.2: How many failure links are in an Aho-Corasick Automaton with 35 nodes?
Question 3 Submitted Jun 5th 2021 at 2:43:25 pm
Problem 6.3: You construct an Aho-Corasick Automaton from a dataset containing 5 unique words,
each of length 6. How many dictionary links will the resulting automaton have?
Note: Unique words can share letters, but the overall words must be di�erent.
Question 4 Submitted Jun 5th 2021 at 2:43:35 pm
Problem 6.4: What is the Burrows- of the string FRIDAYFINAL ? Use $ as the
string-terminating symbol (i.e., the string + string-terminating symbol would be FRIDAYFINAL$ ). LNDIY$RFAIFA
Question 5 Submitted Jun 5th 2021 at 2:43:43 pm
Problem 6.5: You are given the following Burrows- :
nnuvlnrawn$ogdeeteo
What is the original string from which this Burrows- was constructed?
Note: Include the string-termination symbol ( $ ) at the end of your string. nevergonnaletudown$
Question 6 Submitted Jun 5th 2021 at 2:44:05 pm Problem 6.6: Consider the following string:
Generate the LastToFirst (L2F) array from the BWT of this string.
Note: Order the values of the L2F array such that the top item is the �rst element of the L2F array and the bottom item is the last element of the L2F array.
Note: CLASSICAL is the word, NOT the BWT. 6
3 7 5 0 8 1 4 9 2
Question 7 Submitted Jun 5th 2021 at 2:44:11 pm
Problem 6.7: You construct an Aho-Corasick Automaton from the following words:
Computer ComputerScience Science
Data DataScience
How many nodes are in the resulting automaton?
Question 8 Submitted Jun 5th 2021 at 2:44:14 pm
Problem 6.8: How many failure links are in the automaton you constructed in Problem 6.7?
Question 9 Submitted Jun 5th 2021 at 2:44:17 pm
Problem 6.9: How many dictionary links are in the automaton you constructed in Problem 6.7?
Question 10 Submitted Jun 5th 2021
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com