CS61B: Data Structures Midterm #2, Fall 2020
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS61B: Data Structures
Midterm #2, Fall 2020
1. Heap Operations (55 points)
a) (20 points). Given the min-heap to the left below, suppose we call insert(0). The resulting min-heap will have 9 elements, as shown to the right below. What numbers are in spots a-d?
(a) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
(b) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
(c) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
(d) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
b) (35 points) Given the same initial min-heap from before (redrawn to the left below), suppose we call removeMin three times. The resulting min-heap will have five elements, as shown to the right below. What number is in each spot?
(a) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
(b) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
(c) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
(d) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
(e) ○ 0 ○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8
2. Trie Operations (60 points). Given the Trie below, answer the following questions. Recall that isKey is true for blue nodes and isKey is false for white nodes.
a) (15 points) If we call keysWithprefix("su"), what keys will get returned? Recall that keysWithPrefix finds all keys with the given prefix.
□ sun □ chin □ sued □ goal □ sue □ sunn □ chair □ sunny □ n □ y □ e □ d
b) (15 points) What key, when added, creates the fewest nodes? If multiple keys produce the minimum, select all that apply.
□ goals □ in □ goat □ soccer □ chain □ cheese □ at □ camel
c) (30 points) Suppose we add the function shortestPrefixOf that accepts a String s and returns the shortest key in the Trie that is a prefix of s. Calling shortestPrefixOf("goalie") on the Trie would return "goal". A string is a prefix of itself, e.g. calling shortestPrefixOf("goal") would return "goal". Assume shortestPrefixOf has been implemented correctly and as efficiently as possible. By efficient, we mean that it traverses no more nodes than necessary. What String s below would maximize the
number of nodes needed to be traversed? If multiple words produce the maximum, select all that apply.
□ sun □ sunnyday □ sunny □ chin □ sue □ goal □ sued □ sunn □ chair □ chairlift
3. Heap Iterator (50 points). Suppose we have an implementation of the MinPQ interface from lecture given below. This specific implementation only allows Integer items. Assume the priority of an Integer is itself. You should not assume that XMinPQ uses a heap, i.e. the underlying implementation is unknown and not provided.
public class XMinPQ implements MinPQ
public void add(Integer x) {...}
public Integer getSmallest() {...}
public Integer removeSmallest() {...}
public int size() {...}
public Iterator
return new XIterator();
}
private class XIterator implements Iterator
public int x;
public XIterator() {
x = removeSmallest();
}
public boolean hasNext() {
return x > 0;
}
public Integer next() {
x = x - 1;
return removeSmallest();
}
}
}
What is the result of the code below? Reminder: The XMinPQ does not necessarily use a heap, i.e. we know that it implements the priority queue abstract data type, but we do not know how.
public static void main(String[] args) {
XMinPQ mpq = new XMinPQ();
mpq.add(4);
mpq.add(1);
mpq.add(5);
mpq.add(2);
mpq.add(6);
mpq.add(3);
mpq.add(8);
mpq.add(7);
for (int i: mpq) {
System.out.print(i + " "); // line 1
}
System.out.println();
for (int i: mpq) {
System.out.print(i + " "); // line 2
}
}
Line 1: ______________________________________________________
Line 2: ______________________________________________________
4. Asymptotics. (230 points). Consider the code below. For each, give the worst case runtime in Theta notation as a function of N.
a) loops (30 points)
public static void loops(int N) {
for (int i = 1; i < 2; i += 1) {
for (int j = 2; j < 4; j = j * j) {
for (int k = 3; k < N; k = k * 2) {
for (int m = 4; m < 8; m = m * m * m) {
System.out.println("hello");
}
}
}
}
}
○ Θ(1) ○ Θ(log log N) ○ Θ((log N)^2) ○ Θ(log N) ○ Θ(N) ○ Θ(N log N)
○ Θ(N^2) ○ Θ(N^2 log N) ○ Θ(N^3) ○ Θ(N^3 log N) ○ Θ(N^4) ○ Θ(N^4 log N)
○ Worse than Θ(N^4 log N) ○ Never terminates (infinite loop)
b) addToSet (40 points)
public static void addToSet(int N) {
HashSet
for (int i = 0; i < N; i += 1) {
// getNextRandomThing takes constant time
RandomThing rt = getNextRandomThing();
m.add(rt);
}
}
Reminder! Throughout all 6 parts (a through f) of this asymptotics problem, you are giving the worst case in theta notation.
○ Θ(1) ○ Θ(log log N) ○ Θ((log N)^2) ○ Θ(log N) ○ Θ(N) ○ Θ(N log N)
○ Θ(N^2) ○ Θ(N^2 log N) ○ Θ(N^3) ○ Θ(N^3 log N) ○ Θ(N^4) ○ Θ(N^4 log N)
○ Worse than Θ(N^4 log N) ○ Never terminates (infinite loop)
c) nestedSum(nestedSum(x)) (40 points)
public static List
List
for (int i : x) {
for (int j : x) {
newInts.add(i + j);
}
}
return newInts;
}
List
int N = x.size();
// Give the runtime for the following call to nestedSum(nestedSum(x))
List
○ Θ(1) ○ Θ(log log N) ○ Θ((log N)^2) ○ Θ(log N) ○ Θ(N) ○ Θ(N log N)
○ Θ(N^2) ○ Θ(N^2 log N) ○ Θ(N^3) ○ Θ(N^3 log N) ○ Θ(N^4) ○ Θ(N^4 log N)
○ Worse than Θ(N^4 log N) ○ Never terminates (infinite loop)
d) g(N, 1) (40 points)
private static void g(int N, int ss) {
if (ss > N) {
return;
}
for (int i = 0; i < N; i += ss) {
System.out.print(i + " ");
}
System.out.println();
g(N, ss * 2);
}
// Give the runtime for the following call:
g(N, 1);
○ Θ(1) ○ Θ(log log N) ○ Θ((log N)^2) ○ Θ(log N) ○ Θ(N) ○ Θ(N log N)
○ Θ(N^2) ○ Θ(N^2 log N) ○ Θ(N^3) ○ Θ(N^3 log N) ○ Θ(N^4) ○ Θ(N^4 log N)
○ Worse than Θ(N^4 log N) ○ Never terminates (infinite loop)
e) g2(N, 1) (40 points)
private static void g2(int N, int ss) {
if (ss > N) {
return;
}
for (int i = 0; i < N; i += ss) {
System.out.print(i + " ");
}
System.out.println();
g2(N, ss * 2);
g2(N, ss * 2);
}
// Give the runtime for the following call:
g2(N, 1);
○ Θ(1) ○ Θ(log log N) ○ Θ((log N)^2) ○ Θ(log N) ○ Θ(N) ○ Θ(N log N)
○ Θ(N^2) ○ Θ(N^2 log N) ○ Θ(N^3) ○ Θ(N^3 log N) ○ Θ(N^4) ○ Θ(N^4 log N)
○ Worse than Θ(N^4 log N) ○ Never terminates (infinite loop)
f) func (40 points)
public void func(int N) {
int Q = 0;
for (int i = 1; i < N; i *= 3) {
Q += 1;
}
disco(Q);
}
public void disco(int Q) {
if (Q == 0) {
return;
}
for (int i = 0; i < Q; i += 1) {
System.out.println("hi");
}
disco(Q - 1);
}
○ Θ(1) ○ Θ(log log N) ○ Θ((log N)^2) ○ Θ(log N) ○ Θ(N) ○ Θ(N log N)
○ Θ(N^2) ○ Θ(N^2 log N) ○ Θ(N^3) ○ Θ(N^3 log N) ○ Θ(N^4) ○ Θ(N^4 log N)
○ Worse than Θ(N^4 log N) ○ Never terminates (infinite loop)
5. Compress (60 Points)
Consider the UnionFind class as covered in lab.
public class UnionFind {
private int[] parent;
public int sizeOf(int v1) {
int root = find(v1);
return -1 * parent[root];
}
public boolean isConnected(int v1, int v2) {
return find(v1) == find(v2);
}
public void connect(int v1, int v2) { ... }
// Path compression is NOT implemented
public int find(int v1) { ... }
}
Suppose we add the method compress to the UnionFind class, which compresses the height of each tree to 1 by connecting every vertex to its respective root. For instance, suppose we have the parent array below
{-4, 0, 0, 2, -4, 4, 4, 6}
If we call compress(), the parent array would become
{-4, 0, 0, 0, -4, 4, 4, 4}
as vertices 3 and 7 connect to their respective roots. A visualization of this process can be seen below:
Note that the values of vertices 0 and 4 stay the same because they are roots. Also note that the values of vertices 1, 2, 5, and 6 happen to stay the same because they are already connected to their respective roots! Fill in the compress method for the UnionFind class below. Do not change the skeleton provided. No credit will be given to solutions which do not use the given skeleton, even if correct.
public class UnionFind {
...
public void compress() {
for (_____________________________) {
if (__________________________) {
__________________________;
}
}
}
}
6. LLRB Insertions (150 points)
We will be using this left learning red-black tree (LLRB) for the following questions.
Recall from lecture and discussion that when we insert items into a LLRB tree, we sometimes need to perform balance operations. Recall that our balance operations are: rotateRight, rotateLeft, and colorFlip.
For each of the following prompts, give a single int value which, when inserted into the LLRB above, causes exactly the requested balance operation to occur. You may only insert int values into the LLRB tree and only a single balance operation may occur.
If multiple possible values would work, choose the smallest, positive value. If there is no value that results in the given balance operation occurring by itself, simply write "None" in the answer box.
Your inserted values should result in only a single balance operation. For example, if your value causes a sequence of rotations or color flips, it is not a valid answer.
Each question is independent. For each sub part, the LLRB tree you're inserting into is the exact, untouched LLRB you see above.
Reminder: If there are multiple values that could work, give the smallest positive value. That is, if 4 and 5 are both valid answers to a problem, you must give 4 for full credit.
|
a) (20 points) A single rotateLeft operation. |
int value to insert: |
|
b) (20 points) A single rotateRight operation. |
int value to insert: |
|
c) (20 points) A single colorFlip operation. |
int value to insert: |
Now consider the corresponding 2-3 tree for the LLRB shown above. Answer the following questions. The last one is particularly difficult.
|
d) (30 points) What is the minimum number of values that we must add to the corresponding 2-3 tree to increase its height? For this problem, values may be any real value (e.g. 3.6), not necessarily positive integers. |
number of values : |
|
e) (60 points) What is the maximum number of values that we can add to the corresponding 2-3 tree without increasing its height? For this problem, values may be any real value (e.g. 3 6), not necessarily positive integers |
number of values : |
7. By The Numbers (175 points). For each scenario below, give the minimum and maximum. If there is no min or max write "None".
Recall that the height of a tree is the number of links from the root to the farthest leaf, i.e. a tree with 2 nodes has height 1. Recall that the depth of a node in a tree is the number of links from the root to that node, i.e. the root of a tree has depth 0, its children have depth 1, and so forth. Assume for the entirety of this problem that duplicates in BSTs are not allowed.
a) (25 points) The number of nodes in a non-empty tree which is both a BST and a max-heap.
Min: __________ Max: __________
b) (25 points) The height of a BST with 7 nodes where the median is the root.
Min: __________ Max: __________
c) (25 points) The height of a WeightedQuickUnion object with 10 items, where all of the objects are connected.
Min: __________ Max: __________
2022-10-20