TITLE
代写racket | Data structure代做 – 这是一个Data structure的racket practice, 考察Data structure的理解和racket的实现, 包括了racket/Data structure等方面
UC Berkeley Computer Science CS61B: Data Structures
Midterm # 2 , Fall 2022
Write the statement I have neither given nor received any assistance in the taking of this exam. below.
Signature: ___________________________
# Points # Points
0 1 6 400
1 250 7 575
2 400 8 750
3 299
4 575
5 750
TOTAL 4000
Name: __________________________
SID: ___________________________
GitHub Account # : fa22-s_____
Person to Lefts # : fa22-s_____
Person to Rights #: fa22-s_____
Exam Room: _____________________
Tips:
- There may be partial credit for incomplete answers. Write as much of the solution as you can, but bear in mind that we may deduct points if your answers are much more complicated than necessary.
- There are a lot of problems on this exam. Work through the ones with which you are comfortable first. Do not get overly captivated by interesting design issues or complex corner cases youre not sure about.
- Not all information provided in a problem may be useful, and you may not need all lines.
- Unless otherwise stated, all given code on this exam should compile. All code has been compiled and executed before printing, but in the unlikely event that we do happen to catch any bugs in the exam, well announce a fix. Unless we specifically give you the option, the correct answer is not does not compile.
- Do not use ternary operators, lambda functions, or streams.
- indicates that only one circle should be filled in.
- indicates that more than one box may be filled in.
- For answers which involve filling in a or , please fill in the shape completely.
UC BERKELEY
GitHub Account #: fa 22 - s______
0. So it begins ( 1 point). Write your name and ID on the front page. Write the exam room. Write the IDs of your neighbors. Write the given statement and sign. Write your GitHub account # (e.g. fa 22 – s185) in the corner of every page. If you are taking the exam remotely, make sure that you are screen sharing, are recording your workspace, and your mic is unmuted.
- DisjointSets ( 250 points). A correct implementation of the WeightedQuickUnion idea from lecture is given below. Here we have one array: arr. We use the convention that if an element is the root of the set, its array value is the weight of the set negated (as you saw on HW3). Otherwise, its array value is the parent of that element (as you also saw on HW3).
1: public void connect( int v1, int v2) { 2: int rootV1 = find(v1); 3: int rootV2 = find(v2); 4: if (rootV1 != rootV2) { 5: if (arr[rootV1] <= arr[rootV2]) { 6: arr[rootV1] += arr[rootV2]; // adds rootV2 tree size to rootV 7: arr[rootV2] = rootV1; 8: } else { 9: arr[rootV2] += arr[rootV1]; // adds rootV1 tree size to rootV 10: arr[rootV1] = rootV2; 11: } 12: } 13: }
a) (150 points) Suppose we replace line 7 with: arr[rootV2] = v1; What are the potential negative consequences of this change?
if connect is called when v1 is not a root, later isConnected operations may be incorrect if connect is called when v2 is not a root, later isConnected operations may be incorrect runtime for connect operations may be asymptotically worse than with the original line 7
runtime for isConnected operations may be asymptotically worse than with the original line 7 none of the above
b) (100 points) For the same modified code from part a, suppose we have 6 items in our WeightedQuickUnion object, i.e. the valid arguments for v1 and v2 are 0, 1, 2, 3, 4, and 5. What is the worst case height of the WeightedQuickUnion tree (per convention, height is zero-indexed)?
0 1 2 3 4 5 10 11
_CS61B MIDTERM 2 , Fall 2022 GitHub Account #: fa 22 – s_______
- EvenIterable ( 400 points). We want to make an EvenIterable class with a constructor that takes in an Iterable and creates a new Iterable object that only iterates over items in even numbered positions. For example, the output of the code below should be 0 then 10 then 20. See the reference sheet at the end of this exam for definitions of the Iterable and Iterator interfaces.
public static void main( String [] args) { List < Integer > L = List .of(0, 1, 10, 2, 20, 3); EvenIterable < Integer > evenIt = new EvenIterable <>(L); for ( int i : evenIt) { System.out.println(i); } // prints 0 then 10 then 20 }
Fill in the EvenIterable class below. Your constructor may use up to linear space and linear time, i.e. the space and time usage must be O(N). You may not need all lines. Your code should not result in exceptions being thrown for the main function above.
public class EvenIterable < T > implements Iterable < T > {
private _______________________________;
public EvenIterable ( Iterable < T > iterable) {
________________________________;
Iterator < T > it = iterable.__________________;
while (_____________________) {
} }
public Iterator < T > iterator() {
return _______________________________;
}
}
UC BERKELEY
GitHub Account #: fa 22 - s______
3. HashSets ( 299 Points). Suppose we create a class HashableArrayList , given below. public class HashableArrayList < T > extends ArrayList < T > { @Override public int hashCode() { int hc = 0; for ( int i = 0; i < size(); i += 1) { hc += get(i).hashCode(); } return hc; } } a) For example, if we created a HashableArrayList containing [1, 2, 10], the hash code would be 13, since the hashcode of an integer is its own value. Below, draw the results of the following code, assuming the hashcode is reduced (i.e. reduced means converted into a bucket number) by modding by the number of buckets. Assume that we are not resizing at any point. Collisions are handled by external chaining (a linked list) where the first instance variable of each node is a link to the stored item, e.g. [1, 2, 10], and the second instance variable is a link to the next node. Additionally, note that the ArrayList .equals() method compares the contents. The first add operation has been done for you.
1 : HashSet < HashableArrayList < Integer >> set = new HashSet <>(); 2: set.add(new HashableArrayList <>(1, 2, 10)); 3: HashableArrayList < Integer > zeroOneTwo = new HashableArrayList <>(0, 1, 2); 4: set.add(zeroOneTwo); 5: set.add(new HashableArrayList <>(13)); // draw after lines 1- 5 all done
b) Copy your diagram from part a to the diagram to the right. Now suppose we also call the following lines of code. Draw the new state of the hash table after all 8 lines of code have executed. 6: set.add(zeroOneTwo); 7: zeroOneTwo.add(3); 8: set.add(zeroOneTwo);
_CS61B MIDTERM 2 , Fall 2022 GitHub Account #: fa 22 – s_______
4. LLRBs ( 575 Points). Suppose we have the LLRB of integers below:
a) (150 points) Draw the corresponding 2-3 tree:
b) (1 25 points) Give all integers which, when inserted into the LLRB, result in a single rotateLeft operation and no further cascading operations (i.e. no rotateLefts, rotateRights or color flips). If this is not possible, write impossible. If it is possible, use inclusive b racket notation, e.g. if your answer is [62, 64] and [66, 68], this is equivalent to saying 62, 63, 64, 66, 67, 68.
c) (1 25 points) Give all integers which, when inserted into the LLRB results in a single rotateRight operation and no further cascading operations (i.e. no rotateLefts, rotateRights or color flips). If this is not possible, write impossible. If it is possible, use inclusive bracket notation, e.g. if your answer is [62, 64] and [66, 68], this is equivalent to saying 62, 63, 64, 66, 67, 68.
d) (1 25 points) At most, how many additional inserts can be performed into the LLRB above without triggering any color flip operations? Do not count the operation that results in the first color flip.
e) ( 50 points) True or false: If we insert enough values into the LLRB above, eventually we will get a colorFlip(40) operation.
True False
UC BERKELEY
GitHub Account #: fa 22 - s______
5. Tree Life ( 750 points). In the heaps lecture, we used an array to represent a complete binary tree (also called "tree representation 3B" in lecture). Suppose we generalize this idea so that our array now represents a trinary tree (where the word tri nary means three , as opposed to bi nary which means two ). Suppose we then have a trinary heap represented by the array [-, 2, 4, 5 , 12, 6, 7, 8, 11, 20]. Recall that in this representation that the leftmost item is unused, i.e. the – indicates the unused position.
a) (100 points) What value is 8s parent? ______
b) (150 points) If we perform a pre-order traversal of this tree, what are the last 3 values we traverse? Give in the order traversed. _______, _______, _______
c) (150 points) If we perform a post-order traversal of this tree, what are the first 3 values we traverse? Give in the order traversed. _______, _______, _______
d) (1 75 points) If we perform a DFS graph traversal starting from node 12, breaking ties by going to the smallest node first, what will be the DFS pre-order? Give the whole order:
_______, _______, _______, _______, _______, _______, _______, _______, _______
e) ( 175 points) Suppose we replace 20 by some arbitrary value X such that the trinary heap is still valid (e.g. 0 would be invalid, but 33 would be valid). If we use the standard heap deletion algorithm, where can X end up after we call deleteMin exactly once? Select all that might apply. Recall that heaps can contain duplicates.
X might not be in the heap at all after deleteMin.
In the root position previously occupied by the 2.
In the position previously occupied by the 4.
In the position previously occupied by the 5.
In the position previously occupied by the 12.
In the position previously occupied by the 6.
In the position previously occupied by the 7.
In the position previously occupied by the 8.
In the position previously occupied by the 11.
In the same position, i.e. the X might not move.
_CS61B MIDTERM 2 , Fall 2022 GitHub Account #: fa 22 – s_______
- Asymptotics and ArrayDeques ( 400 points).
a) (100 points) Suppose ()= 11 + 22 + 33 + 44 ++, e.g. if = 55 , then ()= 165. Which of the following are true?
()( 1 ) ()( 1 )
()() ()()
()(^2 ) ()(N^2 )
()(^3 ) ()(N^3 )
b) (100 points) Suppose we use the following resize strategy for an ArrayDeque: When the Deque becomes too full, resize by adding 11 new entries. What is the order of growth of the runtime for the following code? Give your answer in big theta notation in terms of N.
ArrayDeque<Integer> ad = new ArrayDeque<>();
for (int i = 0; i < N; i += 1) {
ad.add(i);
}
Answer: ( )
c) (100 points) Let f(x) be defined as follows:
()={ if^ x^ is^ a^ power^ of^2
1 otherwise
Let ()=( 1 )+( 2 )+( 3 )++(). For example, if N = 8, then ()= 1 + 2 + 1 + 4 + 1 + 1 + 1 + 8 = 19. Which of the following are true about ()?
()( 1 ) ()( 1 )
()() ()()
()(^2 ) ()(N^2 )
()(^3 ) ()(N^3 )
d) (100 points) Suppose we use the following resize strategy for an ArrayDeque: When the Deque becomes too full, resize by doubling the size of the array. What is the order of growth of the runtime for the following code? Give your answer in big theta notation in terms of N.
ArrayDeque<Integer> ad = new ArrayDeque<>();
for (int i = 0; i < N; i += 1) {
ad.add(i);
}
Answer: ( )
UC BERKELEY
GitHub Account #: fa 22 - s______
- Asymptotics and Dynamic Method Selection ( 575 points).
Suppose we have the following class definitions:
public class Cheese { public String cheese; public Cheese ( String cheese) { this.cheese = cheese; }
// String’s substring runs in (length of the substring) public Cheese slice( int from, int to) { return new Cheese (cheese.substring(from, to)); }
// String’s length runs in (1) public int weight() { return cheese.length(); } }
public class Parmesan extends Cheese { public Parmesan ( String cheese) { super(cheese); } @Override public int weight() { int w = super.weight(); if (w <= 1) { return w; } Cheese mine = slice(0, w / 2); Cheese yours = slice(w / 2, w); return mine.weight() + yours.weight(); } }
Exam Sanctuary. Listen to any good music lately? Feel free to praise it here. Or draw a walrus. Or something else.
_CS61B MIDTERM 2 , Fall 2022 GitHub Account #: fa 22 – s_______
Clarification (that you might not need, but were putting it here to avoid having to clarify during the exam): The static type of slice( int from, int to) is Cheese because that is the return type specified in the method signature. The dynamic type of the returned object is the actual runtime type of the instantiated object.
a) (1 25 points) Give the tightest asymptotic runtime of the weight method in the Parmesan class in
terms of N, where N is the length of the underlying String cheese? Give your answer in big theta
notation.
Runtime: __________________
b) (1 25 points) Now, suppose we override the slice method by including the following method in
Parmesan.java:
@Override
public Cheese slice(int from, int to) {
Cheese b = super.slice(from, to);
return b;
}
What is the runtime of the weight method previously analyzed in terms of N in big theta notation?
Runtime: ___________________
c) (100 points) Now, suppose we override the slice method by including the following method in
Parmesan.java. This problem is instead of, and thus independent of, part b.
@Override
public Cheese slice( int from, int to) {
String sayCheese = cheese.substring(from, to);
Parmesan c = new Cheese (sayCheese);
return c;
}
This method will result in an error. What kind of error?
Runtime Error Compile Time Error Infinite Loop
UC BERKELEY
GitHub Account #: fa 22 - s______
d) (100 points) Now, suppose we override the slice method by including the following method in Parmesan.java. This problem is instead of, and thus independent of, parts b and c.
@Override
public Cheese slice(int from, int to) {
String sayCheese = cheese.substring(from, to);
Parmesan d = ( Parmesan ) new Cheese (sayCheese);
return d;
}
This method will result in an error. What kind of error?
Runtime Error Compile Time Error Infinite Loop
e) (1 25 points) Now, suppose we override the slice method by including the following method in Parmesan.java. This problem is instead of, and thus independent of, parts b, c, and d.
@Override
public Cheese slice(int from, int to) {
String sayCheese = cheese.substring(from, to);
Parmesan e = new Parmesan (sayCheese);
return e;
}
This method will not error. What is the asymptotic runtime of the weight method previously
analyzed in terms? You may use N to represent the length of the underlying String cheese. Give
your answer in big theta notation.
Runtime: ___________________
f) (0 points) Candidatus Desulforudis audaxviator (in part discovered by my labmate Dylan Chivian while I was in grad school) is the only species known to be alone in its ecosystem. Where was it discovered?
_CS61B MIDTERM 2 , Fall 2022 GitHub Account #: fa 22 – s_______
- Data Structures Design ( 750 points). Suppose we want to add a new operation to the LinkedListDeque from Proj1A, specifically a removeEvery( int x) operation. For simplicity, assume our LinkedListDeque is hard coded to use integer values. This method should remove all instances of x from the list. Describe an implementation of the modified LinkedListDeque class below. Your methods must complete in O(k+log N) time on average (i.e. its OK to ignore any occasional resize operation), where k is the number of xs present in the Deque, and N is the number of items in the Deque. In other words, the methods below must be no worse than linear with respect to k, and no worse than logarithmic with respect to N. Its OK if your methods are faster than the requirement. No credit will be given for nave solutions (e.g. () runtime, since this is linear with respect to N).
a) What additional instance variable do you need? List a single instance variable, including the type and name. You may use only one! You may use any Data structure from the reference sheet or any primitive type.
b) Describe below how the addFirst( int x) operation is different (if at all) from the addFirst operation in a normal LinkedListDeque. If you use your instance variable from part a, use the name you gave to that instance variable. If there are no differences, just write no difference.
c) Describe below your removeEvery( int x) operation. If you use your instance variable from part a, use the name you gave to that instance variable.
As a reminder, the LinkedListDeque class is partially defined below: public class LinkedListDeque { private Node sentinel; private int size; public void addFirst( int item) { … } public int removeFirst() { … } public int get( int index) { … } … }
Map, Set, List (note: all implement Iterable)
public interface Map < K , V > { … boolean containsKey( K key) V get( Object key) V remove( Object key) V getOrDefault( Object o, V value) void put( K key, V value) Set < K > keySet() int size() }
public interface Set
public interface List < T > { … boolean contains( Object o) void add( T item) void add( int index, T item) T get( int i) T set( int i, T item) int indexOf( Object o) boolean remove( Object o) Iterator
LinkedList implements List
ArrayList implements List
TreeSet implements Set
HashSet implements Set
TreeMap implements Map
HashMap implements Map
Note: TreeSet and TreeMap are implemented with a red black tree.
Reference Sheet
Note: For brevity, weve omitted usages
of extends and implements from class
and interface definitions.
Other handy data types:
public class Stack < T > { ...
T pop()
void push( T item)
Iterator < T > iterator()
int size()
}
public class Queue < T > { ...
T dequeue()
void enqueue( T item)
Iterator < T > iterator()
int size()
}
public class MinPQ < T > { ...
T removeSmallest()
T smallest()
void add( T item)
Iterator < T > iterator()
int size()
}
Iterator, Iterable, Comparator, Comparable:
public interface Iterator <T> { ...
boolean hasNext()
T next()
}
public interface Iterable <T> { ...
Iterator < T > iterator()
}
public interface Comparator <T> { ...
int compare( T o1, T o2)
}
public interface Comparable <T> {
int compareTo( T obj)
}