CSE12F22Exam1 :-)
1
CSE 12 F22 Exam 1
Do not begin until instructed.
This exam is closed book, closed notes. No study aids or electronic devices are allowed. Turn off your
phone and have no bags open.
You must hand in all sheets, including scratch paper, at the end of the exam.
This exam is designed to assess your understanding of topics from CSE12. You cannot communicate
with other students during the exam. You cannot discuss this exam with anyone from now until you
receive your grade on the exam. This includes posting about the exam on Piazza or elsewhere online.
Please write “I excel with integrity” in the box below:
Sign your name: _______________________________________________
Print your name: _______________________________________________
Print your email: _______________________________________________
PID: _______________________________________________
You have 45 minutes to complete the exam. Work to maximize points. Write all your answers in the
provided answer sheet on the back of this page. If you get stuck, work through other problems, and come
back to it.
Once the exam starts, you can rip off/remove the answer sheet.
In general, if you think you've spotted a typo in the exam, do your best to answer in the spirit of the
question. Keep in mind that some questions have interesting code examples with intentional bugs for you
to find as part of the question. If you ask a question during the exam, we may decline to answer. In
general, assume that any necessary libraries (JUnit, ArrayList, List, and so on) have been imported.
Stay calm – you can do this!
Do not begin until instructed.
CSE12F22Exam1 :-)
2
Write all answers below. There are 31 total points
Question 1 2 points each for implementation, 1 point each for true/false questions
A: implementation of maybePush()
B: implementation of pop()
C D
Question 2 (6 points, 1 point each) write (Both, Neither, Three, or Four)
A B C D E F
Question 3 (7 points, 1 each) Write TRUE or FALSE
A B C D E F G
Question 4 (2 points each for implementation, 1 point each for C/D)
A. implementation of prepend()
B. test for replace()
C D
Question 5 (3 points, 1 per correct)
A B C
Question 6 (3 points, 1 per correct)
A B C
CSE12F22Exam1 :-)
3
Reference
Module java.base
Package java.util
Class ArrayList
Type Parameters:
E - the type of elements in this list
All Implemented Interfaces:
Serializable, Cloneable, Iterable, Collection, List, RandomAccess
Module java.base
Package java.util
Interface List
void add(int index, E
element)
Inserts the specified element at the specified position in
this list.
boolean add(E e) Appends the specified element to the end of this list.
E get(int index) Returns the element at the specified position in this list.
int indexOf(Object o) Returns the index of the first occurrence of the specified
element in this list, or -1 if this list does not contain the
element.
E remove(int index) Removes the element at the specified position in this
list.
boolean remove(Object o) Removes the first occurrence of the specified element
from this list, if it is present.
int size() Returns the number of elements in this list.
CSE12F22Exam1 :-)
4
Question 1
Consider implementing the interface FixedLengthStack:
interface FixedLengthStack {
int getMaxElements();
int size();
void maybePush(E elt);
E pop();
}
A FixedLengthStack is like a regular Stack, but it has some fixed number of elements it can hold. If elements are
pushed (by maybePush) when the maximum number is already stored, maybePush has no effect and no element is
added. Pop should throw some exception (any exception is allowed) if the stack is empty.
class ALFLStack implements FixedLengthStack {
ArrayList contents;
final int maxElements; // the fixed maximum number of elements the stack can hold
public ALFLStack(int maxElements) {
this.contents = new ArrayList();
this.maxElements = maxElements;
}
public int size() { return this.contents.size(); }
public int getMaxElements() { return this.maxElements; }
public E pop() {
// make sure to answer on the answer sheet!
}
public void maybePush(E elt) {
// make sure to answer on the answer sheet!
}
}
A. Provide an implementation of maybePush() that matches the description above (write the method body
directly in the answer sheet).
B. Provide an implementation of pop() that matches the description above (write the method body directly in
the answer sheet).
C. True or false: If we change the interface FixedLengthStack to the version below, we will need to edit
ALFLStack to fix compile errors:
interface FixedLengthStack {
int getMaxElements();
int size();
void maybeEnqueue(Element elt);
Element dequeue();
}
D. True or false: Changing the type of the contents field from ArrayList to List would cause a compile
error.
CSE12F22Exam1 :-)
5
Question 2
Consider the following IntegerList interface, implementation, and tests:
1 interface IntegerList {
2 void add(Integer s);
3 int sumAll();
4 }
5 public class IntegerListImplementation implements IntegerList {
6 Integer[] elements;
7 int size;
8 public IntegerListImplementation() {
9 this.elements = new Integer[2];
10 this.size = 0;
11 }
12 public int sumAll() {
13 Integer toReturn = 0;
14 for(int i = 0; i < this.elements.length; i += 1) {
15 toReturn += this.elements[i];
16 }
17 return toReturn;
18 }
19 public void add(Integer item) {
20 expandCapacity();
21 this.elements[this.size] = item;
22 this.size += 1;
23 }
24 private void expandCapacity() {
25 int currentCapacity = this.elements.length;
26 If (this.size < currentCapacity) { return; }
27 Integer[] expanded = new Integer[currentCapacity * 2];
28 for(int i = 0; i < this.elements.length; i += 1) {
29 expanded[i] = this.elements[i];
30 }
31 this.elements = expanded;
32 }
1 public class TestIntegerList {
2 @Test
3 public void testSumThree() {
4 IntegerList iList = new IntegerListImplementation();
5 iList.add(1); iList.add(2); iList.add(3);
6 assertEquals(6, iList.sumAll());
7 }
8 @Test
9 public void testSumFour() {
10 IntegerList iList = new IntegerListImplementation();
11 iList.add(1); iList.add(2); iList.add(3); iList.add(4);
12 assertEquals(10, iList.sumAll());
13 }
14 }
CSE12F22Exam1 :-)
6
You run the tests, and see that testSumFour passes, and testSumThree fails with the following message:
java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because "this.elements[i]" is null
Consider each of the following changes independently: each change applied in isolation, without any of the others.
For each, write Both if after the change both tests would pass, Neither if after the change neither test would pass,
Three if after the change just testSumThree would pass, and Four if after the change just testSumFour would pass.
A. Change line 9 to this.elements = new Integer[3];
B. Change line 9 to this.elements = new Integer[4];
C. Change line 14 to use i < this.size instead of i < this.elements.length
D. Add this new line after line 29: this.size += 1; //(inside the loop)
E. Change line 27 to Integer[] expanded = new Integer[currentCapacity + 10];
F. Change line 28 to use i < this.size instead of i < this.elements.length
CSE12F22Exam1 :-)
7
Question 3
Consider this class and interface hierarchy:
interface SomeContainer {
void someMethod(String s);
int someOtherMethod();
}
class AlphaContainerImpl implements SomeContainer {
/* questions about this class body below */
}
class BetaContainerImpl implements SomeContainer {
/* questions about this class body below */
}
Answer True or False for each of the following:
A: Assuming both classes compile, this statement also compiles successfully:
SomeContainer b = new BetaContainerImpl ();
B: Assuming both classes compile, this statement also compiles successfully:
SomeContainer a = new AlphaContainerImpl ();
C: Assuming both classes compile, this statement also compiles successfully:
SomeContainer s = new SomeContainer();
D: Assuming both classes compile, this statement also compiles successfully:
AlphaContainerImpl a = new SomeContainer();
E: Any field declared in AlphaContainerImpl must be declared in BetaContainerImpl with the same name and type
F: AlphaContainerImpl and BetaContainerImpl must define at least two methods with the same name and
parameters
G: Any method declared in AlphaContainerImpl must be declared in BetaContainerImpl with the same name and
parameters
CSE12F22Exam1 :-)
Question 4
Consider these classes and tests:
class Node {
String s;
Node next;
public Node(String s, Node n) { this.s = s; this.next = n; }
}
class SList {
public final Node front;
public SList() {
this.front = new Node(null, null);
}
public void prepend(String s) {
// Write your answer in the answer sheet!
}
public void removeLast() {
Node current = this.front;
while(current.next.next != null) {
current = current.next;
}
current.next = null;
}
public String getLast() {
Node current = this.front;
while(current.next != null) {
current = current.next;
}
return current.s;
}
public void replace(String old, String s) {
Node current = this.front;
while(current.next != null) {
if (old.equals(current.next.s)) { current.next.s = s; }
current.next = current.next.next;
}
}
}
@Test
public void testSList() {
SList sl = new SList();
sl.prepend("a");
sl.prepend("b");
sl.prepend("c");
assertEquals("a", sl.getLast());
sl.removeLast();
assertEquals("b", sl.getLast());
sl.removeLast();
assertEquals("c", sl.getLast());
}
@Test
public void testReplace() {
// Write your answer in the answer sheet!
}
8
CSE12F22Exam1 :-)
9
A. Fill in an implementation of prepend() that passes the given test (and should pass other related
tests as well). You can assume that prepend can be called when the list is empty as well as when
there are elements present in the list.
B. The given version of replace() is buggy. Write the body of a test that demonstrates that replace()
is incorrectly implemented in the answer sheet. Do not use null as an input to replace, or an
element of a list, in your test.
C. Given the implementation of SList with the methods presented, would SList be more appropriate
for implementing a Stack or a Queue? Write your answer as either Stack or Queue directly in
the answer sheet.
D. How many total Node objects are created in testSList (including in all the methods it calls) before
the first use of assertEquals? Write your answer as a number directly in the answer sheet.
CSE12F22Exam1 :-)
10
Question 5
The maze below was solved with a stack worklist/DFS. The asterisks mark the path from the finish back to the start
by following previous references.
A
* start
*
*
*
finish
B
finish
* * *
*
start *
C
finish *
*
*
*
start *
A-C: In these three cases, various orders have been chosen for adding the available neighbors to the worklist. You
will answer which order matches each maze solution. For each, choose from the answers below. You may use the
answers more than once, write the four-letter abbreviation directly in the answer sheet. A reminder that on the page,
West is left, East is right, North is up, and South is down
● ESNW for East then South then North then West
● NSEW for North then South then East then West
● WSEN for West then South then East then North
● NWSE for North then West then South then East
initialize wl to be a new empty worklist (stack _or_ queue)
add the start square to wl
mark the start as visited
while wl is not empty:
let current = remove the first element from wl (pop or dequeue)
if current is the finish square
return current
else
for each neighbor of current that isn't a wall and isn't visited IN SOME ORDER
mark the neighbor as visited
set the previous of the neighbor to current
add the neighbor to the worklist (push or enqueue)
if the loop ended, return null (no path found)
Question 6
For each maze A-C in question 5, could it have been the solution from a queue worklist/BFS for any of the given
orderings? Write Yes or No directly in the answer sheet for each of A-C.
CSE12F22Exam1 :-)
Scratch Paper
11