CS61B Fall 2017
UNIVERSITY OF CALIFORNIA Department of Electrical Engineering and Computer Sciences Computer Science Division
Test #2 Solutions
P. N. Hilfinger
Copyright By PowCoder代写 加微信 powcoder
READ THIS PAGE FIRST. Please do not discuss this exam with people who haven’t taken it. Your exam should contain 7 problems on 11 pages. Officially, it is worth 17 points (out of a total of 200).
This is an open-book test. You have 110 minutes to complete it. You may consult any books, notes, or other non-responsive objects available to you. You may use any program text supplied in lectures, problem sets, or solutions. Please write your answers in the spaces provided in the test. Make sure to put your name, login, and TA in the space provided below. Put your login and initials clearly on each page of this test and on any additional sheets of paper you use for your answers.
Be warned: my tests are known to cause panic. Fortunately, this reputation is entirely unjustified. Just read all the questions carefully to begin with, and first try to answer those parts about which you feel most confident. Do not be alarmed if some of the answers are obvious. Should you feel an attack of anxiety coming on, feel free to jump up and run around the outside of the building once or twice.
Your name: Login:
Login of person to your Left: Right: Discussion TA:
I pledge my honor that during this examination, I have neither given nor received assistance.
Signature:
Test #2 Login: Initials: 2
1. [3 points] The following questions concern complexity analysis. Unless otherwise stated, we are looking for asymptotic bounds (O(·), Ω(·), or Θ(·)) and want the clos- est bounds you can find (If something is O(N), don’t say that it is O(N2), even though it would be. Don’t use O(·) where Θ(·) would apply.)
(a) Consider the following sorting method on an array:
public void sinkSort(int[] A) { boolean changed;
changed = true;
for (int k = A.length-1; k > 0 && changed; k -= 1) {
changed = false;
for (int j = 0; j < k; j += 1) {
if (A[j] > A[j+1]) { /* TEST */ changed = true;
int tmp = A[j]; A[j] = A[j+1]; A[j+1] = tmp; }
What is the worst-case cost, measured by number of times the line marked /* TEST
*/ is executed, for an array of length N? Answer: Θ(N2)
(b) What is the tightest lower bound that you can give for the time cost of executing sinkSort(A) for input of size N (that is, what is the largest lower bound you can give that is true for all inputs of size N, not just the worst case)?
Answer: Ω(N )
(c) Assuming that there are ≤ N inversions in the array A, what is the worst-case cost
of sinkSort(A)? Answer: Θ(N2)
Problem continues on next page.
Test #2 Login: Initials: 3 (d) What is the worst-case time for execution of the following program as a function of
N, assuming that calls to g take constant time?
for (int k = 1; k < N; k *= 2) {
for (int j = 0; j < k; j += 1) { M = g(j, M);
Answer: Θ(N)
(e) Suppose that for every value k, g(N,k) ∈ O(1) (that is, if k is any constant, and h(N) = g(N,k), then h(N) ∈ O(1).) Exhibit a function g for which this is true, and yet p(N) = 1≤k≤N g(N, k) ∈ Θ(N2).
Answer: Let g(N,k) = k . For fixed k it is Θ(1), but p(N) is clearly N(N + 1)/2.
(f) Fill in the blanks to indicate worst-case asymptotic bounds for finding the seventh largest item by the fastest means in the following data structures, assuming each contains N items:
i. A max-heap. Answer: Θ(lgN) ii. A sorted array. Answer: Θ(1)
iii. An unsorted array. Answer: Θ(N)
iv. A perfect hash table (assume a constant-time hashing function.)
Answer: Θ(N)
Test #2 Login: Initials: 4 This page deliberately left blank.
Test #2 Login: Initials: 5
2. [4 points] In this question, we’ll implement part of a binary-search structure called IntTreeMap that maps integer keys to strings. Fill in the definition on the next page to create a IntTreeMap class that shares as much tree structure as possible among copies of the tree. It creates new tree nodes (type Node) only when necessary to ensure that modifications to one IntTreeMap do not interfere with the behavior of other IntTreeMaps. For example, suppose that A is the IntTreeMap on the left below. The notation ‘K : V ’ denotes a Node object with a key K and corresponding value V . Squares in the diagram are Java variables, and circles are IntTreeMap objects.
A: B: C: D: E:
6:A 12:F 16:G
3:Q Suppose we now execute
IntTreeMap B = new IntTreeMap(A), C = new IntTreeMap(A), D = new IntTreeMap(A), E = new IntTreeMap(A);
B.put(8, "H");
C.put(2, "R");
D.put(13, "K");
E.put(2, "X");
The intent is to end up with the structures shown for B, C, D, and E. In particular, since the insertion into E does not change the mapping of key 2, E and A can share all their nodes. Dashed lines denote pointers to previously existing structures shared with other IntTreeMaps. Fill in the method and constructor on the next pages to get this effect.
Test #2 Login: Initials: 6
public class IntTreeMap { private Node root;
private static class Node {
Node(int key0, String val0, Node left0, Node right0) {
key = key0; value = val0; left = left0; right = right0;
String value;
Node left, right;
public IntTreeMap() { root = null;
public IntTreeMap(IntTreeMap other) { root = other.root;
Test #2 Login: Initials: 7
public void put(int key, String val) { root = insert(root, key, val);
private static Node insert(Node t, int key, String val) { if (t == null) {
return new Node(key, val, null, null); } else if (key == t.key) {
if (val.equals(t.value)) { return t;
return new Node(key, val, t.left, t.right);
} else if (key < t.key) {
Node tmp = insert(t.left, key, val); if (tmp == t.left) {
return new Node(t.key, t.value, tmp, t.right); }
Node tmp = insert(t.right, key, val); if (tmp == t.right) {
return new Node(t.key, t.value, t.left, tmp); }
Test #2 Login: Initials: 8 3. [4 points] A threaded binary tree is a tree in which each node contains a pointer to the
next node of the tree in an in-order traversal, as illustrated by the dashed arrows here:
Here, the thread pointer is in addition to the tree’s child pointers, as shown in the TTree class below. (There is actually a clever way to thread a tree that avoids having an extra pointer, but we’re not using it in this problem.)
public class TTree {
public TTree(String label, TTree left, TTree right) {
this.label = label; this.left = left; this.right = right;
this.thread = null; }
public String label;
public TTree left, right, thread;
public static void inorder(TTree tree, Consumer
inorder(tree.left, visitor); visitor.action(tree); inorder(tree.right, visitor);
There is also the following utility class:
public interface Consumer
Test #2 Login: Initials: 9
We add the following threadTree method to the class TTree. Fill it in and add any other declarations needed in the class to fulfill its comment. Your solution must not use any iteration or recursion other than that provided in the other, previously implemented methods of TTree.
/** Properly thread the nodes of TREE, as described in the problem, * returning a pointer to the first node in in-order. */
public TTree threadTree(TTree tree) { Threader visitor = new Threader(); TTree.inorder(tree, visitor); return visitor.start();
private static class Threader implements Consumer
private TTree first, last;
public void action(TTree node) { if (first == null) {
first = last = node;
last.thread = node;
last = node; }
node.thread = null; }
public TTree start() { return first;
Test #2 Login: Initials: 10
4. [1 point] In the partial game tree below, maximizing nodes are denoted by △; min- imizing nodes by ▽; and P nodes represent positions with static values (as you can see, for this tree not all statically evaluated positions are at the same level.) Crossed-out edges indicate branches that are pruned by the alpha-beta algorithm, and therefore have no ef- fect on the root value. Fill in values for the unpruned nodes (△, ▽, and P) that result in exactly the indicated subtrees being pruned, and no others (you need not fill in values for any pruned subtrees). Use only values in the range 0–9, inclusive (values may be used as often as desired.)
Test #2 Login: Initials: 11
5. [1 point] Fill in the definition of patn with a Java pattern string that matches valid Java arithmetic expressions containing just identifiers, additions, multiplications, and divi- sions (no numerals, whitespace, parentheses, or other operators), and bracketed by < and >. Assume that Java identifiers consist only of letters. The pattern should capture the expression as its first capturing group, not including the <>.
static String patn = “<([a-zA-Z]+([*+/][a-zA-Z]+)*)> “; static void printFirstExpr(String S) {
Matcher m = Pattern.compile(patn).matcher(S); if (m.matches()) {
System.out.println(m.group(1));
For example if S is
“This only looks like an expression: x*y/z+q, but this is one:
x/z*foo+bar
Test #2 Login: Initials: 12 6. [1 point] Who was the only U.S. Secretary of Commerce to become President?
7. [2 points] Fill in the program below to fulfill its comment. Do not use any arithmetic operators (+, -, *, /), function calls, or conditional expressions (?:).
/** The integer value consisting of every Kth bit of X, starting with
* bit 0, packed adjacent to each other. In other words,
* bitjoftheresultisbitj*KofX. Here,bit0isthe
* least-significant (units) bit, bit 1 is the 2’s bit, etc., and
* bits 32 and beyond are 0. *
* For example, pack(83, 2) == 13, because 83 in binary is 1010011,
* and taking bits 0, 2, 4, and 6 gives 1101, which is 13 in decimal.
* Also, pack(-1, 31) == 3, because -1 is represented as 32 1-bits in
* binary, so bit 0 and bit 31 are both 1, giving 11 in binary or 3 * in decimal. */
static int pack(int x, int k) { int b, r;
while (x != 0) {
if ((x & 1) == 1) {
r = r | b;
b = b << 1;
x = x >>> k;
return r; }
Test #2 Login: Initials: 13 8. [2 points] Here are some questions concerning hashing.
(a) Consider the implementation of a hash table for a class Pixel, defined
public class Pixel {
private int _row, _col;
/** Keep track of row and column of last Pixel created. */ private static int _lastRow, _lastCol;
public Pixel(byte row, byte col) { if (row < 0 || col < 0) {
throw new IllegalArgumentException();
_lastRow = _row = row; _lastCol = _col = col; }
public boolean equals(Object other) {
Pixed p = (Pixel) other;
return _row == p._row && _col == p._col; }
public int hashCode() {
return See options below ; }
// Other methods not shown. }
For each of the following possible replacements for the blank, indicate (by completely filling in the appropriate boxes) whether the resulting hash function is valid (i.e., makes the library classes HashSet and HashMap work properly,) and, if so, whether the resulting function can always serve as a perfect hashing function (at least for a sufficiently large table).
(i) return _lastRow ^ _lastCol
(ii) return _row ^ _col
(iii) return _row * _col
(iv) return (_row << 7) + _col
Test #2 Login: Initials: 14
(b) Suppose that a certain hash table that uses open addressing contains N items and that its hash function determined a different bucket number for each of those existing N values (it’s won’t necessarily do that for other values than those in the table). Suppose furthermore that the table’s current load factor is 1/2. What is the worst- case bound for the number of equality comparisons required to insert a new value that is not currently in the table, assuming the table does not have to be resized? (We did present open-address hashing in lectures, so please don’t ask us about it now.)
Bound: Θ(N )
(c) Under the same assumptions as part (b), what bound can you place on the worst- case time to insert a value that is already in the table (which would not change the contents of the table)?
Bound: Θ(1 )
(d) Again under the same assumptions as part (b), suppose that the implementer decides to resize the table as soon as the load factor exceeds 1/2. After inserting one more node into the table, what is the worst-case bound for the next search in that table?
Bound: Θ(N )
CS61B Fall 2018
UNIVERSITY OF CALIFORNIA Department of Electrical Engineering and Computer Sciences Computer Science Division
Test #2 (revised)
P. N. Hilfinger
READ THIS PAGE FIRST. Please do not discuss this exam with people who haven’t taken it. Your exam should contain 8 problems on 13 pages. Officially, it is worth 17 points (out of a total of 200).
This is an open-book test. You have 110 minutes to complete it. You may consult any books, notes, or other non-responsive objects available to you. You may use any program text supplied in lectures, problem sets, or solutions. Please write your answers in the spaces provided in the test. Make sure to put your name, login, and TA in the space provided below. Put your login and initials clearly on each page of this test and on any additional sheets of paper you use for your answers.
Be warned: my tests are known to cause panic. Fortunately, this reputation is entirely unjustified. Just read all the questions carefully to begin with, and first try to answer those parts about which you feel most confident. Do not be alarmed if some of the answers are obvious. Should you feel an attack of anxiety coming on, feel free to jump up and run around the outside of the building once or twice.
Your name: Your SID:
Login of person to your Left: Discussion TA:
Test #1 Login: Initials: 2 1. [2 points] In this question, we will assess a variety of hashing functions for the following
class Room {
/** E.g., new Room("Cory", "521", 52, true); */
Room(String building, String roomNum, int capacity, boolean reserve) {
_building = building; _roomNum = roomNum; _capacity = capacity; _reservable = reserve;
} @Override
public int hashCode() { HASHING FUNCTION HERE }
public boolean equals(Object other) {
Room o = (Room) other;
return _building.equals(o._building) && _roomNum.equals(o._roomNum)
&& _capacity == o._capacity && _reservable == o._reservable;
// Other methods not shown.
private String _building; private String _roomNum; private int _capacity; private boolean _reservable;
Assume that the hashCode functions for the String class is uniformly distributed and deterministic on the data we deal with.
We are given a HashMap
1. map.get(x) will always or sometimes return the wrong value.
2. map.get(x) will always return the correct value, but is likely to take significantly
more than constant time.
3. map.get(x) will always return the correct value and is likely to run in constant time.
Test #1 Login: Initials: 3 Assume that the map can get arbitrarily large, as can the number of rooms in any building.
(a) return _building.hashCode(); Description: 1. ⃝ 2. 3. ⃝
(b) return _building.hashCode() + _roomNum.hashCode(); Description: 1. ⃝ 2. ⃝ 3.
(c) return _building.hashCode() + _roomNum.hashCode() + _capacity; Description: 1. ⃝ 2. ⃝ 3.
(d) return _building.hashCode() + _roomNum.hashCode() + (int) System.currentTimeMillis();
Description: 1. 2. ⃝ 3. ⃝
(e) int boolHash = _reservable ? 1 : 0; // 1 if _reservable else 0
return (_building.hashCode() + _roomNum.hashCode()) * boolHash;
Description: 1. ⃝ 2. 3. ⃝
(f) return (_building.hashCode() + _roomNum.hashCode()) >>> _capacity;
Description: 1. ⃝ 2. 3. ⃝
(g) Suppose we introduce the following bug into the Room.equals method:
public boolean equals(Object other) { return true;
Compared to the previous implementation of the .equals method, when using this new implementation, a call to the get method will (fill in the bubble for the correct answer):
⃝ Always return the correct value
Sometimes return the correct value
⃝ Never return the correct value
Test #1 Login: Initials: 4 2. [2 points] We are given the following min-heap, where each letter represents a different
Given this initial min-heap, assume we insert a new value, H.
(a) Which letter(s) could represent the smallest number in the resulting min-heap? (Fill in the squares for all that apply.)
ABCDEFGH
(b) Which letter(s) could represent the last item (rightmost on the bottom row) in the
resulting min-heap?
ABCDEFGH
(c) Which letter(s) could represent the largest item in the resulting min-heap?
ABCDEFGH
Now return to the original heap (just A–G; no H inserted). After removing the minimum
value from the original heap:
(d) Which letter(s) could represent the smallest in the resulting min-heap?
ABCDEFG
(e) Which letter(s) could represent the second-smallest number in the resulting min-
ABCDEFG
(f) Which letter(s) could be the right child of the root in the resulting min-heap?
ABCDEFG
Test #1 Login: Initials: 5
3. [5 points] The binary search tree class BSTSet on page 6 contains an incomplete implementation of a set type represented as a binary search tree whose labels are strings. In this problem, you will be completing its representation and several of its instance methods.
(a) If we add no additional instance variables to the representation, what is the asymp- totic cost of executing the size method as a function of N, the number of items in the tree?
Θ(lgN) ⃝ Θ(√N) ⃝ Θ(N) Θ(N2) ⃝ Θ(2N) ⃝
(b) If we restrict our trees to ones that are as bushy as possible, so that they have as few
levels as possible, how does the answer to part (a) change (if at all)?
Θ(lgN) ⃝ Θ(√N) ⃝ Θ(N) Θ(N2) ⃝ Θ(2N) ⃝
Problem continues on page 7
Test #1 Login: Initials: 6 public class BSTSet {
/** The empty BSTSet (all empty BSTSets are the same object). */ public static final BSTSet EMPTY = new EmptyBST();
/** Destructively add ITEM to this set, returning the modified * set. Has no effect (and returns this) if ITEM is already
* contained in the set. */
public BSTSet add(String item) { /* Implemented in part (c) */ } /** Return the number of items in this set. */
public int size() { /* implemented in parts (c) */ }
/** Return the Kth smallest item in this set. Item 0 is the
* smallest item, item 1 is the next smallest, etc. */ public String get(int k) { /* implemented in part (e) */ }
/** A new BSTSet containing only the item ITEM. */ private BSTSet(String item) {
_left = _right = EMPTY;
_item = item;
// There may be other methods that are not shown.
private static class EmptyBST extends BSTSet { @Override
public BSTSet add(String x) { /* implemented in part (d) */ } @Override
public int size() { /* implemented in part (d) */ }
public String get(int k)
{ throw new java.util.NoSuchElementException(); }
private EmptyBST() { super(null); } }
private String _item;
private BSTSet _left, _right; }
Test #1 Login: Initials: 7
(c) Implement the add and size methods in BSTSet so that size is a constant time operation and the add method executes in O(h) time, where h is the height of the tree. (The implementation of EmptyBST is in part (d)). Add any necessary instance variables to BSTSet.
public class BSTSet { …
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com