CS61B Fall 2017
UNIVERSITY OF CALIFORNIA Department of Electrical Engineering and Computer Sciences Computer Science Division
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 14 pages. Officially, it is worth 17 points (out of a total of 200).
Copyright By PowCoder代写 加微信 powcoder
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 of person to your Left: Discussion TA:
Login: Right:
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:
(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: Ω( )
(c) Assuming that there are ≤ N inversions in the array A, what is the worst-case cost
of sinkSort(A)? Answer:
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);
(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) = .
(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:
– A max-heap. Answer:
– A sorted array. Answer:
– An unsorted array. Answer:
– A perfect hash table (assume a constant-time hashing function.) Answer:
Test #2 Login: Initials: 4
Test #2 Login: Initials: 5
2. [4 points] In this question, we’ll implement part of a binary-search structure called TreeMap that maps integer keys to strings. Fill in the definition on the next page to create a TreeMap 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 insure that modifications to one TreeMap do not interfere with the behavior of other TreeMaps. For example, suppose that A is the TreeMap 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 TreeMap objects.
A: B: C: D: E:
6:A 12:F 16:G
3:Q Suppose we now execute
TreeMap B = new TreeMap(A), C = new TreeMap(A), D = new TreeMap(A), E = new TreeMap(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 TreeMaps. Fill in the method and constructor on the next pages to get this effect.
Test #2 Login: Initials: 6
public class TreeMap {
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 TreeMap() { root = null;
public TreeMap(TreeMap 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 ___________________________________________________; } else if (key == t.key) {
if (___________________________________________________) {
return _________________________________________________;
} else if (___________________________________________________) {
Node tmp = insert(__________________________________________);
if (________________________________________________________) { return t;
return ___________________________________________________;
Node tmp = insert(___________________________________________);
if (________________________________________________________) { return t;
return ____________________________________________________;
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) {
_______________________________________________________________;
_______________________________________________________________;
return ________________________________________________________;
// Put other necessary definitions here, without using loops or recursion.
Test #2 Login: Initials: 10
4. [1 point] In the partial game tree below, maximizing nodes are denoted by △; min- imizing nodes by ▽; and ✷ 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 ✷) 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 = ” “; 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 (?:).
/**Theintegervalueinwhichbitjisbitj*KofX. Here,bit0is
* the least-significant (units) bit, bit 1 is the 2’s bit, etc. 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 all 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;
b = ______________________;
while (______________________________) {
if (_____________________________) {
r = ____________________________;
b = _______________________________;
x = _______________________________;
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: Θ( )
(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: Θ( )
(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 nore node into the table, what is the worst-case bound for the next search in that table?
Bound: Θ( )
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com