UC Berkeley – Computer Science
CS61B: Data Structures
Midterm #1, Spring 2016
This test has 9 questions worth a total of 40 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. Write the statement out below in the blank provided and sign. You may do this before the exam begins.
“I have neither given nor received any assistance in the taking of this exam.”
________________________________________________________________________________________________ ________________________________________________________________________________________________
Points Points
0 0.5 5 5.5
1 3.56 8
2 2.57 0
3 5.58 6
4 2.59 6
Total 40
Signature: ___Alice Sheng__________
Name: Alice Sheng
SID: 18675309
Three-letter Login ID: hug Login of Person to Left: dad Login of Person to Right: mom
Exam Room: __779 Soda_________
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.
Unless otherwise stated, 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. Unless we specifically give you the option, the correct answer is not ‘does not compile.’
The last two problems are the “hard” ones.
Optional. Mark along the line to show your feelings Before exam: [____________________]. on the spectrum betweenand. After exam: [____________________].
UC BERKELEY
Login: hug
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. IntList Essentials (3.5 Points).
a) Recall the definition of the IntList class:
public class IntList {
public int val;
public IntList tail;
public IntList(int val, IntList tail) {
this.val = val;
this.tail = tail;
}
}
What will be printed by the code below? Write your answer in the three blanks provided.
public static void next1(IntList list) {
list = list.tail;
}
public static IntList next2(IntList list) {
list = list.tail;
return list;
}
public static void next3(IntList list) {
IntList temp = list;
temp = temp.tail;
}
public static void main(String[] args) {
IntList L = new IntList(1, null);
L = new IntList(2, L);
L = new IntList(3, L);
next1(L);
System.out.println(L.val); _____3_______
next2(L);
System.out.println(L.val); _____3_______
next3(L);
System.out.println(L.val); _____3_______
}
2
CS61B MIDTERM, SPRING 2016
Login: hug
b) Fill in the strangeInsertFront() method below such that both print statements at the bottom of this page print out “0 1 2 3 4″. You may have only one statement per line (do not add semi-colons, use ours).
public class IntList {
public int val;
public IntList tail;
public IntList(int val, IntList tail) {
this.val = val;
this.tail = tail;
}
public void print() {
System.out.print(val + ” “);
if (tail != null) {
tail.print();
}
}
public IntList strangeInsertFront(int x) {
this.tail = new IntList(this.val, this.tail);
this.val = x;
return this;
} }
public class P2 {
public static void main(String[] args) {
IntList L = new IntList(4, null);
L = L.strangeInsertFront(3);
L = L.strangeInsertFront(2);
L = L.strangeInsertFront(1);
IntList L2 = L;
L = L.strangeInsertFront(0);
L.print(); // should print 0 1 2 3 4
L2.print(); // should also print 0 1 2 3 4
}
}
3
2. SList Debugging and Testing (2.5 Points). Consider the SList implementation below.
public class SList {
public class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n; }
}
private static IntNode sentinel; // static sentinel is the flaw
public SList() {
sentinel = new IntNode(982734, null);
}
public void insertFront(int x) {
sentinel.next = new IntNode(x, sentinel.next);
}
public int getFront() {
if (sentinel.next == null) {
return -1;
}
return sentinel.next.item;
}
}
Write a JUnit test that fails on the code above, but would pass on a correct implementation. You may use any JUnit methods like assertEquals, assertNotEquals, assertTrue, assertFalse, etc.
@Test
public void test() {
}
SList s1 = new SList();
SList s2 = new SList();
s1.insertFront(1);
s2.insertFront(2);
assertNotEquals(s1.getFront(), s2.getFront());
assertEquals(1, s1.getFront()); /* also fails */
UC BERKELEY
Login: hug
4
CS61B MIDTERM, SPRING 2016
Login: hug
3. ArrayHorse.com (5.5 Points).
a) Consider the code below. Assume N is odd and positive.
public static int[][] genCoolGrid(int N) {
int[][] grid = new int[N][N];// Everything defaults to 0 in int arrays for (int i = 0; i <= N / 2; i += 1) {
for (int j = (N / 2) - i; j <= (N / 2) + i; j += 1) {
grid[i][j] = 8;
grid[N - 1 - i][j] = 8;
}
} return grid; /* sorry, low on space, bad style, but works! */ }
Show the return value of genCoolGrid(5) in the boxes below. Note: top left is grid[0][0]. grid[0][0] 00800 grid[0][4]
08880 88888 08880
grid[4][0] 00800 grid[4][4] Solutions that left the 0’s blank were given almost-full points.
b) Suppose we define an interface for functions on integers of a single variable called IUF. An example implementation of this interface that squares integers is shown to the right.
public interface IUF { public class Squarer implements IUF {
int apply(int x);
}}
Write a method mapColumn that destructively applies the given function to a single column of a 2D array. For example, if we pass in a Squarer object as f and 0 as c, we’d get back a copy of the grid with column 0 squared.
public static int[][] mapColumn(IUF f, int[][] m, int c) {
for(int i = 0; i < m.length; i += 1) {
m[i][c] = f.apply(m[i][c]);
}
return m; }
c) Write code such that veryCoolGrid is set equal to 5x5 coolGrid, but with the middle column squared.
You need to instantiate a new Squarer, which is a IUF. If you used
“coolGrid”, that was accepted.
int[][] veryCoolGrid = mapColumn(new Squarer(), genCoolGrid(5), 2);
5
public int apply(int x) { return x * x; }
UC BERKELEY
Login: hug
4. All Natural (2.5 points). Add a new method allNatural to the SList class. After execution, the SList should contain only numbers that are greater than or equal to zero, and in the same order that they were in before the operation began. For example, if the list were [5, -7, 2, 6, -3, 0] the list would be [5, 2, 6, 0] afterwards. As in class, the sentinel node’s value is a dummy value and is not considered part of the list. We have filled in part of the method for you; each line should be filled in with exactly one statement or variable name (you may not add any semi-colons). To give you some flexibility, you may fill in EITHER solution below. Do not fill out both. You should not use new.
public class SList {
public static class IntNode {
public int item;
public IntNode next;
public IntNode(int item, IntNode next) {
this.item = item;
this.next = next;
}
}
IntNode sentinel;
public SList() {
sentinel = new IntNode(99999, null);
}
public void insertFront(int item) {
IntNode n = new IntNode(item, sentinel.next);
sentinel.next = n;
}
public void allNatural() {
IntNode a = sentinel;
IntNode b = sentinel.next;
while (b != null) {
if (b.item >= 0) {
a.next = b;
a = b; }
b = b.next; }
a.next = null;
} …
public void allNatural() {
IntNode p = sentinel;
while(p!=null && p.next !=null){
if (p.next.item < 0) {
p.next = p.next.next;
}
p = p.next; // **see note**
}
} ...
**NOTE**: else { p = p.next } is even better because it handles consecutive negatives correctly.
Circle which of your two solutions you’d like graded. We will ONLY grade one of your solutions. Regrades will not be accepted for mis-circled responses.
LEFT RIGHT
6
CS61B MIDTERM, SPRING 2016
Login: hug
5. EggEggeggegg (5.5 points). You start with only one variable, egg, whose contents are fully described in the following box-and-pointer diagram:
a) Draw a box-and-pointer diagram if we run the following statements in the order shown:
Statement A: for (int i = 0; i < 2; i += 1) {egg.tail = egg.tail.tail;}
Statement B: egg.tail = new IntList(egg.tail.head - 1, egg.tail);
Statement C: IntList backup = egg;
Statement D: egg = egg.tail.tail;
Statement E: backup.tail = egg;
Descriptions of the above statements for explanation purposes:
A: Deletes two nodes from the tail.
B: Spawns a copy of the tail, with a value of 1 less than head. In part B, we’ll need to use this to make an IntList with a head value of 3
C: Makes a backup pointer
D: Moves egg forward twice.
E: Connects backup and egg
To make grading easier, redraw your answer below in the box-and-pointer diagram provided. You may not need all of the boxes provided. Work outside these lines will not graded. Make sure to point the variables egg and backup at the appropriate box. Do not include boxes that cannot be reached from either egg or backup.
b) Rearrangethe5statementssothatafterexecutioniscompleted,thereexistsanIntListwith exactly four elements: 1->2->3->4 (not necessarily pointed to by
CDABE First operation Second Third Fourth Final
Two alternative, correct answers: CDEAB, CDAEB
7
UC BERKELEY
Login: hug
6. Array Processing (8 Points). You are a programmer for the people’s glorious state of Oceania. Your citizens have started trying to avoid censorship by rotating their text messages. For example, suppose a citizen wants to use the banned word “light”, for example: “nice light today”. Instead, the citizen might say “ght today nice li”. It is your job to write code to remove banned words. Throughout this problem you may assume that message and banned are of length greater than zero, and that banned.length < message.length. You may also assume that k is a valid number1. Hint: for positive integers, a % b returns the remainder of dividing a by b, e.g. 7 % 3 is 1.
(a) Fill in the matches method below, which returns true if the message starting at k matches the banned word, treating the message as circular. For example, if message is ['d', 'd', 'o', 'g', 'b', 'a'] and banned is ['b', 'a', 'd'], this method will return true for k = 4, and false for all other k. You may not need all lines. If you don’t use a line, leave it blank.
private static boolean matches(char[] message, char[] banned, int k) { _________________________________________________
for (int i = __0__; i < ___banned.length___; i += 1) {
int messageIndex = ___(k + i) % message.length____; if (message[messageIndex] != banned[i]) {
______return false_____________________;
}
}
_____return true________________________;
}
(b) Complete the helper function matchStart, which returns the start index of a banned word in a message. For example, if message is ['d', 'd', 'o', 'g', 'b', 'a'] and banned is ['b', 'a', 'd'], this method should return 4, because the match begins at position 4. If there is no match, return -1. You can do this part even if you skipped part a! You may use the method from part a, even if you didn’t actually get it right. You may assume that banned words occur only once (if at all).
public static int matchStart(char[] message, char[] banned) {
for (int k = 0; k < message.length; k += 1) { if (matches(message, banned, k)) {
return k; }
}
return -1;
}
1 By valid we mean 0 ≤ k ≤ message.length – 1
8
CS61B MIDTERM, SPRING 2016
Login: hug
Finally write the filter method, which returns the original message but with the banned word removed. Assume that a banned word, if it appears at all, appears only once. You can do this part even if you skipped parts a and b. You may use your methods from part a or part b in this problem.
Some examples:
message = ['d', 'd', 'o', 'g', 'b', 'a'], banned = ['b', 'a', 'd'], return ['d', 'o', 'g']
message = ['d', 'd', 'o', 'g', 'b', 'a'], banned = ['o', 'g'], return ['d', 'd', 'b', 'a']
message = ['b', 'a', 'b', 'a', 'd', 'd', 'd', 'o', 'g'], banned = ['b', 'a', 'd'], return ['b', 'a', 'd', 'd', 'o', 'g'] 2
We gave the solution below almost full credit. In some cases, it will
properly filter out the banned, but “rotate” the array (see second example)
public static char[] filter(char[] message, char[] banned) {
int match = matchStart(message, banned);
if (match < 0) {
return message;
}
int numToCopy = message.length - banned.length;
char[] result = new char[numToCopy];
int messageIndex = (match + banned.length) % message.length;
for (int i = 0; i < numToCopy; i += 1) {
result[i] = message[(messageIndex + i) % message.length]; ____________________________________________;
}
return result;
}
The full solution for the for loop is as follows. It requires you to use insight from problem 9 (where we introduce Math.max)
for (int i = 0; i < numToCopy; i += 1) {
int d = Math.max(messageIndex - banned.length, 0);
result[(d + i) % numToCopy] = message[(messageIndex + i) % message.length]; }
7. Pip Digs Pep (0 Points). What Bay Area experimental music collective released a 1997 jingle for Pepsi, associating the ubiquitous beverage with “Old outdated software getting thrown into the trash” and a “Medicated ointment being spread on painful rash”? Negativland
2 By using this trick, citizens can defeat our censorship tool! No doubt our citizens will discover this trick. To fix this, we will simply apply the filter function multiple times.
9
UC BERKELEY
Login: hug 8. Interfaces (6 points). You may assume that you have a correct implementation of ArrayDeque and
LinkedListDeque throughout this problem, and that it implements the Deque interface.
a) Consider the Deque interface from Project 1c. Add a default method reverse that reverses the Deque.
public interface Deque
void addFirst(Item x);
boolean isEmpty();
void printDeque();
Item removeFirst();
default void reverse() {
void addLast(Item x);
int size();
Item get(int index);
Item removeLast();
There were many, MANY solutions. See below for sample solutions.
} }
default void reverseRecursive() {
// Note: if(size() != 0) is wrong if reversing two at a time if (size() > 1) {
Item tempFirst = removeFirst();
reverseRecursive();
addLast(tempFirst);
} }
default void reverseUsingArray() {
int size = size();
Item[] tmp = (Item[]) new Object[size]; for (int i = 0; i < size; i += 1) {
tmp[i] = removeLast();
}
for (int i = 0; i < size; i += 1) { addLast(tmp[i]);
} }
default void reverseUsingList(){
Deque
// Can also use: ArrayDeque
while (!isEmpty()) {
helper.addLast(removeFirst());
}
while (!helper.isEmpty()) {
addFirst(helper.removeFirst());
} }
10
CS61B MIDTERM, SPRING 2016
Login: hug
// “In place” solutions need two for loops: one to add, one to remove
// Appending to the end. Note the for loop is different
default void reverseLast2() {
}
int size = size();
for (int i = size – 1; i >= 0; i-= 1)
addLast(get(i));
for (int i = 0; i < size;
removeFirst();
i += 1)
i += 1) i += 1)
// Appending to the beginning
default void reverseFirst() {
int size = size();
for (int i = 0; i < size;
addFirst(get(i*2));
for (int i = 0; i < size;
removeLast();
}
Designated fun zone. Draw something. Leave a scent on the paper. It is up to you.
r7uvULuLUL5u: . . . . . :., . . . . . . . . . . . . . . . :77LrY7L7L7u .
:7UvuLULULUui ..,.:::.. .............. .LLuLuLuLuLFi..iiv7uuSu2L2Jjvu77:. . . . . . . . . . . . . .
.
r2vuvuLu7jvUvju0kNjULJJXuF2P2Xu5u1YY:. . . . . . . . . . . . rJuLuLu7uuqu5uqS0uu7uU57jvLrv7u2OE@O8Lr:i., . . . . . . . . . . :1J5Y2LFPGY1S0kE2kuXF2ijLYr7YEPOq8SqFOM@GOk5:, ...................
.
.
. . ..
. . .
. .
,7UX2S100OjPkZqGk02qFSYSUSJXE@ZMEOFE8@M@MBM@M@Mk:. ..................... . GuXS01EZOFNPOZ8XZSZENU0XZFGM@0OEOXZZBZMqq5MM@M@M@Sr . ... . . . . . . . . . . . . . . . . 5XXGSEEOk0POZOP0PG0OX0qOPOOM0O0O0NL7ivvu7L72SMM@M@Mk:. . . . . . . . . . . . . . . . . . . . . . . .., . . . . . . . . . . . . . . . . . . . . . .
.71@M@MMv, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , .uO@M@F: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. ,v@M@q: . ..,.. . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . , . . . . , iOM@E: . . . . ..... ... . . . . ,.. . . ,.... . ,.... ..,.. . ... . . . , .., .., . . ,.. ... ,. . :8M@E, . . ..,..., ,., . ..,.,...,...,.. , ,...,.,...,.,.. ..,.... ..... . ... . . ... ,.. ..,., . .iZM@1. ..,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,...,.,.,.,.,.,.,...,.. . ,..., ,.. ,.,.....,..... . ,i0M@i ..,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,., ,.,.,.,.. ,.,...,.,.,
8kES808NZqMEOq0XOZOP80Oq8GM0O0MG87i::., .
qEP8ZOqGEMGMqZXMGM0OqMZONMZMZO08u;.,
MXGEM080MEMq8kOZMEO0O0ONMGMZOEMk7,:,,
EGEMEO0OEMN8P8GMZO0OZOPM8MGMEMPY:i::..
MqM0O0OEMEO0OZBGM0OZMqOGMZM8MXuirii.:..
ZOEMEMEMGO0OEMGMEMEM08ZBGMGBF1;7:i,:.. .
M0MZMEMZMEOEM8MGMZMEONMOMEME2vv:i::..
ZMEMEMZMEO0MGMGMEMZMEO8MGME57L:i,:,, .
MEMEMEMEMEOZMGMGMEMNOEMZMEXr7,:..., . .
GMZMEMZMZMEMGMGMEMZM0MGMEZLjr7iriririi,, . . .
MEMGMGMZMZMGMGMGMGM0MGMZMSkjUJ51P1ENMZOXF7r::.... .., . . U@...:.:.:.:.:.:.:.,.:.:.:.:.:.:.:.:.:.:.:.:.:.,.:.,.,.,.,.:.:.:.:.:.,.:.:.:.:.,.,.,.,.,.: 8OGMGMZMZM8MZMZMZMEOZM8M0GX0UP2FLjr7;YLkXSvvii.,.,.::rrPOGj2q: :.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.,.,.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.,.:.:.:.:.:.:.:.:.:.. M0MGM GMG MGB GBZM ZMG MZM GMZO N0U 1vvi i.. :: ri7 i;:: .,, riJ Lv:i i1L :.: .:.: .:. :.:. :.: .:. :.:. :.: . :.,.: .:. :.: .:.: .:. :.: .:.: .:. :.:. :.: .:. :.:. :.: .:.: .:. :.: .:.: GOGB8MGMGM8B8BZMZMZMGMGOXXYj77ii::.. .:ri7ir::,iir:. Ui,,:.:.:.:.:.:.:.:.:.:.:.:,:.:.:.:.:.:.:.:,:,:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.. MGMGMGMGMGMZM8MGMZMGM8MkPu1vY;7rL7UYurvi: ::7i7ir:::r::.. .i.:,:.:.:.:,:.:,:,:::,:.:,:,:,:,:,:,:,:,:,:,:.:.:,:.:.:.:.:.:.:.:.:,:.:.:.:.:.:.:.:.:.: ZM8MG MOB GMG B8MZ B8M 8MO BqEF kj5 Y5SO O@M @M@ M@GJ :ri 7ii. ,.: :ri 7J5J Fr: .:. :,:. :,: ,:,: ,:, :,: ,:,: ,:, : ,:,:, :.: .:. :,:, :,: ,:, :,:, :,: ,:,: .:, :,: .:.: ,:. :.:. :.: .:, :,:, , BGB8MOM8B8B8BGMGB8M8BqNk0FNkMM@M@ZBM@MNrMM5:ri7:. .iiJM@M@M@M7,:.:,:,:,:,:,:::::,i,:,:,:,:,:,:,:,:,:,:,:,:,:,:,:,:,:,:.:,:.:,:,:,:.:,:,:,:,:,:.:,:,:.
.
. . .
. . . . .
............. . . . . . . . . . . . . .
.:OMB ..,.:.,.,.:.,.,.:.:.:.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.. ,@Mr ,.:.:.:.:.:.:.,.,.,.:.:.:.,.,.,.,.,.,.,.,.,.,.:.,.,.:.,.,.,.,.,.,.,.,.,.:.:.,.,.,.,.,.,
. .@X..:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.,.,.:.:.:.:.,.:.:.,.,.,.,.,.:.:.:.,.:.,.:.:.:.:.:.:.:..
8M8MG B8M 8M8 BGB8 M8B O@8 kuFU k5X S011 vYr 7:: .:,r ri, i:r: BGMGMOBOM8M8MGMGM8BMZLLrvrLrvrYvUY2YULYr7:: ,:i:7: OMOBOB8MOBOB8M8B8B8B2Liri;:i:i:i,:,,.. . . ..::rivi.
MGBOBOB8BO@OB8M8BOBZ57vir:i,:,: .
8MOB8BOB8BOM8BOB8BO8YYrvir:i::,:..
MG@OBOB8BOBOB8BO@OBFULY77i7ir:i::..
OMOBOBOBOBOBOB8BM@ZPjULJ7Lr7ir:i:i.:..
BGBOBOBOBOBOBOBOBOO15Y2vj7Lrvi7ir:i,:.: ..::77;,. .,ri;,. .iv::.. .ir:r:r:r:r:r:i:i:i:i:i:i:r:;:r:, . ..:.7U82L:r:: . ,:i:i:i:i:i:i:i:::i:i.
.
.,i:7rLi. . .:;i7i7:.
,ir:i:i:i:i:i:i:i:i:i:i:i:i:i:i::,i:::i:iir:;:i,i:i:i:::i:i,::i:::i,i:i,i::,:::,i,::i.
.iL 8U1L r7k vi, :::, i:i :::i :i: :,: ::,i :i, : ,:,:, :,: ,:, :,:, :,: ,:, :,:, :,: ,:,: ,:, :,: ,:,: ,:, :,:, :,: ::, :,:: , .iiL7L7r:i:i:i:i:i:i::,i:i:i:i:i:i,::i::,:,:,:,:,:,i::,:,:::,:,:,:,:::,:,:::,:,:,:,:,:,:,:,::i:i. .,iir:: :ir:i:i:i:i:i,i:i:i:i:i:i:i::::,:::,:,i,:,::i:i:i:i::,:::,:,:::,i::::,:::,:,:::,:,::i::
,ir:i:i:;:;:i:i:i:i:i:i:i:i:i:i:i:i:;:;:i . ii;:r:i:r:r:i:i:i:i:i:i:i:i:i:i:i:i..
.,i:i:i:i:i:i:i:i:i:i:i:i:i:i:::i:i:: ..::i:i:r:;:r:;:i:i:i:i:i:i:i:i:i:i:i. :ivL7:i:;,:.::i,:,i:i:i:i:i:i:i:i:i:i:i::
::7;vi;,.
.,r;7i77vii. .,: . . ..7:i:r:r:r:i:i:i:i:i:i:i:i:i:i:ri: . .
OMOBOBOBOBOBOBOBMBkkJ2J2L2vY7Lrvirii::.:,i:7YF77::.iruLYii.:k2ii,,.;irir:r:rir:r:i:;:i:;:;:ri7i;.. BGBOB8BOBOBOB8BO@GNuFJ1j5J2Lu7Lrv;7ir:i:riv2MGOkZ8@MMqZkNuYuMk5r7:::r:r:riririr:;:;:;:;:r:rir:,
OMOBO BOB OBO BOB8 @MO kku 5uFu Su1 LuvJ rvr 7i7 iri7 iJu NkEq MGB M@E E5;: vvF jur r:ri rir irir iri r:; :r:; :r: r :, BGBOBOBOBOBOBOBO@NP1FuFuSUFu2Y2LJ7Lrvr7;7:rrL7Lrvrv7ujL:i.,iL7u7Y77iririririri7iririr:r:i:,
OMOBOBOBO@OBOB8@M81Xu5u5uX2XuFJ2LuvY7Lr7i;i7rY7Yr7ir:i,:.. i7LrL7v:riririri7i7i7ir:r:ri7r7:,.. BG@OBOBOBOBOBOBO@qXUFY2Y1uSUSu1YULu7L7LiriL7Lr7i7;v7Yrr:i::.v7vir:ri7i7i7i7i7i7i7iririYLUri,:.. ..,.,. ,,ii7i7iii5E@M@Z7. . : . ::i:i:i:i:i:i:i:i. OBOBOBOBOBOBOB8@M825j2LUY5Y1Y1YULu7Liv77iv7vr7rYvUUqkZ0PFO227jr;,ri7iriririri7;7iriri7i7ii::.:.:,i:rii:: ,,rivrviYG@M@q7. ,:rr7:: :,:.:.,., ,.. ,..
..: :ii LvUr r:: ,i:r i7; vvU YS1X F ..::7rvr772JSFqGGEMOMOB8BEMEMEG .. ,,r; vr7 rLY PSOG ON8 qGPE SEk ZXE kEkE 1 ,,i:7r7rYuGO@M@M@G8kEkEkZk0kESqFNSP BG@OBOBM@MBOBOM8MO@EZSP2Su5YuvJ7j7Yr7ivrvrL7L7jvULu7Lr7i7i;,,:FM@Mv:7rYvuJkPBY7ir:i:i:i:i:i:;ir:i:i:i:i,i:rir::.. ::7rvi7LGM@M@Mu:,,58Ok0SZX0k0k0F0kE5 OBOBO BO@ OBM @OB8 M8M OBE GkN5 P2S jULu LUL J7L rvrL 7J7 Y7Y7 L7J r7: r:i: :.2 M@O @ZBM @M@ M@M@ v:: i:i :i:i :i: i :i:i: rir :ri i:i: i:i :i: ri7r Y77 rqM@ M@M F, 28 ZkZX ZXZ SZS 0kEX q @OBO@O@MBOBMBOMEM8BOBE8PZk05X15u1J5uUvLvu7L7Jvj7Lrvr7:i:;::.iM@OBOM0MZMO@MS,::i:i:i:i:i:i:i:i:i:ririi:i:i:ii7rY7Y7L7vU@M@Gu. .iiLi,.ZqEk0XZkZX0kESE5 OMOBOBMBOBO@M@8M8BGBO@OMqGXZkZFXUXUXU5LjvuvJvuvJ7Lr7iririr:,7@MBZ@GO0MM@8r :,i,:,i:i:i:i:i:;:r:riri;:;:i:ri7rL7J7vir:1jr. ::7rJvu7rF8k0S0SEXEXEkEXN BGBOBOBOBO@M@OB8M8B8BO@OMEOqGXESqUP5P5SJULuLULuLuvLrvrvrr:i.kM@8OOM0MMB7,.:,:,:,:,::i::,i:i:riri;:;:rir:ri7;vrvr7::., ..i:ri7rLvuY1UGk0SEXES0kES0kE5 OMOB8@OBMBO@O@OMEM8B8BO@OBGMqZk05P1P5N5N21LUL1J1J2YuvJ77rv::E@MMPBMBM2.,,i:i:i,:,:,:,i:::i:i:rir:i:;:riri7rvrvr7i;,:.:,i:7rL7JvjvF50qOkES0kEPESEkEk0Sq BZBOB O@M @MB OBO@ OMZ MOB O@OB OBO MZOP EX0 FNF qSN1 5J5 uFu5 uFu Su1 JUL7 v@M @0O 8@Oi .i: r:i: i:i ,:, :,:: i,: , i:i:r :;: r:r i7;v rL7 L7L 7J7v ;7; 7rL7 JLu L52 0qOq GPE SES0 SZS EkE S0kE F 8MOB8BOBM@MBO@M@OMGMOBOBOB8B8B8MZONZkEF0Sq5P1k2X2X1X1NSEXZ5MM@8O0@Mv:7;7iri;:;:i::,::i:::i:i:iir:ri7ivrLrvrvrv7JLu7Yr7rLvuvuuE0ONGPZXZXZkZXZkEXZSEXGXN MZBOB OBO BO@ OBO@ MBG MGB OBOB OBO BOBM @OM ZON 8PGX ZSE k050 S0k ZqO EM0M O@M MEM MEiv 7Lr 7ir: ri; :i: i:i: i:i : i:i:7 iri 7;v rLrv rv; 7r7 rvrv rL7 uLUv SG@ E8q ZPZk ZkZ XZSE kZX Zk0 S0SZ S 8MGBO BOB O@O @O@M @MB 8MG MOBO BOB 8M8B O@M @OB 8MEO q8q OqZP OEM ZMZ MEMG @MM 0MG BYL7 Lr7 irir ir: i:i :i:i :i: i :i:ri 7i7 ;vr Lrvr v;7 i7i 7rJL UY2 uuYG M@M MkZ XZXZ XZX ZXEk ZXZ kZP EXZX N BZM8B 8BO BOB OBO@ M@O BGM EBOB OMG M8B8 MGM GMG M8MG @M@ OBO@ M@0 OEO EM0M M@0 OEB XuvL rv; 7iri 7ii :i: i:i: i:i : i:ri7 ;7r v7L 7Lrv rvi 7i7 iv7U Y2L Fq@M @OB NZk EkEF EkN F0SN kEF EkZ SNFN 2 8M8MO BOB OBM @OBO @OB MBG MGBO BOM ZM8B 8B8 MZM ZOE@ M@M @O@M @0O 0OE M0OO @0M EMM Xvj7 Lr7 irir :r: i:i :i:i :i: i :i:ri 7rv rv; 7rvr 7rv ;7r L7Jv uuG M@MB EOP 80O 0ONG P8q 808q O0O N8q ONOE O BZB8BOBO@O@O@MBMBO@MM8MGBOBOBEB8B8MZMGOG@M@GMZ@M8kZN8N8qOO@EOEM8MJY7Lr7i7ir:r:;:;:i:i:i:i:i:ririri7;7i7rvrv7JvuvUv5P@M@OMEMGMZMZO080ON80Oq8PZPZqEq@M@O 8M8MG MOB OBO BOBM @O@ M@O MGMO B8B OMEM 8BG MGM EBOM EOG @MOq OGB GM8 MO@O B8B O@8 J7Y7 v;7 ir:r :r: r:r :i:i :;: i :riri rir i7i 7ivr L7J L2J UuZM @OM OBZ0 qGS Ek0 FqkE kGF 0FP5 q5P 50F PGBG M @EB8MGBOBOBOBO@M@M@O@OMOBOBOBOMZMGMOOqBOBO@M@8M8BM@O@OBM@8MO@8BM87J7Lr7irii:;:;:i:r:i:;:i:rir:ririri7;v7JvuLUv2XBMBGMGM8MPZPESEk0S0S0qOXZSEkEFqSZF8OBE OM8BG MGB OBO BOBO BO@ OBO BOBO BOB OBOM ZMG MXM M@M@ OM0 G0MG B8B GMO @8MG MZB O@2 L7Lr 7ir i;:i :i: ;:r :i:i :i: r iriri ri7 i7r v7Jv uLu LkZ @8MZ MEM ZMZ8 XZk EXZ S0S0 SZE qk0S NS0 S0k NS@8 O BGB8M ZMG BOB OBOB O@M BO@ O@OB OBO B8BO BZM 0OM @OBG @OM q8qO qO0 OM@ ZOGM ZMZ BM5 7L7L r7i r:i: i:r :r: ;:i: i:; i 7irir iri 7rL 7uLU Yuj Z8@ ZMZO 0O0 ONM0 ZPE kEX ZS0k ZXZ S0SE k0k 0k0 Fq8B E OMGM8 MZM OB8 BOBO BOB M@M BO@O @OB OBOM OB8 MZ@ OB8M O@O Mq8N 8XM MBE 8EME MEM OOv LrLr vir :;:i :;: r:; :r:i :;: r iriri 7;v rv7 uLUY PqB E8E M0Oq OqO 0OP8 NGX ZXZ XZXE SZX Ek0k ESE SES E18O M BGMGB 8MG BOB OBOB OBO BO@ OBOB OBO BOBO B8M OB8 M8B8 BM@ Z8qO G@M MX8 ZM0O ZMZ @XY 7vrv rvi r:i: ;:i :;: r:i: i:r : riri7 ;7r LrY LSkO 8B8 O0O q8qO q8E 8080 OXG PEX ZXZk ZXE XEkE XGX GXZ XNSB N OM8M8BGB8BOBOBO@OBO@O@OBOBOBO@OBOMZM8BOMGM0@MBGBM@OMPG0O0O0OEMOS7LrLrvr7ii:i:i:;:i:;:;:;:r:r:ri7;7rvL08BGMZO0O0ONOXEXOEOEMEOqGqGPGPEXZXEkEkZXGXZXZk0G8 @8B8B 8MG BOB OBOB OBO @OB O@OB OBO @OBO BOM GM8 @OBZ MZB M@OM 0OE O0O POPG POG MJj 7vrv rvr 7ii: i:r :ri riri r:r i r:i:; :ri rYM PGX8 NO0 O0O 08NG F0N O0OE OqG N8P GXGP ZkG qZkZ kZX ZXE XZSM 0 ZM8BG B8M 8MO BOBO BOB OBM @O@O BOB OBOB OBO BGM GM8B GM8 BZ8N OGM EO0 ONM0 ONM PU7 L;7i 7i7 ir:i :;: rir irir iri r :i:i: i:i :BM ON8P 80M 0Oq 8qOq GS8 0O0O EZq 8PG PGPG PZX 8PGP ZPE PGX ZXNN M MZB8MGM8M8BOBOBOBOBOBOBM@OBMBOBO@OB8MGMZMZOGBOMEOEMEMEM0O0OZOGO0ZFkuU7L;r:i:::::i:;:;ir:r:;:i:i:i,7MBEMEGq8qONONO0ON8NO0OEMqGq8N8qOq8X8qONGP8PGkZSZ5GG GM8BO MZM 8BO BOBO BOB OBO BOBO BO@ OBOB OBO BOM GM0M EMG BGMZ MGM ZME OEME MG@ M@M @M@M @M@ 8OPE u27 vi; :i:i :i: i :i:i, :,: i@Z OEME 8XZ 5NS Zq8N O0O 0O0O ZOq ON8 NOqO q8N ONOq GPG qGX 0kZk M MEBOB8M8B8BOBOBOBOB8BOBOBOBO@OBOBOBOBOB8M08qOEMZMEM8MGM0MEMZBO@M@M@M@M@M@M@M@M@M@OMN055LYrr:r::.:.vMON8NOEM0GkGPZPGPEqO0O0M08NON8N8qONONOqGNZPGXZkNX0E EOGB8M8M8B8MOB8BOBOBOBO@OBOBOBOBOBOBO@OBOBGMEMqONOEM8MEMGMEM8@OBO@O@O@M@O@M@M@M@M@M@M@M@M@M@OBZGPNEMP8PGP8NO0ZqONGPGPOqO08EM0 8NOqOEOq8q8qONGPGPZXGXGPO M0MZB 8B8 B8B 8BOB OBO BOB OBM@ O@M @OBO @OB OBO BO@O @OB GMEO ZMZ MGM GMZO 8BO @O@ OBOB OBO @O@O BO@ M@M @O@O @M@ M @M@M@ M@M @GM qZXZ XNk ZXO EON8 NO0 8qM0 MZO 0Oq O0Oq Oq8 NGPG P8P 8PG qOPG P E8EMZ MZM ZMZ MGBO MOB OBO BOBO BOB OBOB 8MG MOB OB8B ZM8 BGME OGM GMG OZM0 MGM 8MO BGBO M8M OM8B 8M8 BOB 8BOB 8BG B 8B8B8 B8M 8BN X5XU q5q 1k5 NkGX ZkZ kZq8 0ON Oq8 q8qG q8P GPZP GPZ P8P GP8P E
BOBOB OBO @OB OB8B O@0 PuF j5JU LJv uvj7 JvY rrr Lrv7 uuq X8XP 2kY YL5 77i7 L27 r,i irir iri 7i7i 7i7 i7i rir: ::i : i::,: :rr Jrr ir:i :i: i:; :uM@ Xv.
OBOBOBOBM@OBOB8BMM5SuFu5Yj7J7L7L7L77:vvYLSPMMMqEFkJv:i::,ri::7::7L:7iriri7i7iri7i7ir:i:i:i::,::i:rr7ivrvr;.,.. . @8BOB OBM BO@ OBOB O@O G2k uFu1 Lj7 L7L7 Lrv iii L72L Li7 7L7j Y2J 17Y vJri .:i r,@ 5iir i7i 7i7i 7i7 ;vr r:i: r:i : i:::i :i: ;:r i7ir ,, OBOBO@O@O@OBOB8M8BGEFXuFj1Lu7L7Y7Lr7:;i7rvr7ivrL;7i7rY7Y77::.i:SMM,::i:::::i:7r7ir:i:i:i:i:i:i:i:i:i:i:i,:.. . .
. ..ivFLLii::.. ..i:i.. . .:i:i:i:i:i:i:i:i:i:: . ....7u2ii::.. ..::iivi:.::i:;:i:i:i:i:i:i:i:i:i. ,. ,,ju v:i ,. .. :,: :i:r ;7: r7S SGi: :i: i:i: i:i :i: i:i: : :i:.. ..::r:rir:rr25@M@OOvi:i:i:i:i:i:i:i:i:i, ,,ririr:r7X8@M@Ni ..i:i:i:i:i:i:i:i:i::
11
UC BERKELEY
Login: hug
b) Suppose we add another default method to the Deque interface:
A: default void append(Deque
B: public void append(ArrayDeque
@Override
C: public void append(Deque
D: public void prepend(Deque
E: public void prepend(ArrayDeque
Consider the code below. For each call to append or prepend, tell us what happens by circling exactly one of the provided answers. If you circle a letter (A, B, C, D, or E), you are saying that the method with that label is called. If you circle compile-error you are saying this line will not compile. If you circle runtime-error, you are saying the code will compile, but will crash when this line is reached. Some possibilities may not occur (e.g. there may actually be no compiler errors).
When you’re done, you should have circled exactly 8 items.
public class DMS {
public static void main(String[] args) {
} }
Deque
d.addLast(10);
d.addLast(20);
ArrayDeque
ad.addLast(30);
ad.addLast(40);
d.prepend(d); Compile-Error Runtime-Error A B C D E d.prepend(ad); Compile-Error Runtime-Error A B C D E ad.prepend(d); Compile-Error Runtime-Error A B C D E ad.prepend(ad); Compile-Error Runtime-Error A B C D E
ad.append(d); Compile-Error Runtime-Error A B C D E ad.append(ad); Compile-Error Runtime-Error A B C D E d.append(d); Compile-Error Runtime-Error A B C D E d.append(ad); Compile-Error Runtime-Error A B C D E
/* Did you circle 8 things, one per line? If not, go circle 8 things. */
12
CS61B MIDTERM, SPRING 2016
Login: hug
9. Dynamic Method Selection and Inheritance (6 points). Modify the code below so that the max method works properly. Assume all numbers inserted into a DMSList are positive. You may not change anything in the given code. You may only fill in blanks. You may not need all blanks.
public class DMSList {
private IntNode sentinel;
public DMSList() {
sentinel = new IntNode(-1000, new LastIntNode());
}
public class IntNode {
public int item; /* Equivalent of first */
public IntNode next; /* Equivalent of rest */
public IntNode(int i, IntNode h) {
item = i;
next = h; }
public int max() {
return Math.max(item, next.max());
} }
public class LastIntNode extends IntNode { public LastIntNode() {
super(0, null);
}
@Override
public int max() {
return 0; }
}
public void insertFront(int x) {
sentinel.next = new IntNode(x, sentinel.next);
}
public int max() {
return sentinel.next.max();
}
public static void main(String[] args) {
DMSList dmsl = new DMSList ();
dmsl.insertFront(5);
dmsl.insertFront(10);
dmsl.insertFront(20);
System.out.println(dmsl.max());/* should print 20 */
}
} /*endofclass*/ /*endoftest,boo*/
13