CS61B Fall 2015
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 9 problems on 10 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 inanimate 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 lab section 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:
1. /2 2. /1 3.
6. /2 7. /3 8.
/2 4. /3 9.
Login: Right:
Test #2 Login: Initials: 2
1. [2 point] For each of the methods below, give the best case and worst case runtime in Θ(·) notation, as a function of n. Your answers should be as simple as possible, excluding unnecessary constants and lower-order terms. Assume there is no limit on the size of an int (otherwise all run times are technically constant). The answer may be infinity.
public static void first(int n) {
Best case: Θ(
(int outer = 1; outer < n; outer *= 2) { int inner;
inner = 0;
while (inner < n) {
inner++; }
); Worst case: Θ( )
public static boolean second(int[] arr) {
int n = arr.length;
for (int index1 = 0; index1 < n; index1 += 1) {
int index2 = index1 + 1; while (index2 < n) {
if (arr[index1] + arr[index2] == n) { return true;
index2 += 1; }
return false;
Best case: Θ( ); Worst case: Θ( )
Problem continues on the next page.
Login: Initials:
public static int third(int n) { return third(n, n);
public static int third(int x, int n) { if (x == 1) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += third(x - 1, n); }
return sum; }
Best case: Θ( ); Worst case: Θ( ) d. Ignore the cost of resizing the heap.
public static void fourth(PriorityQueue
for(int x : in) {
heap.add(x);
Best case: Θ(
); Worst case: Θ( )
Best case: Θ( ); Worst case: Θ( )
[1 point] Suppose that A is an array of n ints sorted into non-descending order, and suppose that B is formed from A by adding random integers between −3 and 3 to each element (so that A = [1, 4, 5, 7] might become [2, 1, 8, 4]). Give best and worst-case times for insertion sort to sort B back into non-descending order. Justify your answer.
Test #2 Login: Initials: 4
[2 points] Given the following (max-) heap,
a. Show what the heap looks like after inserting 1 and then 20 (just show the final heap; you don’t need to show it just after inserting 1).
b. Starting from the original heap (shown at the top), show what the heap looks like after removing 15.
Test #2 Login: Initials: 5 4. [1 point] Between 1 January and 1 June, a certain star seems to shift by 1/36000 degrees
against the background of very distant stars. About how far away is it?
5. [2 points] For parts (a) and (b), suppose we have a HashMap implementation that has an initial capacity of 1, and a load factor of 1. In this hashmap implementation, each resizing of the hashmap increases the number of buckets by 1. Assume we are using a good hash function—one that (miraculously) always divides our data sets evenly between the buckets. Give a Θ(·) worst-case bound for the running times of the following operations. Justify your answers.
a. Inserting n key-value pairs (assume distinct keys).
b. Looking up a key after the n insertions from part (a).
For parts (c) and (d) now suppose we have the same HashMap implementation, except resizing doubles the capacity, and we use a hash function that maps all keys to 0. Give a Θ(·) bound for the average runtime of the following operations. Justify your answers.
c. Inserting n key-value pairs (assume distinct keys).
d. Looking up a key after the n insertions from part (c).
Test #2 Login: Initials: 6
6. [2 points] Suppose the instance methods hashCode1() and hashCode2() in class A are both “good” hash functions. For each of the following computations, answer whether or not it is also guaranteed to yield a good hash value and explain why or give an example of a situation when it wouldn’t be “good.”
a. hashCode1() ^ hashCode2().
b. hashCode1() if hashCode2() is 0 and hashCode2() otherwise.
c. Generate a random number. If that number is odd, yield hashCode1() and otherwise hashCode2()
d. -hashCode1() if hashCode1() is even, and otherwise hashCode1().
Test #2 Login: Initials: 7
7. [3 points] For each of the parts below, the first lines gives the (same) initial array, and the remaining lines show the state of the array at major steps during a sort (not necessarily evenly spaced steps). For each item, indicate which algorithm can generate it: heap sort, quicksort, LSD radix sort, MSD radix sort, or insertion sort. Assume that quicksort always chooses the first element in a subsequence as the pivot; the particular partitioning algorithm might not be the stable one used in homework 8.
a. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257 257 613 095 226 442 333 572 628 421 291 093 598 658 783 997 754 093 095 226 257 442 333 572 628 421 291 613 598 658 783 997 754 093 095 226 257 291 333 421 442 572 628 613 598 658 783 997 754
b. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257 997 783 754 613 658 421 598 442 333 572 628 226 291 093 095 257 783 658 754 613 628 421 598 442 333 572 257 226 291 093 095 997 658 628 598 613 572 421 095 442 333 093 257 226 291 754 783 997
c. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257 421 291 442 572 613 783 333 093 754 095 226 997 257 658 628 598 613 421 226 628 333 442 754 257 658 572 783 291 093 095 997 598
d. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257 613 658 095 997 783 226 754 442 333 572 628 421 291 093 598 257 095 226 613 658 783 997 754 442 333 572 628 421 291 093 598 257
e. 658 613 095 997 783 226 754 442 333 572 628 421 291 093 598 257 095 093 226 291 257 333 442 421 572 598 658 613 628 783 754 997 095 093 226 257 291 333 421 442 572 598 613 628 658 754 783 997
Test #2 Login: Initials: 8 8. [3 points] A certain TrieSet class represents a node such as that shown on the left by
the linked structure shown on the right.
… … … That is, internal nodes contain the character on the edge leading from their parent (ignored for the root node), plus a pointer to their first child, plus a pointer to the next sibling node to their right. Leaf nodes also contain the entire string that they represent (their child pointers are null). Sibling nodes are linked in order of the characters on the edges leading from their parents. For simplicity, assume that the end-of-string “character”, which we’ve represented as ✷ in lecture and in DSIJ, is represented by the ASCII NUL character (in Java, ’\0’), is always the last character of a key, and only appears at the end. (Usually in Java, unlike C or C++, there is no explicit end-of-string character actually present, but for this problem, we’ll
pretend that there is).
Below and on the next page is a small part of the Java rendition of this class. You are to
fill in the two private .contains() methods. Each of them takes two parameters: the key being searched for and the node’s level in the trie (0 for the root).
public class TrieSet implements Set
_root = null;
public boolean contains(String key) {
if (_root == null) { return false;
return _root.contains(key, 0);
private Node _root;
Continues on next page
Test #2 Login: Initials: 9 Continuation of TrieSet class
private static class Node { …
/** Return true iff the subtree rooted at me contains KEY,
* assuming that I appear at level K of this trie, and that
* the length of KEY is at least K+1. */
boolean contains(String key, int k) { // FILL IN
private char _c;
private Node _firstChild; private Node _nextSibling;
private class LeafNode extends Node {
boolean contains(String key, int k) { // FILL IN
/** The (single) String represented by this leaf node. */
private String _value; }
Test #2 Login: Initials: 10 9. [2 points]
a. Show the 2-4 tree corresponding to the following red-black tree (shaded nodes are black):
b. Show an alternative red-black tree that corresponds to the same 2-4 tree as in part (a).
c. If a certain 2-4 tree has a height of H (that is, has H + 1 levels) what are the maximum and minimum heights of the corresponding red-black trees? Do not count the empty (null) nodes at the bottom of any of these trees in computing heights (so a 2-4 tree with just a root node has one level and height 0). Your answers should *not* use Θ(·) notation.
Maximum: ; Minimum:
d. Show two 2-4 trees containing values 1–15 and having maximum and minimum depths.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com