UC Berkeley – Computer Science
CS61B: Data Structures Midterm #1, Spring 2015
This test has 9 questions worth a total of 35 points. The exam is closed book, except that you are allowed to use a one page written cheat sheet. No calculators or other electronic devices are permitted. Give your answers and show your work in the space provided. Write the statement out below, and sign once you’re done with the exam.
“I have neither given nor received any assistance in the taking of this exam.”
Score
/0.5 5 /3 /1.5 6 /0
/37 /8 /58 /5 /79 /2
/17 Sub 2 /18 /35
Name:
Three-letter Login ID: ID of Person to Left: ID of Person to Right:
Exam Room (circle): Wheeler Pimentel
Score
0
1
2
3
4 Sub 1
Total
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 you’re not sure about.
Not all information provided in a problem may be useful.
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,
we’ll announce a fix. The correct answer is not ‘does not compile.’
Don’t panic! Recall that we shoot for around a 60% median. You should not expect to be
able to do all of the problems on this exam.
Optional. Mark along the line to show your feelings Before exam: [____________________]. on the spectrum betweenand. After exam: [____________________].
UC BERKELEY Login: _______
0. So it begins. (0.5 points). Write your name and ID on the front page. Circle the exam room. Write the IDs of your neighbors. Write the given statement. Sign when you’re done with the exam. Write your login in the corner of every page. Enjoy your free half point.
1. IntLists (1.5 points).
public static void main(String[] args) {
IntList a = new IntList(5, null);
System.out.println(a.head); _5__
IntList b = new IntList(9, null);
IntList c = new IntList(1, new IntList(7, b));
a.tail = c.tail;
a.tail.tail = b;
b.tail = c.tail;
IntList d = new IntList(9001, b.tail.tail);
System.out.println(d.tail.tail.tail.head); ____
System.out.println(a.tail.head); ____
c.tail.tail = c.tail;
System.out.println(a.tail.tail.tail.tail.head); ____
}
In the four blanks beside the print statements above, write the result of the print statement. The answer to the first one is already provided for you. Show your work at the bottom of this page (it may be considered for partial credit). For your reference, the definition of the IntList class is given below:
public class IntList {
private int head;
private IntList tail;
public IntList (int i, IntList n){
head = i;
tail = n; }
}
2
CS61B MIDTERM, SPRING 2015
Login: _______
2. The Ole Flitcharoo (3 points). public class Foo {
public int x, y;
public Foo (int x, int y) {
this.x = x;
this.y = y; }
public static void switcheroo (Foo a, Foo b) {
Foo temp = a;
a = b;
b = temp; }
public static void fliperoo (Foo a, Foo b) {
Foo temp = new Foo(a.x, a.y);
a.x = b.x;
a.y = b.y;
b.x = temp.x;
b.y = temp.y;
}
public static void swaperoo (Foo a, Foo b) {
Foo temp = a;
a.x = b.x;
a.y = b.y;
b.x = temp.x;
b.y = temp.y;
}
public static void main(String[] args) {
Foo foobar = new Foo(10, 20); foobar baz
Foo baz = new Foo(30, 40); x
10 20 30 40
switcheroo(foobar, baz);
fliperoo(foobar, baz);
swaperoo(foobar, baz);
}
}
y x y
Fill in the contents of the boxes above with the contents of the foobar and baz variables at the indicated points in time. The first row has been completed for you.
3
3. IntList Manipulation (5 points).
You are given the following class implementation for an IntList:
public class IntList {
public int head;
public IntList tail;
public IntList(int v, IntList s) {
head = v;
tail = s; }
/* Non-destructive. Assume skip > 0. */
public static IntList skipBy(int skip, IntList s) {
} }
if (___________________________________________) {
return ___________________________________________;
} else {
IntList p = s;
int count = skip;
while (___________________________________________) {
___________________________________________
count–; }
return new IntList(__________________________________);
}
Fill in the method skipBy to return a new IntList that contains the elements of the list s if we skipped by skip number of nodes. For example, if s was the following: [1 2 3 4 5 6 7], then calling IntList.skipBy(3, s) returns [1 4 7] and IntList.skipBy(9, s) returns [1]. Your implementation should be non-destructive (none of the original IntList objects should change). You may assume that skip > 0, and that the IntList has no cycles.
UC BERKELEY Login: _______
4
CS61B MIDTERM, SPRING 2015
Login: _______
4. Debugging (7 points).
(a) 61B student Bilbo Gargomeal runs the following code while studying for the midterm and finds that the first print statement outputs “Chocolate”. He fears the presence of evil spirits in his code.
public class IceCream {
public static String flavor;
public IceCream(String f) {
flavor = f;
}
public void melt() {
flavor = “melted ” + flavor;
}
public static void main(String[] args) {
IceCream vanilla = new IceCream(“Vanilla”);
IceCream chocolate = new IceCream(“Chocolate”);
System.out.println(vanilla.flavor);
//chocolate.melt();
//System.out.println(vanilla.flavor);
} }
Why is the print statement outputting “Chocolate” and not “Vanilla”? Give your answer in 10 words or less:
If we uncomment the two lines of code above, will the code compile? If so, what is the output of the print statement?
5
UC BERKELEY Login: _______
(b) Our hero Bilbo tries to execute the code below, and finds to his surprise that the two arrays are not considered equal. Consulting Head First Java, he reads that == returns true “if two references refer to the same object“. He remembers from lecture that an array consists of a length and N simple containers (where N = length), and reasons (correctly) that this means that the underlying objects pointed to by x and y must be different. He then runs it through the visualizer and observes the figure to the right.
public static void main(String[] args) {
int[] x = new int[]{0, 1, 2, 3, 4};
int[] y = new int[]{0, 1, 2, 3, 4};
System.out.println(x == y);
}
Given what Bilbo has learned while debugging his code, for each of the following, answer whether the code will print true, print false, or state that there is not enough information. Please use the three blanks provided to the right of each print statement. Assume that the code compiles and executes without error.
public static void main(String[] args) {
int[] x = new int[]{0, 1, 2, 3, 4};
int[] y = new int[]{0, 1, 2, 3, 4};
y = someUnknownFunction(x, y);
System.out.println(x == y);
}
public static void main(String[] args) {
int[] x = new int[]{0, 1, 2, 3, 4};
int[] y = new int[]{0, 1, 2, 3, 4};
anotherUnknownFunction(x, y);
System.out.println(x == y);
}
public static void main(String[] args) {
int[] x = new int[]{0, 1, 2, 3, 4};
int[] y = new int[]{0, 1, 2, 3, 4};
System.arraycopy(x, 0, y, 0, 5);
System.out.println(x == y);
}
____________________
____________________
____________________
6
CS61B MIDTERM, SPRING 2015
Login: _______
(c) Bilbo tries the hardMode exercise for lecture 6 and comes up with the following, where a StringNode is defined exactly like an IntNode, but the item field is of type String:
/** SentinelSSList: Similar to hardMode exercise but with Strings.
* @author Bilbo Gargomeal
*/
public class SentinelSSList {
private StringNode sent;
public SentinelSSList() {
sent = new StringNode(null, null);
}
public SentinelSSList(String x) {
sent = new StringNode(x, null);
}
public void insertFront(String x) {
sent.next = new StringNode(x, sent.next);
}
public String getFront() {
if (sent.next == null) return null;
return sent.next.item;
}
public void insertBack(String x) {
StringNode p = sent;
while (p.next != null) {
p = p.next; }
p.next = new StringNode(x, null);
}
}
The code compiles fine but the autograder is giving unhelpful messages about why it isn’t working. There is exactly one bug in this code. You want to help Bilbo but don’t want to give away the answer. Provide a simple JUnit test below that will fail on Bilbo’s code (but would pass on a correct list). For possible partial credit, also explain the bug.
@Test
public void testBilboList() {
7
UC BERKELEY Login: _______
5. Bits (3 points). What does the following function do? Give a simple description (ten words or less) of the return value in terms of the argument.
public static int mystery(int a) {
int b = 0;
for (int i = 0; i < 32; i++) {
b = b << 1;
b = b | (a & 1);
a = a >>> 1; }
return b; }
6. PNH (0 points). This game’s hardest difficulty was unlocked with the code LLLRRRLR.
This area is a designated fun zone. Perhaps you would like to draw something in the space? One possibility is some sort of mythical creature and a volcano.
8
CS61B MIDTERM, SPRING 2015
Login: _______
7. Higher Order Functions and Arrays (8 Points).
For this problem, you’ll develop a method step() that takes a 2D array of strings and replaces every string with its longest neighbor, EXCEPT the edges, which you will assume are always null and should never change. For example, if given the 2D array on the left, step will return the array on the right. We use two dashes — to represent a null pointer. The “” in row 4, column 3 is an empty string.
For the sake of allowing easy customization, your program will compare strings using an object that implements the NullSafeStringComparator interface defined below.
public interface NullSafeStringComparator {
/** Returns a negative number if s1 is ‘less than’ s2, 0 if ‘equal’,
* and a positive number otherwise. Null is considered less than
* any String. If both inputs are null, return 0. */
public int compare(String s1, String s2);
}
(a) Write a new class LengthComparator that implements NullSafeStringComparator. The LengthComparator should compare strings based on their lengths. The length of a string s can be retrieved using s.length(). Do not provide a constructor, as it is unnecessary.
(b) Complete the helper function max, which returns the maximum string of a 1D array using the StringComparator sc to judge the string. You can do this part even if you skipped part a!
public static String max(String[] a, NullSafeStringComparator sc) {
String maxStr = a[0];
for(___________________; _______________; i += 1) {
if (_________________________________________) {
___________________________;
}
}
return maxStr;
}
— — — — — —
— “cat” “cat” “dogs” “dogs” —
— “cat” “cat” “dogs” “dogs” —
— “ca” “cat” “cat” “cat” —
— — — — — —
—- — — — — — “a” “cat” “cat” “dogs” — — “a” — “cat” “a” — — “a” “ca” “” “ca” — —- — — — —
9
UC BERKELEY Login: _______
(c) Complete the step function so that it completes the task described on the previous page. You may assume that every row has the same number of columns, that the size is at least 3×3, and that the edges are all empty strings. You may not assume that the number of rows is equal to the number of columns. You should assume that the edges of the array are all null (as in the figure on the previous page). You may not add any semicolons. You may not use the ++ or — operators. Use only the blanks provided. You can complete this part even if you skipped parts a and b.
public static String[][] step(String[][] arr) {
/* Recall: All String references in stepped are null by
default, so the edges are correct on initialization. */
String[][] stepped = new String[____________][____________];
for (int i = ______; ______________________; i += 1) {
for (int j = ______; j < __________________; j += 1) {
String[] neighbors = ________________;
______________________________;
for (int k = -1; k <= 1; k += 1) {
for (int m = -1; m <= 1; m += 1) {
_______________________;
_______________________;
} }
_________________________________________;
}
}
return stepped;
}
10
CS61B MIDTERM, SPRING 2015
Login: _______
8. A Robot Renegade Cop (5 Points).
public class Robot {
public int energy = 0;
public String className = "Robot";
public void enervate(Robot r) {r.energy -= 5;}
public void reportEnergy() {System.out.println(energy);}
public void reportName() {System.out.println(className);}
}
public interface Police {
public void detain();
}
public class Robocop extends Robot implements Police {
public String className = "Robocop";
@Override public void detain() { System.out.println("halt. citizen."); }
@Override public void enervate(Robot r) {r.energy -= 20;}
@Override public void reportEnergy() {System.out.println(energy);}
@Override public void reportName() {System.out.println(className);}
}
For each line in the RobotLauncher class below, fill in the blanks. For blanks (right hand side of page), you should write out the results of the print statement on that line. If a print statement on a line will not compile, write INVALID in the blank. For the two assignment statements (lines 6 and 9), write a valid cast if required. If a cast is not required (i.e. the line will compile just fine), leave the cast blank.
1: public class RobotLauncher {
2: public static void main(String[] args) {
3: Robocop rCop = new Robocop();
4: rCop.reportEnergy();
5: rCop.detain();
6: Robot r = (_______) rCop;
7: r.reportEnergy();
8: r.detain();
9: Police p = (_______) rCop;
10: p.reportEnergy();
11: p.detain();
12: r.enervate(r); rCop.enervate(r); rCop.reportEnergy(); 12:___________
13: r.energy = 100;
14: r.enervate(rCop); rCop.enervate(rCop); r.reportEnergy();14:___________
15: r.reportName();
16: rCop.reportName();
17: rCop.className = "ketchup friend";
18: r.reportName();
19: }
20:} // Other than (maybe) print statements and casts, code compiles.
4:________0__
5:___________
7:___________
8:___________
10:___________
11:___________
15:___________
16:___________
18:___________
11
9. Static Shock (2 Points).
public class Shock {
public static int bang;
public static Shock baby;
public Shock() {
this.bang = 100;
}
public Shock (int num) {
this.bang = num;
baby = starter();
this.bang += num;
}
public static Shock starter() {
Shock gear = new Shock();
return gear;
}
public static void shrink(Shock statik) {
statik.bang -= 1;
}
public static void main(String[] args) {
Shock gear = new Shock(200); System.out.println(gear.bang); ____ shrink(gear);
shrink(starter());
System.out.println(gear.bang); ____ }
}
UC BERKELEY Login: _______
12