EECS 281 final || 100% Correct Answers.
You are given a hash table with size M = 10 and hash function H(n) = (2n + 3) mod M .
Collisions are resolved using quadratic probing. What would the table look like (with an X
denoting an empty location) after inserting the following elements in the order given?
4, 10, 12, 7, 2 correct answers [X, 4, X, 10, X, X, 2, 12, 7, X]
In which one of the following situations would you want to use a hash table? correct answers
You have a classroom full of students each with a 10-digit ID number, and you want to find
themby their ID number.
What does the following function return?
1 int count(Node* curNode) {
2 if (curNode == nullptr)
3 return 0;
4 else if (curNode->parent == nullptr)
5 return 1 + count(curNode->left) + count(curNode->right);
6 else if (curNode->left == nullptr && curNode->right == nullptr)
7 return 1;
8 else
9 return count(curNode->left) + count(curNode->right);10 } // count() correct answers The
number of external (leaf) nodes plus the root
Suppose there existed something called a *baugh-Tree. A *baugh-Tree can be implemented
similar tothe array-based binary tree covered in lecture, except that its internal nodes can
have up to six children.What are the best- and worst-case space complexities, respectively, of
a *baugh-Tree with n nodes? correct answers Θ(n), Θ(6^n)
Given the following preorder and inorder traversals of a binary tree, what is the postorder
traversal of thissame binary tree?
• Preorder: 11, 19, 31, 7, 10
• Inorder: 31, 19, 11, 10, 7 correct answers 31, 19, 10, 7, 11
Suppose you have a binary search tree, where h represents the tree's height and n represents
the numberof nodes. What is the worst-case complexity of a search operation on this tree in
terms of h and/or n? correct answers Θ(h)
Given pointer-based representations of both, what can be said about a binary search tree that
cannot besaid about a binary tree? correct answers The inorder traversal of a tree is always a
sorted list.
Suppose that in a binary search tree, when a node with two children is deleted, it is replaced
by its inorder successor. Given a pointer to the node to be deleted, what is the time
complexity of finding the inorder successor in the average case, if the tree contains n nodes?
correct answers Θ(log n)
Which of the following statements about AVL trees is TRUE? correct answers Optimally re-
balancing an AVL tree after a deletion can take more than O(1) time
You are given a hash table with size M = 10 and hash function H(n) = (2n + 3) mod M .
Collisions are resolved using quadratic probing. What would the table look like (with an X
denoting an empty location) after inserting the following elements in the order given?
4, 10, 12, 7, 2 correct answers [X, 4, X, 10, X, X, 2, 12, 7, X]
In which one of the following situations would you want to use a hash table? correct answers
You have a classroom full of students each with a 10-digit ID number, and you want to find
themby their ID number.
What does the following function return?
1 int count(Node* curNode) {
2 if (curNode == nullptr)
3 return 0;
4 else if (curNode->parent == nullptr)
5 return 1 + count(curNode->left) + count(curNode->right);
6 else if (curNode->left == nullptr && curNode->right == nullptr)
7 return 1;
8 else
9 return count(curNode->left) + count(curNode->right);10 } // count() correct answers The
number of external (leaf) nodes plus the root
Suppose there existed something called a *baugh-Tree. A *baugh-Tree can be implemented
similar tothe array-based binary tree covered in lecture, except that its internal nodes can
have up to six children.What are the best- and worst-case space complexities, respectively, of
a *baugh-Tree with n nodes? correct answers Θ(n), Θ(6^n)
Given the following preorder and inorder traversals of a binary tree, what is the postorder
traversal of thissame binary tree?
• Preorder: 11, 19, 31, 7, 10
• Inorder: 31, 19, 11, 10, 7 correct answers 31, 19, 10, 7, 11
Suppose you have a binary search tree, where h represents the tree's height and n represents
the numberof nodes. What is the worst-case complexity of a search operation on this tree in
terms of h and/or n? correct answers Θ(h)
Given pointer-based representations of both, what can be said about a binary search tree that
cannot besaid about a binary tree? correct answers The inorder traversal of a tree is always a
sorted list.
Suppose that in a binary search tree, when a node with two children is deleted, it is replaced
by its inorder successor. Given a pointer to the node to be deleted, what is the time
complexity of finding the inorder successor in the average case, if the tree contains n nodes?
correct answers Θ(log n)
Which of the following statements about AVL trees is TRUE? correct answers Optimally re-
balancing an AVL tree after a deletion can take more than O(1) time
