UC Berkeley – Computer Science BETA MIDTERM SOLUTIONS CS61B: Data Structures (Produced by TAs delirious from grading)
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.”
I have neither giving nor received any assassins in the talking of this exam.
Amundo Cow
Score
/0.5 5 /3 /1.5 6 /0
/37 /8 /58 /5 /79 /2
/17 Sub 2 /18 36 /35
Name: Amanda Chow
Three-letter Login ID: ftw ID of Person to Left: omg ID of Person to Right: lul
Exam Room (circle): Wheeler Pimentel
Score
0
1
2
3
4 Sub 1
Total
Tips:
Happy Lunar New Year!
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: [_____hungry____________]. on the spectrum betweenand. After exam: [______hungry___________].
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); _9__
System.out.println(a.tail.head); _7__
c.tail.tail = c.tail;
System.out.println(a.tail.tail.tail.tail.head); _7__
}
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
y x y
switcheroo(foobar, baz);
fliperoo(foobar, baz);
swaperoo(foobar, baz);
}
}
10 20 30 40 30 40 10 20 10 20 10 20
3
UC BERKELEY Login: _______
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. 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 (s == null) {
return null;
}
else {
IntList p = s;
int count = skip;
while (p != null && count > 0) {
p = p.tail;
count–; }
return new IntList(s.head, skipBy(skip, p)); }
} }
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.
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:
flavor is static, so instantiating chocolate changes it.
If we uncomment the two lines of code above, will the code compile? If so, what is the output of the print statement?
Yes.Prints“melted Chocolate”.
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);
}
not enough information
_______false________
_______false________
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.
7
@Test
public void testBilboList() {
SentinelSList lst = new SentinelSSList(“Dennis smells good”);
assertEquals(“Dennis smells good”, lst.getFront());
}
UC BERKELEY Login: _______
8
CS61B MIDTERM, SPRING 2015
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; // This is a logical shift.
}
return b; }
Returns the int that has the reversed binary representation of a.
An example of a reverse:
a: 00101….01
|
v
b: 10….10100
9
6. PNH (0 points). This game’s hardest difficulty was unlocked with the code LLLRRRLR.
Dance Dance Revolution 3rd Mix (must specify mix number)
This area is a designated fun zone. Perhaps you would like to draw something in the space? One
,:,SPUr ,i:qL,
. r:L …,
. PGOOEEEZ0GZ8ZENE0ZPEP0NE00S0kNP00ZXF11uU5PPPkSjYvrrr:.:iiii,.,…. .i8NX7v7:i:…
O@OGN0qEZMO80EP0NEN0PqqNqqS0NN080XF51PFEEEkP2SFjv7;r:,::rri. . i@0EGZqGGOGZN8NG0G0EN0NZ0ZEZGGZGPkFPkNEZ001SU52JLiiri:::i7:. . E8GZ8880GqNEGZZEGEGZZ0ZE80ZEEXX5FXP0ZqNkXS5JLuJLL7rii:iii.. . .
.:,iuPPquvi;:r:: :iiiFEGGE77k5ui,..
..
, ::,
…: ,::r;,:.
:vLUP0GZvY@00kFJ7: .72FkNqS0JLXSENXu: .
UC BERKELEY Login: _______
possibility is some sort of mythical creature and a volcano.
#Amanda-volcano
1ji7uLkFYu2J5FUv7ii:7vJY7i, ..:ii:,:Li. 71::r7uYLvYJL7r:::iirir;i:ii7vLir;i.,
. . . X8vrUj5uu2UvLr;7LLvvYLJuk5qF2jvYLuuirvii7rYY: .,::::.,, XGL71F5LYYYvYvjuSFX5NkPk1uJLYLjLY2Uu52220P0Fr . ..
,:iii:::: kG1v1uJ7LvJFPkP080q12YUUuJF5PXPXXX0qXFXFk2u2r. .:,,,,ii :.rYYY7JuFq0PXSk55u7iP8SvurvY2PNXNX2uYJLL2UkZGq00Gqqk0XP5k5F5uLU7i.:77:::i;;:i:i.,:,.iJ;…,,i: . MZM8ESUrvv7i:. iBF7Y7;v55551U2J1SNqNXGZO0E0NXkXqkPkXSS5SUu7irJvi:r77rririLr,:ii:iLi,::, .:.., ,….. ::i77rr: P0vv2ZqSuuUkNENGZ80ENEN0XqXEPPXPFkSSX0N5Yv7YJu7rrv77i:irru7::r;::::i ,:.: :
Fj12122j2SZ0kuuJuu7LZLJ21u1FEGOGMZZ0GEG00PXSPPXkXSPFSPkkEXUvvJYYuuujUv7i:iirL;:iri:.,:;2J. 7:::.. iUrJ11P5L, iEvjkNPZZOZEEGZZ0GENXPXNNZ0Eq0SNXXSNPXUJJjLJ5XSkuj7vir::;7;iri,,.:,..LSNJ:.,
i .:,
Oi:7i,., .
juOSq2r:vXB@BZL5@MM8OGG0GGMZ8GO8OZ8ZGZOGZPkSEZOO8PPSS2u7LLuuuJLL7i7r:,. .
Gku7vuv, Y@@M8OZOGOOM8OOMMMGO8OZOEXkqNOOOE0155FjJvuUUuYu7L177i:.. . .::i7jUkv, .LOOZG8ZO0qEGXk0Ev;72i. vi10FriYXr NBBMMO88MOMGOOMOOOMOOZGqqkZGOEEkkUF1FuLvYJY7Lvr7uLv:: . ..:vF1q00Pk5X1: :qMOOZZG8PEZGvuMOL i2j:
i U@Si:vSi .@@OMOOMBMOGMMMOMOO8ZEEPN0OOO8Eq008EGEqk5jjrvvir17i.:…::::ii::, M5Fk7LGBM7:vqB@OOOBMBMMOBMBM88OEOEZNZZMMM0EZOGZE8EqFP1F2uJ;757,::.. ..,…. v;ri:.:;5MEY8@OOMBMBMMMMBBOOGOOOG8ZGG8GZPkFSuuLJLLLLLu217;Jq7::i…. . . . BPXLL:..:;kqMMMMBMBMBMBMBMO8MMMO88MOMPSjjL7iiirri:r7ju7irUNr,:i…… …..
v7U77Ui :7iFBBBBMBMMBBMMMMMBMMOMOM0q1J7Jvrir;i:::iiri:,r5k:,i:……….
Uvu1j7r .FB@BBMBBBBBMMMBMBOMOM8OPkju2SF2u2u5S15Pku7i.r5u:,i:………. .rZM@B@B@BGu7:,.. iB@BPJ7i:rrYSi.. OOOGEqjJ :@B@MBM@B@MMMBMMOMOMOO0SUjJYuqGMM@k8@@B@@vvSqL.:ii:,.. . ….iJ@B@B@E:5MBML: .,v.
MOBBBMOZ8Y. @B@B@B@BBB@MMMBMBMBOZ5uv7irjZMBM5q@B@B8.JBM,.:i::,:…….,UuLjJYr: …. . BBX5F2UOM@OZB@M@B@B@BBMMMBMMM@BMZkjriiivJ2ujLJYF22uqGji,.:::::.. . ……. ….77::. …:i.:..
.BMOM88ZEZGEGNNEZ08G8E80ZNZ0XSSS0ZO0EX0kS2uYuJL7JLr:ri;::.. X@MMGG0Gq0NZEZZOGOGOZGN8E80kkNNGGGNNqPF5Lv7UuJLuJvi;r;:,..
.
:1ZZX00GOi7Zq0E8Sui. :08Z08EO80GGqEZEF2uL
LLZ802jFSFZB@MBB@BBB@MBMMBBMBB@BOq2rii;::::::…,ijvi…,.,::,.. :ivEU.;v1@BBM@BBB@MBMMMBMBM@B@M0uvrri:,,…:::;7::…,,.,:,. PqBZZMOj .@B@MBB@MBBBMBMBB@MBB@B@G577::,,.,.,..,,………,,,. MqP@@MO@;7B@BBB@MBB@MBBBM@B@M@B@BBFvi::,,,.,………….,,,..
r2PM@BBMBBBB@BMB@MBBBBBB@@@BZYr::.,……………..,.. i7E@G7:.7@B@M@B@M@B@MBB@MBBBBBB@B@MF;:,,………… .:r::,. @M0UL:. .S@@@BBB@B@BMM@BBM@BBM@M@B@Pv::…… … . .i1i,:,
….:::::,:,,…..:,::7:i:,.,.:::i:.::. .,.
. .. .
. ….,.. . .
.,.
..:,::ii:,::,,iL, . ., iL0r …..:77r::ir,i7i,,:. vB@BL :. . .:.i:iii :vLi:ii rL;.:XBB2:: ., ,iL7i::,:u7:;j: ,7r.iXM:.. .:. . ..
.
.::i:.
.U@MOZO88ZGPOq.iSO@L. :, vBB8OMMMMMMZ@r.iYB5. .. i@B@B@B@B@@@Bk. i:2u . .
:r: LBMGGZGG8qZEZrXGMi .:7i,
. .:ZMOZOEO80NZO2i2O@7 i,.,.
..iirvi:rSLr7iv5Yur .:., .iY, .. .::::.v7vuv7J7uOq: .. .i.YYi. … .:.
:7i.
;L7,. . .,:,;u7:v77Lu7v1Y . ,:rLYi .2X7 .,.,.
v. 7.
,.
Sr. :Lu7.
,: :
u;i7r XB@B@O v1JLju1i
.
….,..i;…:iuPuY7,iSkru2i rYvjv7:i:7i…v@B2:.
i@@BBB@@@B@OBB@MBBBMBB@M@BMYr:,………..,rNi ..
Lv1uv7LuS8@B@B@M@B@BMM@B@MBB@BBB@B@BPr:,,………,ivJ,
,:rL77UBB@B@MBBBB@@@MMB@MBB@B@B@B@B@0jr:,……,.:i;::::.,.. X21Jur5PZB@BBB@B@B@BOM@B@MBMBB@B@B@BMjYr:,,,,,::irr::,::rvYri:,.,:i;r:,…:ir,..ivSvrYLj2uNOZ,:rLi .Lij77LL:. B@@@B@MBB@B@B@B@B@BM8MM@BBBBB@M@B@B@Bq7vrrii:i:irr::…..::;rvvrrri:,… .,rv7ii;juYLkXqkqu: ivi:;:,:i.Li,. . 0kZOMEMOBB@BBB@@@B@MOMBB@MBB@B@B@B@B@B277r;ii:i:iir:. ..::i::…. ..iu2v7ii:i718ONOP27,,, i:,….i.. .. S1kPPNZ8M@B@B@B@B@BOO@B@BBBB@@B@B@B@B@BU7r;i,,,,,:7qZ1riiiiri;:::ii:::,kBMSr::i7irYFMOO7,,.ivi::.ri…:J ,: X1Pq0PG8BB@B@B@B@B@OMM@@@M@B@B@B@B@B@B@BXv7riii..,iYPPSqv ,,..::. . ;JJviiiirLri7rLMMk,7Ji ..:v:i,rY::. :. k22kqqE@B@BBB@@@B@B8M@B@BBBBB@B@B@@@B@B@BOjL;iii,:…::LuLi .rvYri,..:7v::i2G@Y:7L5qF: .iir:7:,,: kuSSqkqM@B@B@B@B@B@ZBB@@@B@B@B@B@B@B@B@B@B@0u;,…….,,:r;i7:;i:iri:,r:,.,v7.:rXM@B iu1Lv:irvirvUi7r…: uJ5S5qNBB@B@B@B@B@BOM@B@BBB@@@@@B@B@B@B@@@B@BGv:…..,::::,,.,…. .rii:,ir.,LMB@B@r .juL7LYvrriu7YLr77iOi Sj5FFF0M@B@B@B@B@BBZMB@@BMBB@B@B@B@B@B@@@@@B@B@Fi,:.,,::ir7i:…..:i7rri::i:rF@B@@@B@ iYL77Liirirvjk1q2Y7Y XFkqPPPBB@B@B@B@B@BGM@B@MMM@B@@@@@B@B@@@B@B@B@B@Mui:..:ii7vJuUJuJujUvvri:rLXB@B@B@B@B@ v577r,,vr7vLu52FuLXi 01NPNNNM@B@B@B@B@BB0@B@BBMMB@@@B@B@B@B@@@B@B@B@B@BE7i…::ii7vYLLrii:,,,:irG@B@BBP0kOBO .rJi.:i:::ruJLuJ1X0v F2kkFqkZB@B@@@B@B@MOB@@BMBG@B@B@B@B@B@B@B@B@B@B@B@B@0v. …… .. .:i:,;;i7rir7LuXBX::L7iLr..r7uYJvU5Lvvri 2JFFSPP2BB@B@B@@@BMG@B@MBMOB@B@B@B@@@B@B@B@B@@@B@B@B@BEr,. .:vuuv7vr..:rv2u21EBOuLvJ::;:r7ruvvLuFFLLLi.. LvJjJuuLF@@@B@B@B@MOM@BMMMGBB@B@B@B@B@B@B@B@B@B@BOJi…. …..,,.. .:7vrJvJuv7juuJ1USqGM@0;,:…i7,r5LuL2uUF1JLPkr:ii. BMM88E8XqB@B@B@B@B@GB@@MBM8M@B@M@B@B@B@B@B@B@Bu ..,,::,. ,.iLvUJ755JYUUuL1YJ2UE@X7rY: ,7: r7rjLuLLLUr7F0B@MZkZ:: ..,::ii:… ,uuLr77vLr: B@@@B@B@B@B@B@@@B@BOM@BMBBZBBBM@B@B@B@B@@@Bu .,….:i7r:ri::,,:::i::irPLv22JYjUYLSq7L555@@PYL772L:..:v,:;rrv7qqXM88E7:r::rvivi7:,,.., :L2vvvvr7rLLi
X2XXEkkSMBBM@B@B@B@@@B@@@@@B@B@B@B@B@B@B@B@@@B@B@B@B@@@B@B@B@B@B@B@u2Yr7v:7.:UvLur.,rYirii i,:,,. .Ji .7 Y.L.: iu: kkPNkNPPFMMMM@M@@@B@B@B@B@B@B@@@B@@@B@B@B@B@@@B@B@B@B@B@B@@@B@B@Br iqEOk7UNuv72PiLi,,.. 7:::: . ,,.MP ..:ii . ir 7i: 5uqqZ0EN00BMMB@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@@@@@B@B@B@B@B@B@5.,7YLFXYuNML2iUF;:iru.:.,:,. …,.rYui:::7 i. 1: O@BOi. 55XPqZG8E8OBO@B@@@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@@@B@B@B@N ::::ruuL5EFMqrXr r51:Jv,:.:,.. .7::::rr : .:ik5X@@BPr, qFNP0PqZOGGOBM@B@B@B@B@B@B@B@@@B@@@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B .,rri:irS1Uu5U17L :iri, i.. .,::7;::.,:: ,. ,. .i:UL758O0v:. q5XXXNS0NGNOMBB@BBB@O@@@B@B@B@B@B@B@MMB@B@B@B@B@B@B@B@B@B@B@B@@ …:ri;vLL7LOXquukk: .7, . . ,7i. . .. . r . :F@@@ZY:. .
:ir,…,iL1JuL7r77L7::: .LkL..i,::.r;.5@kMBY ,.
.
.vBq5. UBqu: .uFj2i uk12j .Ek1Fu i@Zk2j ,@8k5L OPS2U qGS5L GMX1: . ,ZZLr.
BMBB@B@B@B@B@B@BBB@MMBBM@M8M@MBM@B@B@B@B@k. :.r777rirrUOMLrL7rvv7iri7vY7u251u7JU2JUF2FOjFMFM@v:i1SN5SFUuM:vY000OquSY2EBM7,:ii,:::,r,, G8GMOMOMMMB@B@B@B@BMM@B@BB0BBBMMB@B@B@BJ,..::irr:;;i:r:rJ7,iiiiJuYiLLuUuuUJkPGMFYYuNUJuq2O8L..:::irYJGFvv2L5uUFM2Lj772Y0qk55i:iBMM;. M8BOMM@B@B@@@B@B@B@MBB@M@MOB@MMM@B@B@M: .,:ir;::i:,::…..: .,iiiL7U5rFN0PX0O55juLLjj5FULv7.iLLi::,ii:7r:u77;r7XX1UjJJLruv77SENGGv.urr. OOM@OOk7;ik@@@@@B@@BM@@BMB8B@M8MB@B@Mi.,:;ivjF7,:iirrv;:ri..:.,vr771r:2LivkuL:,25qLrYuNO;i.,i7uNPuvrLr::ivr::;:ii77vL7iir:,ii7S7r;.ukXq5uu: jjUr,,77::MkkB@B@BBMMB@MBM8B@MOO@B@Z:.:rrir::ir,:ii:,:v..i,,7,vqNvu1LYv7:iJrrrY1X1kXuri::;i7Frv2JuUrv7i,::i::.,.:7:.7L:.ii77: i7;i. iPOXS5ur: 5ur .S@MO@B@B@MBOBBBB@Z@BBZM@@B:.:;vi::,..:ii7:..:r..,iLv2LvuirkqjvrrU105NOMEv:. :,iiiv7:i7rvv7i.v :::ii,iuvi:.,:,..iJ: ::: iMB8qJJ7rii.,
5LNB@BBJ.L@JGB@B@BBBMM@MBBOM@BOM@Br .:i:i:,:i,:,:ruL775Sr:Uu;,.Lu7:ir7.:kkUkEGOBi
NOMU;7u5M@8rGMB@B@B@MMB@M@MBB@OBB@Mi i:::;:,…..::r,,:Yri:,vv :qquLLF.:i7LXG@O:
, 5@PB@EB@@B@BBG@BBBBO@B@B@B0;. .:i,. ..ii::. .,:Y, .:i.7Li:Y1::ZZ2vLG1
:,ir:. 7BqUOM@B@BBB@BOM@M@BMB@B@B@i rZ2. rv.:::..::L:ruXJ:.::Yrii:uv:kNv rZ8: ..,.. ,:0ivriiku,:…:..vi7YjkPr:JSuuJ1LYFk: :iur. 7GFvrri:.:FEZZM i,vP8PqB@B@GBB@B@B@B@MBMBM@MBB@B@@M .vLr:.5; .rYjr,:ii:ri:..:i5iL1,UkiiuM@Bi .,ri:. ..:71::r,::i:. :2uv27U57LkJuvX5j7;ii . :iivYu7:qMPuY777UB@Zuv
.i75@@B@B@B@B@B@B@BBMBMBB@M@B@@@BE :7qji..:. . .. iiru2..iLN@B@O
:..:rUMB@MBB@@@@@B@BBBBBBBBB@B@@@B@B@Z;::i:,, rJ1J: .,:.:,:..iuuuYSL:L@B@B@7 7::ivGBBMBBB@@B@B@BBB@B@BBB@B@@@@@B@@@@M7:7uSOL728X1F5r:,iv:iu0@BMM@B@B@BZ MqNkqO@MBMBB@B@@@B@B@BBB@M@B@B@B@B@B@@@B@B@5uUriJv:7ri:L2uEO8M@@@B@B@B@B@. .,.,i7uJiL7rrir::iuviv75uL75ri;iruYuXviJPqS27r:::rFOi ::j0MMGMMBMBB@B@M@B@MBBBB@B@B@B@B@B@@@B@B@B@B@B0NkvFPkN@B@B@B@MBMBMMM@B@N: ,uur7virLL7rirUkjq5LvrY1S1ri::rv:7i:,
: ijOOM8MB@B@B@B@M@B@M@M@B@B@B@B@@@B@@@B@B@B@B@B@B@B@B@B@@@BMBBMBOMMBBB2r. ,:rjUU1vvJvYu5JPSku;LU7777ruLE0LuLvv,. ,.v8MMBBM@B@B@B@BBB@B@BBB@B@B@B@B@@@B@B@B@B@B@B@B@B@BBMMM@B@@@BBOMOMBBUY. .vLrvq00uY2vJvLur:i:rJFqOUvr7urJiL2XqL;::ri,,,. vrkZO8MM@B@B@B@B@B@B@B@BBB@B@B@B@@@B@B@B@B@B@B@B@B@B@MMM@@@B@B@BMOOO@@2. .::u1LPuU77qL1U7uv:ii:LJ27rU2LFvu7Y7,:vL70ZSqGujX5Lr, uJ0GGMM@B@@@@@B@B@B@B@@@B@B@B@B@@@B@B@B@B@B@B@@@B@B@@@MBB@B@B@B@BMGBB8. :2u;r2rS7N51u7::.:i::v7YrYLS81vMGXjB82j1i :rri,iL0B@BMur..
7L8OBB@B@B@B@B@B@B@B@B@B@B@B@B@@@@@B@B@B@@@B@B@@@B@B@B@B@MON@B@B@BOBB :ir22iJPu7v20v7i.,…:ivSZYSq5LLL7UvvYLLi,.. JqMBB@BBMBMBB@B@B@@@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B@OZM@B@MMO@B:,j2rYuirYqFrJOi7u7:r:7Fk12ZkMEPujurU7r7u::i2r: FkOM@BBMMMBB@BB@@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@@@@BMMMOZOO@Bv.77vvFU2L:YMuUu7::7;:u7iJ7:2iS7OiLi:Sri:;7::7Fk7:,. qP0ZZM8OOBM@BBB@B@@@B@B@B@B@@@B@B@B@@@B@B@B@@@B@B@B@B@B@B@B@8ZEOOM@O :LFvrYGXFrYOukJi755FLr::rru:i,:,:r: ik.:u:r,,i:,.:ii P5qXE0OOMMBB@B@M@B@B@B@@@B@@@B@B@@@B@B@B@@@B@B@B@B@B@B@B@B@@@BMOMB@:,.ruLvj0uuU7FYUuuvY7uYukr :r. ..r,:k..uk:.YY7i,.:,.7OBP7. 0XXqN8Z8ZOB@M@M@B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@B@B@B@B@@@@@B@@@B@M@2 ..:rruN1:rPX77P7uvrY7Lrv; .:i, ;iiii1i::Y.YLiLJ,.,, rB@B@Mv. NS0kkk0OOGMM@B@B@B@B@B@B@B@@@B@@@B@B@@@B@B@B@B@@@@@B@B@B@B@B@B@B@B: … .iui..rUNvJui .Lvri ,:…vMF,:70Y:iv:,,::.ii: .r:2@@M@B@G: XSNZXXFOBMM@B@B@B@@@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@@@@@B@Br:Yr,r7.:L::vr7rr.::7,L;, ,r::r,:v,i LS ;U::i,:, .. :LYL15X0MB@B0:.
.,.YXi.iri:irvvui:FriY,iuLJ5u1juujYv7;.:::::. .SOOFXk0kS5JJrr. ,i7vir::vYrrri;U2Lri7iri7XXuLES0PXXMNqj. ::;:L:. i0@MZZ@MOM@NYYuu. ::iJYiF:.7urY5ii;iL27,::ivuuuJvuJSJqPJX@u…::iLL. :kGu77J7rru25UFr
..:vii.:::: i;,:,,:i:,i:LPJJYrr7ivuLvuv2U127i:, .LEX2LB@0FMGLri…:
:r:,i:::iv:,:r7L77ri:YkrvYJ7777rjY118XLiu5L7kiri5u:. ,,77:,ir:,iiv::i7i:,iUkY2L75Z2j2JLv017u0k2L;N@EPu.
.:…POv: :@B@MBB@B@
.
.,, .vi.
.,. .i@B@B@B@F.
,@@@BM@@@Br :B@B@B@B@E 2@B@B@Br
G :
. .
..
.,::: 7uvvvLLr7
rXqu2jLLv7L7Lr .iiu11YuLLv7 iFF2SSJ ::.:r
. U@MEB@B@8 …:r7u;:,. ,BG8BOOOG .:;i:. NOPOONEN :i: v@ZZNEXP :i, ,MMEGEPS ,: ivr7vvJ .. uLqUUj .. v:,::,
.2@B@B@Li:. iuZB27:.
.:77: :7r.
. r ..
MP2 ,BGX GON5
i@PFu :MSUu iOSPF
75BMMM
Gu@OOP .Z,
,rY2Z@@@ki:. .:8F,i::. …
.
::..
10
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. The neighbors of a string are the eight strings surrounding it (including diagonals). 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.
public class LengthComparator implements NullSafeStringComparator { public int compare(String s1, String s2) {
— — — — — —
— “cat” “cat” “dogs” “dogs” —
— “cat” “cat” “dogs” “dogs” —
— “ca” “cat” “cat” “cat” —
— — — — — —
— — — — — —
— “a” “cat” “cat” “dogs” —
— “a” — “cat” “a” —
— “a” “ca” “” “ca” —
— — — — — —
} }
if ((s1 == null) && (s2 == null)) return 0;
if (s1 == null) return -1;
if (s2 == null) return 1;
return s1.length() – s2.length();
11
UC BERKELEY Login: _______
(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(int i = 0; i < a.length; i += 1) {
if (sc.compare(a[i], maxStr) > 0){
maxStr = a[i];
} }
return maxStr;
}
12
CS61B MIDTERM, SPRING 2015
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 null (as in the figure on the previous page). You may not assume that the number of rows is equal to the number of columns. 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) {
String[][] stepped = new String[arr.length][arr[0].length]; for (int i = 1; i < arr.length - 1; i += 1) {
for (int j = 1; j < arr[0].length - 1; j += 1) { String[] temp = new String[9];
// temp holds all the neighbors + itself: there will
// be exactly 8 neighbors + self
int count = 0;
for (int k = -1; k <= 1; k += 1) {
for (int m = -1; m <= 1; m += 1) {
temp[count] = arr[i+k][j+m];
// Store the all the neighbors
count += 1;
} }
stepped[i][j] = max(temp, new LengthComparator()); // Here we need to construct a new LengthComparator
// every time, since it’s not static.
}
}
return stepped;
}
13
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();
13: r.energy = 100;
14: r.enervate(rCop); rCop.enervate(rCop); r.reportEnergy();14: 60
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:halt. citizen.
7:________0__
8: INVALID
10: INVALID
11:halt. citizen.
12:_____-40___
15: Robocop
16: Robocop
18: ketchup friend
UC BERKELEY Login: _______
14
CS61B MIDTERM, SPRING 2015
Login: _______
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); 300 shrink(gear);
shrink(starter()); System.out.println(gear.bang); 99
} }
Observe everything is static. Then, there will only ever be one bang variable per execution of the program. Then we only need to track changes to bang.
15