# CS代考 CS61B Fall 2016 – cscodehelp代写

CS61B Fall 2016
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 10 problems on 13 pages. Officially, it is worth 17 points (out of a total of 200).

This is an open-book test. You have two hours 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.

Test #2 Login: Initials: 2 Reference Material.
/** Binary tree. */
public class BinTree

1. [2 points] Give Θ(·) bounds for the best-case and worst-case running times of the following calls. Where there are multiple parameters to the call, you may be asked to come up with some expression, E, involving the parameters, as well as bounds on the value of E. For example, given a method call with arguments X and Y, you might choose E = X + Y and say that the worst-case running time is in Θ(E2) and the best case is in Θ(E).
Assume that print and println are constant-time operations. For Java library classes, determine time bounds based on your knowledge of the data structures that underlie them.
(a) What is the complexity of eval(a, b)? Specify a suitable expression for E involving a and b and bounds on that expression. Assume a <= b. public static void eval(int N, int M) { for (int i = N; i < M; i += 1) { System.out.println(i + " dabs."); } (b) For the same program as in part (a), what is the complexity of eval(N, 100000000) as a function of N, assuming that N ≥ 0? Best-case bound: Θ( ) Worst-case bound: Θ( ) (c) What is the complexity of eval(L, v) as a function of N = L.size()? public static void eval(LinkedList list, int value) { for (int x : list) {
if (x == value) {
for (int j = 0; j < list.size(); j += 1) { Best-case bound: Θ( ) Worst-case bound: Θ( ) where E = . System.out.println(list.get(j)); Best-case bound: Θ( ) Worst-case bound: Θ( ) Test #2 Login: Initials: 4 (d) What is the complexity of eval(A, K)? Specify a suitable expression for E involving K and A.length and bounds on that expression. Assume K>=0.
public static void eval(int[] array, int M) { if (M > 0) {
eval(array, M / 2); }
616 612 1218 10
/** Destructively modify binary search tree BST, removing all keys * that are greater than LIMIT. Returns the modified tree. */
public static BinTree trimHigh(BinTree bst, int limit) { if ( ) {
} else if (

Test #2 Login: Initials: 10 7. [2 points]
(a) Give a single expression that produces the same value as ((x/512) % 64) + 384 for integral x ≥ 0, but does not use+,-,*,/, or%.
((x/512) % 64) + 384 ==
(b) Describe succinctly what the number printed by the following program is a count of. Your answer should involve properties of x and y only (not z), and should not make any mention of the bitwise operations. Assume that all variables are of type int.
z = x ^ y; n = 0;
for (int i = 0; i < 32; i += 1) { n += 1 & z; z >>>= 1; }
System.out.println(n);
8. [1 point] Which name among the following does not belong, and why?
, , Bryant, -Taylor, Dunbar, , . Guest,

9. [1 point] Fill in the definition of patn with a Java pattern string such that the following method prints the first sequence in S of one or more decimal integer numerals separated by commas, or nothing if no such sequence exists. You may assume there are no blanks embedded in the sequences.
static String patn = ; static void printNumberList(String S) {
Matcher m = Pattern.compile(patn).matcher(S); if (m.matches()) {
System.out.println(m.group(1));
For example if S is
“The lottery numbers are 10,7,9,31,22, and yesterday’s were 19,5,29,48,30.” then printNumberList(S) should print
10,7,9,31,22

Test #2 Login: Initials: 12 10. [2 points] Consider a program for playing a two-person board game, where the board
is represented by the following Board class:
public class Board implements Comparable {
/** Return the Boards that result from taking each of the possible
* legal moves from this position. Always non-empty unless gameOver(). */ public Collection children() { … }
/** Return true iff this is won or drawn position. */
public boolean gameOver() { … }
public int compareTo(Board b) { … } }
That is, a Board is a kind of tree whose children are possible next positions in the game. Board objects are comparable; if A and B are Boards, then A is larger than B iff the position represented by A is more favorable to the first player (whom we’ll call “white.”) Just exactly how Board determines this ordering is irrelevant to this problem (you do not have to implement minimax search.)
We want an iterator over Boards that produces a sequence of Boards that would result from optimal play, starting with white’s move. That is, a new BoardIterator(b0) (where b0 must not be null) would first return b0, then the largest child, b1, of b0, then the smallest child of b1, etc. Complete the following to have this behavior.
/* These might come in handy. Both take a single argument,
* a Collection, and return the object in the collection that is * last (max) or first (min) in natural order. */
import static java.util.Collections.max; import static java.util.Collections.min;
public class BoardIterator implements Iterator {
public BoardIterator(Board startingBoard) {

Login: Initials: 13 public boolean hasNext() {
/** Assumes hasNext(). */ public Board next() {