These are the questions and answers from the Gradescope lecture quizzes that we gave out this quarter.
Lecture 3
1. string Member Functions
How would you use substr to extract "Julie" from the following string? Select all versions that would work.
string full = "Cynthia Julie";
string julie = __________;
A. full.substr(8)
B. full.substr(8, 5)
C. full.substr(8, 13)
A and B
2. Pass by Reference vs. Pass by Value
What does the following code snippet print?
int binky(int& x) {
x += 6;
return x;
}
int main() {
int x = 4;
int y = binky(x);
cout << x << ", " << y << endl;
return 0;
}
A. 4, 4
B. 4, 10
C. 10, 4
D. 10, 10
D
3. Simple Test
Say you have the following two lines of code:
string expectedOutput = binky();
string myOutput = winky();
What function from Simple Test would you use to test that expectedOutput and myOutput are equal to each other? Select all that would work.
A. EXPECT_EQUAL(true, myOutput)
B. EXPECT_EQUAL(myOutput, expectedOutput)
C. EXPECT_EQUAL(true, expectedOutput)
D. EXPECT_EQUAL(expectedOutput, myOutput)
B and D
Lecture 4
1. Vector operations
What's the output of the following code snippet?
Vector<int> res;
for (int i = 0; i < 5; i++) {
res.insert(0, i);
}
cout << res << endl;
A. {0, 1, 2, 3, 4}
B. {4, 3, 2, 1, 0}
C. {5, 4, 3, 2, 1}
D. {1, 2, 3, 4, 5}
B
2. Vector performance
We learned in class that the insert and remove operations can be slow depending on how many elements in the Vector need to be shifted around as a result of the addition / deletion. With that in mind, assume we have a Vector<int> myVec with n elements in it. Which operation is faster:
// Option a
myVec.insert(0)
// Option b
myVec.remove(0)
A. Option a
B. Option b
C. Both are equally fast
C
3. Grids
Say you have access to two variables row and col which are both ints representing a position on a Grid<string> myGrid. We'll call the element myGrid[row][[col] myGridElem. Therefore,
string myGridElem = myGrid[row][col]
What boolean value would you use to check if myGridElem's northwest (top-left) neighbor is in bounds within myGrid?
if (_____FILL IN HERE_____) {
cout << "The northwest (top-left) element is in bounds!" << endl;
}
A. myGrid.inBounds(row - 1, col + 1)
B. myGrid.inBounds(row + 1, col)
C. myGrid.inBounds(row - 1, col - 1)
D. myGrid.inBounds(row + 1, col + 1)
C
Lecture 5
For each of the following questions, Stacks and Queues can be read as follows:
// Stacks
bottom { 1, 2, 3 } top
// Queues
front { "hello", "world" } back
Here's the relevant Stanford library documentation that you might find useful:
1. Snacks
What is the contents of favoriteSnacks after the following code snippet?
Stack<string> favoriteSnacks;
favoriteSnacks.push("oreo");
favoriteSnacks.push("goldfish");
favoriteSnacks.pop();
favoriteSnacks.push("mochi");
favoriteSnacks.pop();
favoriteSnacks.push("takis");
A. { "mochi", "takis" }
B. { "oreo", "takis" }
C. { "oreo", "goldfish", "mochi", "takis" }
D. { "takis", "oreo" }
B
2. Queues
Select all code snippets that will throw an error.
Code snippet 1:
Queue<int> myNums;
myNums.dequeue();
Code snippet 2:
Queue<int> myNums;
myNums.enqueue(3);
myNums.peek();
myNums.peek();
Code snippet 3:
Queue<int> myNums;
myNums.peek();
Code snippet 4:
Queue<int> myNums;
myNums.enqueue(3);
myNums.dequeue();
myNums.dequeue();
A. 1
B. 2
C. 3
D. 4
A, C, and D
3. Stacks and Queues
Suppose we have the following code:
Queue<double> coupaQueue;
coupaQueue.enqueue(4.7);
coupaQueue.enqueue(2.5);
coupaQueue.dequeue();
coupaQueue.enqueue(5.3);
cout << coupaQueue.dequeue() << endl;
Select all code snippets that would print out the same number.
Code snippet 1:
Stack<double> coupaStack;
coupaStack.push(2.5);
coupaStack.push(5.3);
coupaStack.pop();
cout << coupaStack.pop() << endl;
Code snippet 2:
Stack<double> coupaStack;
coupaStack.push(4.7);
coupaStack.pop();
coupaStack.push(2.5);
cout << coupaStack.pop() << endl;
Code snippet 3:
Stack<double> coupaStack;
coupaStack.push(2.5);
coupaStack.pop();
coupaStack.push(5.3);
cout << coupaStack.pop() << endl;
A. 1
B. 2
C. 3
A and B
Lecture 6
1. Map Tweets
We want to create a map called tweets that looks like the following:
{ "stephen": "tweet1", "draymond": "tweet2" }
Select all of the following code snippets that would produce a map like this.
Code snippet 1:
Map<string, string> tweets;
tweets["stephen"] = "tweet1";
tweets["draymond"] = "tweet2";
Code snippet 2:
Map<string, string> tweets;
tweets.put("draymond", "tweet2");
tweets.put("stephen", "tweet1");
Code snippet 3:
Map<string, string> tweets;
tweets.put("tweet1", "stephen");
tweets.put("tweet2", "draymond");
Code snippet 4:
Map<string, string> tweets;
tweets.put("stephen") = "tweet1";
tweets.put("draymond") = "tweet2";
A. 1
B. 2
C. 3
D. 4
A and B
2. Set Locations
Suppose we have the following code.
Set<string> campusLocations;
campusLocations.add("huang");
campusLocations.add("coupa");
campusLocations.add("huang");
for (string location : campusLocations) {
cout << location << ", ";
}
Which of the following would be printed?
A. huang, coupa, huang,
B. huang, coupa,
C. coupa, huang,
C
3. Map within Map
Suppose we have the following code.
Map<string, Map<string, int>> transitTime;
Map<string, int> transitOptions;
transitOptions["car"] = 30;
transitOptions["bus"] = 45;
transitTime["SF"] = transitOptions;
transitTime["SF"]["walk"] = 2000;
cout << transitTime["SF"] << endl;
What is printed out by the code above?
A. {"car": 30, "bus": 45, "walk": 2000}
B. {"bus": 45, "car": 30, "walk": 2000}
C. {"bus": 45, "car": 30}
B
Lecture 7
For the following 3 questions, we will refer to this code, with line numbers labeled.
line 1: int function(int num) {
line 2: if (num == 1) {
line 3: return 7;
line 4: } else {
line 5: return 1 + function(num - 1);
line 6: }
line 7: }
1. Reading Recursion
Looking at the above code snippet, what would be printed out if we call function(4)?
A. 7
B. 11
C. 10
C
2. Base Case
Looking at the above code snippet, what line(s) contain the base case?
A. lines 2-3
B. line 5
C. line 1
A
3. Recursive Case
Looking at the above code snippet, what line(s) contain the recursive case?
A. lines 2-3
B. line 5
C. line 1
B
4. Big O
Select all that Big-O analysis takes into account:
A. how big each step is
B. how fast the computer is
C. the amount of time it takes to run code
D. the number of steps it takes to run code
D
Lecture 8
1. Determining Big O
What is the big-O runtime of the following code snippet?
for (int i = 0; i < N; i++) {
for (int j = 0; j < 10000; j++) {
cout << "Hello, World!" << endl;
}
}
A. O(N^2)
B. O(N)
C. O(1)
D. O(M * N)
B
2. Reporting Big O
A student determines that a code snippet has a big-O runtime of: O(N^3 - N^2 + N - 3). What should they report the big-O runtime as?
A. O(N^3 - N^2 + N - 3)
B. O(N^3)
C. O(N^2)
D. O(N^3 - N^2 + N)
B
3. Determining Big O Part 2
What is the big-O of the following code snippet?
void function(int n) {
for (int i = 0; i < n; i++) {
cout << "hello" << endl;
}
}
A. O(1)
B. O(N)
C. O(N^2)
D. O(logN)
B
Lecture 9
1. Wrapper Functions
Select the following statements that are true about wrapper functions.
A. It is the function that a caller/other users will have access to
B. It includes any extra bookkeeping parameters you like
C. It contains a call to the recursive helper function
D. It performs recursion
A and C
2. Binary Search
Select the following statements that are true about binary search.
A. The input can be unsorted
B. It runs in O(log n) time
C. It runs in O(n) time
D. It works by continuously halving the search space in order to find the element in question
B and D
Lecture 10
Have you ever wanted to know all the combinations of the Rock, Paper, Scissors game?! The time has now finally arrived!
For the rest of the questions, we want to generate all of the combinations that you could play in a game of Rock, Paper, Scissors. We will use "R", "P", and "S" to abbreviate. We have the following function header:
void generateAllSequences(int length, Vector& allSequences, string sequence)
1. Q1
What does the sequence parameter in generateAllSequences represent?
A. The original input to the function
B. The current string that we can see in the recursive call (some combination of Rs, Ps, and Ss
C. The output of the function
B
2. Q2
What could our recursive calls look like? Select all the code options that would produce the correct "R", "P", and "S" combinations.
Option 1:
sequence += "R";
generateAllSequences(length, allSequences, sequence);
sequence.erase(sequence.size() - 1);
sequence += "P";
generateAllSequences(length, allSequences, sequence);
sequence.erase(sequence.size() - 1);
sequence += "S";
generateAllSequences(length, allSequences, sequence);
sequence.erase(sequence.size() - 1);
Option 2:
Vector<string> letters = ["R", "P", "S"];
for (int i = 0; i < 3; i++) {
sequence += letters[i];
generateAllSequences(length, allSequences, sequence);
sequence.erase(sequence.size() - 1);
}
A. Option 1
B. Option 2
A and B
3. Q3
Using one of your choices of code from the previous question, what sequence would be generated first?
A. RPS
B. SPR
C. RRR
D. SSS
C
Lecture 11
Let’s return to our Rock, Paper, and Scissors game from last time, but this time we are in a much more competitive state. Instead of generating all sequences of "R", "P", and "S", we want to find the winning combination against our opponent.
Assume we have a given function that will return true if our sequence will win against our opponent and false otherwise:
bool trySequence(string sequence)
Let’s look at the following code for Rock, Paper, Scissors, that is slightly adjusted from the code we wrote last time. To simplify, we will only check sequences of length 3.
bool findWinningSequence(Vector<string>& sequence) {
if (sequence.size() == 3) {
// to do 1
}
Vector<string> letters = ["R", "P", "S"];
for (int i = 0; i < 3; i++) {
sequence += letters[i];
// to do 2
sequence.remove(sequence.size() - 1);
}
return false;
}
1. Q1
What should // to do 1 be? Select all that would work.
Option 1:
return true;
Option 2:
return trySequence(sequence);
Option 3:
return findWinningSequence(sequence);
A. Option 1
B. Option 2
C. Option 3
B
2. Q2
What should // to do 2 be? Select all that would work.
Option 1:
if (trySequence(sequence)) {
return true;
}
Option 2:
if (findWinningSequence(sequence)) {
return true;
} else {
return false;
}
Option 3:
if (findWinningSequence(sequence)) {
return true;
}
A. Option 1
B. Option 2
C. Option 3
C
3. Q3
What piece of code is our "choose" step?
A. if (sequence.size() == 3) {
B. sequence += letters[i];
C. sequence.erase(sequence.size() - 1);
B
4. Q4
What piece of code is our "unchoose" step?
A. if (sequence.size() == 3) {
B. sequence += letters[i];
C. sequence.erase(sequence.size() - 1);
C
Lecture 12
For this quiz, we will be writing a function to see if 2 numbers from a list add up to a target number. This is a simplified version of a problem you may see in section.
We want to write the function: bool canMakeSumFromTwoNums(Vector<int>& values, int target). It takes a reference to a Vector<int> and an int target value and returns true if exactly 2 numbers from the Vector sum to the target value.
For example, canMakeSum({3, 4, 5}, 9) should return true because 4 + 5 = 9. But canMakeSum({1, 3, 5}, 9) should return false because no 2 numbers add up to 9.
1. Q1
Which of the following statements is true to make our code run as fast as possible?
A. We should return true as soon as we find 2 numbers that add up to the target, regardless of if we’ve finished checking all of the combinations of 2 numbers.
B. We should only return true if we’ve found 2 numbers that add up to the target if we have checked all combinations first.
A
2. Q2
Which of the following statements is true about when we should return false?
A. Return false as soon as we check the first 2 numbers and see that they don’t add up to the target number.
B. Only once we have checked all possible combinations and haven’t found any that add up to the target number, then return false.
B
3. Q3
Which of the following are true about the recursive calls we will need to make? Select all that apply.
A. One of the recursive calls represents choosing the number. This means we are choosing the number to be 1 of the 2 numbers that we sum, trying to sum to the target number.
B. One of the recursive calls represents NOT choosing the number. This means we are not choosing the number to be 1 of the 2 numbers that we sum, trying to sum to the target number.
C. We need 2 numbers to sum to the target number, so that’s why we need 2 recursive calls.
A and B
Lecture 13
1. Insertion Sort
The worst case scenario for insertion sort causes a Big O of O(n^2). What would the input need to look like for insertion sort to reach that worst case Big O?
A. Elements in reverse sorted order
B. Elements in random order
C. Elements already in sorted order
A
2. Recursion in Sort Algorithms
Which of the following algorithms are done recursively?
A. Insertion sort
B. Bubble sort
C. Merge sort
C
Lecture 14
We want to write a class that models a Giraffe. We have the following code, some of the lines labeled with numbers.
// Giraffe.h
#ifndef _giraffe_h
#define _giraffe_h
class Giraffe {
public:
(1) Giraffe(string name, double height);
(2) void eatGrass(double grassAmount);
(3) void walkAround(double timeToWalk);
private:
(4) string _name;
(5) double _height;
};
#endif
1. Q1
What line(s) are the constructor(s)?
A. 1
B. 2
C. 3
D. 4
E. 5
A
2. Q2
What line(s) are the member functions(s)?
A. 1
B. 2
C. 3
D. 4
E. 5
B and C
3. Q3
What line(s) are the member variable(s)?
A. 1
B. 2
C. 3
D. 4
E. 5
D and E
4. Q4
We are now writing the eatGrass function. We see a comment above the function that says // grassAmount is non-negative. What is that comment called?
A. Accessor
B. Mutator
C. Precondition
D. Private data
C
Lecture 15
1. Q1
When would we want to use a dynamically allocated array over a statically allocated array?
A. When we want persistent memory that we have control over deleting.
B. If we want to resize the array.
C. If we don’t want to do the extra work of deleting the array.
A and B
2. Q2
Consider the following snippet:
int myFunction() {
int* myArray = new int[2];
heapArr[0] = 7;
heapArr[1] = 13;
return 42;
}
A. It will compile / run smoothly
B. It will cause a memory leak
C. It will crash
D. No issues here
A and B
3. Q3
Which of the following are true about the snippet?
A. It will compile / run smoothly
B. It will cause a memory leak
C. It will crash
D. No issues here
A and B
4. Q4
If we change int* myArray = new int[2]; to int myArray[2]; in the above code, what will happen when we run it?
A. It will run just fine in terms of memory
B. It will cause a memory leak
A
5. Q5
What will be printed out by the following code?
int* myArray = new int[2];
cout << myArray[0];
A. -1
B. 0
C. We have no idea, it will be a random/"garbage" value
C
Lecture 17
Q1
Which of the following code snippets won’t cause any memory issues?
Snippet 1:
int* arr = new int[3];
delete [] arr;
arr[0] = 5;
Snippet 2:
int* arr = new int[3];
arr[0] = 5;
delete [] arr;
Snippet 3:
int* arr = new int[3];
arr[0] = 5;
Snippet 4:
int* arr = new int[3];
arr[0] = 5;
delete [3] arr;
A. 1
B. 2
C. 3
D. 4
B
Q2
What would we expect to printed out by the following code?
double iLikePie = 3.14;
cout << &iLikePie << endl;
A. 3.14
B. It’s address in memory
B
Q3
We want to create 2 structs, one will represent a book and the other will represent the author. For each book, it should point to its author. See the following Book struct:
struct Book {
string title;
int year;
______
};
What should go in the blank line to make sure that if we change information about the author, then it will be updated for all of the books by that author?
A. Author author;
B. Author* author;
C. book -> author;
B
Lecture 18
Throughout this concept check, we will be referring to this binary heap:
Q1
To the binary heap from Q1, we want to enqueue 6. What should the heap look like after enqueuing 6?
Option 1:
Option 2:
Option 3:
A. Option 1
B. Option 2
C. Option 3
B
Q2
To the binary heap from Q1 (pretend that we have not enqueued 6), we want to dequeue. What should the heap look like after dequeuing?
Option 1:
Option 2:
Option 3:
A. Option 1
B. Option 2
C. Option 3
A
Q3
For the binary heap from Q1 (pretend that the previous 2 questions haven't happened), what would it look in a 0-indexed array?
Option 1:
![binary heap with the following array representation: [ 3, 5, 7, 9, 10, 11, 15, ?, ?]](img/pqheap-8.png)
Option 2:
![binary heap with the following array representation: [ 11, 10, 15, 9, 5, 7, 3, ?, ?]](img/pqheap-9.png)
Option 3:
![binary heap with the following post-order traversal: [ 3, 7, 5, 9, 15, 10, 11, ?, ?]](img/pqheap-10.png)
A. Option 1
B. Option 2
C. Option 3 \
C
Lecture 19
Q1
What is a collateral value of a technology?
A. A value that is intentionally embedded into a product.
B. A value that a team agrees would be useful within a product.
C. A value that appears unintentionally, as a result of how users interact with them.
C
Q2
True or false: A priority queue could be used to rank such things as hospital queues, housing needs, or organ donation.
A. True
B. False
A
Q3
Which philosophies underlying the coordinated entry system
A. Decrease harm to underserved communities
B. Housing first
C. Prioritization according to need
D. Prioritize access to everyone
B and C
Lecture 20
Q1
When would we want to use LinkedNodes over arrays?
A. When we want to do lots of lookups, using LinkedNodes is faster than arrays
B. When we have lots of edits to make, using LinkedNodes is faster than arrays
C. It doesn't matter, they have the same Big-O
B
Q2
We want to create the following picture:
So far, we have written the following code:
LinkNode* node1 = new LinkNode;
node1 -> data = 3;
LinkNode* node2 = new LinkNode;
node1 -> next = node2;
What line of code should we write next to create the picture above? Select all that apply.
A. node2 -> data = 7;
B. node1 -> next -> next -> data = 7;
C. node1 -> next -> data = 7;
D. node1 -> data = 7;
A and C
Lecture 21
For all problems, you can assume there are at 3 nodes in the list, and do not need to worry about updating the size.
Q1
In a doubly linked list, each node has a next and a prev pointer. What pointers do we need to change to add a node to the front?
"Previous front node" refers to the node that is at the front before adding any nodes. "Current node" refers to the node that we want to add in the front.
A. front pointer
B. tail pointer
C. the previous front node’s previous pointer
D. the previous front node’s next pointer
E. current node previous pointer (assume it is initialized to null)
F. current node next pointer
A, C, and F
Q2
In a doubly linked list, what pointers do we need to change to add a node somewhere in the middle of the list?
"Previous node" refers to the node that is right before where we want to place our node. "Current node" refers to the node that we want to add. "Next node" refers to the node that is right after where we want to place our node.
A. the previous node’s previous pointer
B. the previous node’s next pointer
C. the next node’s previous pointer
D. the next node’s next pointer
E. current node previous pointer
F. current node next pointer
B, C, E, and F
Q3
If we are using a LinkedList for a queue with a tail pointer, what would a dequeue look like? Select which code block would return the dequeued node and update the list correctly.
Option 1:
_front = _front -> next;
return _front;
Option 2:
LinkedNode *toDequeueNode = _front;
_front = toDequeueNode -> next;
return _front;
Option 3:
LinkedNode *toDequeueNode = _front;
_front = toDequeueNode -> next;
return toDequeueNode;
A. Option 1
B. Option 2
C. Option 3
C
Lecture 22
Assume that we have created a printList function which will print out a linked list. We have also created a freeList function which frees all memory associated with a list.
For this concept check, we will refer to the following code:
void main() {
Node* list = /* some logic to make the list 1 -> 3 -> 5 -> null */
// line 1
printList(list);
freeList(list);
}
Pay special attention whether list is being passed by value or by reference.
We will replace // line 1 with function1(list);. The definition of function1 is below:
void function1(Node* list) {
list = new Node;
list->data = 42;
list->next = nullptr;
}
We now run the main function.
Q1
What is printed out by printList in main, after we call function1?
A. 1, 3, 5
B. 42
C. 42, 3, 5
A
Q2
Is there a memory leak?
Yes
Q3
How many nodes are leaked?
A. 0
B. 1
C. 2
D. 3
E. 4
B
Q4
We will replace // line 1 with function2(list);. The definition of function2 is below:
void function2(Node*& list) {
list = new Node;
list->data = 42;
list->next = nullptr;
}
We now run the main function.
What is printed out by printList?
A. 1, 3, 5
B. 42
C. 42, 3, 5
B
Q5
Is there a memory leak?
Yes
Q6
How many nodes are leaked?
A. 0
B. 1
C. 2
D. 3
E. 4
D
Lecture 23
Inserting Into a BST
Assume we have the following BST. We want to insert 9. What would the resulting BST look like?
Option 1:
Option 2:
Option 3:
A. Option 1
B. Option 2
B. Option 3
A
Creating a BST
We want to produce the following BST. What order of inserting numbers would lead to this BST?
A. 12, 5, 7, 17
B. 12, 5, 17, 7
C. 12, 7, 5, 17
D. 12, 7, 17, 5
E. 12, 17, 5, 7
A, B, and E
Heap vs. BST Big O
Check all statements that are true.
A. Both PQHeap::enqueue and BST::put operations have the same Big-O, regardless of their structure.
B. PQHeap::enqueue and BST::put have the same Big-O only if the BST is balanced.
C. If a BST is not balanced, then a PQHeap::enqueue has a faster Big-O than BST::put
B and C
Lecture 24
Assume we have the following tree:
Q1
What would be printed out by an in-order traversal?
A. 3, 7, 9, 15, 5, 10, 11
B. 9, 7, 15, 3, 10, 5, 11
C. 9, 15, 7, 10, 11, 5, 3
B
Q2
What would be printed out by a pre-order traversal?
A. 3, 7, 9, 15, 5, 10, 11
B. 9, 7, 15, 3, 10, 5, 11
C. 9, 15, 7, 10, 11, 5, 3
A
Q2
What would be printed out by a post-order traversal?
A. 3, 7, 9, 15, 5, 10, 11
B. 9, 7, 15, 3, 10, 5, 11
C. 9, 15, 7, 10, 11, 5, 3
C
Q3
Let’s look at the traverse function from lecture, without the print line:
void traverse(Node* node) {
if (node != nullptr) {
// option 1
traverse(node->left);
// option 2
traverse(node->right);
// option 3
}
}
We want to add the following print line:
cout << node->key << " ";
Where should we add the print line in order to do an in-order traversal?
A. Option 1
B. Option 2
C. Option 3
B
Q4
Where should we add the print line in order to do a pre-order traversal?
A. Option 1
B. Option 2
C. Option 3
A
Q5
Where should we add the print line in order to do a post-order traversal?
A. Option 1
B. Option 2
C. Option 3
C
Lecture 25
Q1
We are going to create a Huffman encoding tree from the text "heyy".
We start with 3 tree nodes, one for 'h', one for 'e', and one for 'y'.
If we store these in a priority queue, what would our partially-built Huffman tree look like after one step?
Option 1:
Option 2:
Option 3:
A. Option 1
B. Option 2
C. Option 3
A and B
Q2
What will the fully-built Huffman tree look like?
Option 1:
Option 2:
Option 3:
A. Option 1
B. Option 2
C. Option 3
C
Q3
Using our fully-built Huffman tree, what is the code for "yeh"?
A. 01011
B. 11100
C. 01110
A
Lecture 26
Q1
We want to start at node 1 and end at node 6 for the first graph at the following link (Graph Image):
We will run some steps of BFS. First, we create a Queue called toExplore.
We start with enqueuing node 1 in toExplore. After one loop of BFS as defined in lecture, what will be the contents of toExplore?
You may assume for this quiz that neighbors are explored in ascending order.
A. 1 2 5
B. 2 5
C. 5 2
D. 2 5 3 4 6
B
Q2
With the same graph as above, after another loop of BFS, what will be the contents of toExplore?
A. 5 3
B. 3 5
C. 2 5 3
D. 5 1 3
Q3
What’s the difference between BFS and Djikstra’s algorithm?
A. Both BFS and Djikstra takes into account weights/distances between nodes.
B. Neither BFS or Djikstra take into account weights/distances between nodes.
C. Djikstra finds the shortest path in graphs while taking into account weights/distances between nodes.
D. BFS finds the shortest path in graphs while taking into account weights/distances between nodes.
C
Lecture 27
Q1
Which of the following are valid, deterministic hash functions? It doesn’t have to be a great hash function, just valid.
Option 1:
int hash(int elem) {
return abs(elem) % numBuckets;
}
Option 2:
int hash(int elem) {
return randomInteger(0, 10);
}
Option 3:
int hash(int elem) {
return 1;
}
Which are valid hash functions?
A. Option 1
B. Option 2
C. Option 3
A and C
Q2
We are going to insert 1, 4, and -6, using 3 buckets and this hash function:
int hash(int elem) {
return abs(elem) % numBuckets;
}
How many nodes will be in bucket 0?
A. 0 nodes
B. 1 node
C. 2 nodes
B
Q3
How many nodes will be in bucket 1?
A. 0 nodes
B. 1 node
C. 2 nodes
C
Q4
How many nodes will be in bucket 2?
A. 0 nodes
B. 1 node
C. 2 nodes
A