Western University

Department of Computer Science

CS1027B Computer Science Fundamentals II

Midterm Exam
March 2, 2024

Please print your name CLEARLY, otherwise Gradescope will not understand it.

Last Name:

First Name:

Student Number:

Section Number (1-Morey, 2-Sarlo, 3-Solis-Oba):

Instructions

ˆ Fill in your name, student number, and section.

ˆ The midterm is 2 hours in length.
ˆ The midterm has 12 pages and 26 questions worth a total of 110 marks. 10 of these marks are bonus
(your mark will not be divided by 110 at the end).
ˆ The first part of the exam consists of multiple choice questions. For each question DARKLY FILL
IN ONLY ONE ANSWER BUBBLE.
ˆ For the second part of the exam, answer each question ONLY IN THE SPACE PROVIDED.
ˆ When you are done, raise your hand and one of the TAs will collect your exam.
ˆ Remain in your seat when you finish until a TA collects your exam.
ˆ Do not write on or deface the barcodes at the top of the exam pages.
ˆ Do not turn this page until instructed to begin.

1
Part I. Multiple Choice Questions
For each multiple choice question, darkly fill in ONLY ONE answer bubble.
1. (2 marks) Consider the following classes saved in A.java and B.java respectively.
public class A {
private int num;
public A () {
num = 3; // Line 1
}
}
public class B extends A {
public B () {
super(); // Line 2
this.num = 5; // Line 3
}
}

## ##
Which of the following statements is true?
Line 1 would cause a compiler error Line 3 would cause a compiler error
Line 2 would cause a compiler error The code would compile and run without errors

2. (2 marks) Consider the following code fragment and determine which statement below is correct.
int x = (int)(3.0); // Line 1

## ##
System.out.println(x.toString()); // Line 2
Line 1 would cause a compiler error The code would compile but would crash at runtime
Line 2 would cause a compiler error The code would compile and run without errors
3. (3 marks) Consider the following code fragment.
public class Foo<Bar> {
private Bar data;
public Foo (Object item) {
data = item;
}
}

##
Which of the following statements is true?
This will cause a compiler error because Bar is not a valid generic type name

## The statement data = item will cause a compiler error

The code will compile but will throw an exception
The code will compile and run without errors

4. (1 mark) In Assignment 1, you were asked to create two methods, toString() and toString(Line
theLine), in the LetterCrush class. These two methods demonstrate:

## Overloading

## Overriding
Polymorphism
Static methods

2
5. (3 marks) Consider the two Stacks, a and b, shown below and the following code that acts on these
stacks. What is printed when this code is executed?

a= 4 9 2 7 ←− top

b= 8 1 ←− top

while (!a.isEmpty() && !b.isEmpty()) {

System.out.print(a.pop());
System.out.print(b.pop());

## ## ## ##
}
4891 489127 48912171 This code would crash immediately
7128 712894 72189848 71289 and then it would crash

6. (3 marks) Determine what would print when executing the following code fragment.
String s = new String("hi");
String t = new String("hi");
String u = s;
if (s.equals(t)) System.out.print("A");
if (s == t) System.out.print("B");
if (s.equals(u)) System.out.print("C");
if (s == u) System.out.print("D");

## AB
AD
## AC
BD
## ABC
BCD
## ACD
ABCD

7. (4 marks) Consider the following singly linked list and the code fragment that acts on the linked list.
Determine what would happen when the code fragment is executed.

front 4 −1 −5 3 9

LinearNode<Integer> curr = front;

int count = 0;
while (curr != null) {
if (curr.getValue() > 0) count++;
else curr = curr.getNext();
}

##
System.out.println(count);
It would correctly count the number of nodes containing positive values

## It
It
It
would
would
would
count the number of total nodes in the linked list
throw a NullPointerException
get caught in an infinite loop

8. (2 marks) Determine what would print if the following code fragment executes.
Integer[] arr1 = new Integer[5];
int[] arr2 = new int[5];

# # # # #
System.out.print(arr1[0] + " " + arr2[0]);
00 null null 0 null null 0 It would throw a NullPointerException

3
9. (3 marks) Determine what would print when executing the following code fragment.
private static void m1 (int k) throws Exception {
if (k > 5) throw new Exception("too large");
System.out.print(k);
}
public static void main (String[] args) {
try {
for (int i = 3; i <= 7; i++) m1(i);
} catch (Exception e) { System.out.print("X"); }

## # # # # #
}
X 345 345X 345XX 34567 34567XX
This code would crash before anything gets printed
10. (3 marks) Determine what would print when executing the following code fragment.
public class Thing {
private static int x;
private int y;
public Thing (int p) {
x = p - 1;
y = p + 1;
}
public static void main (String[] args) {
Thing a = new Thing(4);
Thing b = new Thing(8);
System.out.print(a.x + " " + a.y + " " + b.x + " " + b.y);
}

# # # # # #
}
3535 3539 3579 3979 7579 7979
11. (2 marks) Consider the following code fragment based on the class Thing from Question 11 above.
Determine which statement below is correct.
Object t = new Thing(15); // Line 1
System.out.println(t.toString()); // Line 2

## Line 1 would cause a compiler error

Line 2 would cause a compiler error
## The code would compile but crash at runtime
The code would compile and run without crashing
12. (4 marks) Suppose we have a non-empty singly linked list and want to write an algorithm to remove
the last node in the list. Determine which of the following options would accomplish this correctly.
Assume that curr has been correctly declared as a LinearNode and references the first node of the list

##
before calling the code from these options.
while (curr != null) { curr = curr.getNext(); } curr = null;

## while (curr != null) { curr = curr.getNext(); } curr.setNext(null);

while (curr.getNext() != null) { curr = curr.getNext(); } curr = null;

# while (curr.getNext() != null) { curr = curr.getNext(); } curr.setNext(null);

None of these code fragments is correct

4
13. (3 marks) Consider the following peekSecond() method for a singly-linked list implementation of a
Stack in which the top node is the first node of the linked list. The purpose of the peekSecond()
method is to return the second item in the stack (one after the top) without removing it.
public T peekSecond () throws EmptyCollectionException {
if (isEmpty()) throw new EmptyCollectionException("empty stack");
LinearNode<T> secondNode = top.getNext();
return secondNode.getValue();
}

##
Which of the following statements is true?
The code will cause a compiler error

## The
The
The
code
code
code
will
will
will
compile but will crash in some cases
compile but will crash in every case
compile and run as expected in every case
14. (3 marks) Determine what would print when executing the following code fragment. Note: the
length() method on a String returns the number of characters in the String.
String[] arr = {"dog", "star", "map", "candy"};
int total = 0;
try {
for (int i = 0; i <= 4; i++) { total += arr[i].length(); }
} catch (ArrayIndexOutOfBoundsException e) {
total += 10;
} catch (Exception e) {
total += 20;
}
System.out.print("t = " + total);

# t = 10 # t = 15 # t = 20 # t = 25 # t = 35 # t = 45
15. (3 marks) Consider the integer array, arr, shown below. We want to remove the value 8 from the array
and shift all subsequent values to the left by one spot so there is no gap in the middle of the array. The
last item should be copied to the spot before it and remain in the last spot in the array (i.e. the same
value will be in both cells at the end of the algorithm). Select the correct code to accomplish this.

arr = 2 8 5 9 1 0 3
0 1 2 3 4 5 6

## for (int i = 1; i < arr.length-1; i++) arr[i] = arr[i-1];

## for
for
for
(int
(int
(int
i
i
i
=
=
=
1; i < arr.length-1;
arr.length-1; i > 0;
arr.length-2; i > 0;
i++)
i--)
i--)
arr[i]
arr[i]
arr[i]
=
=
=
arr[i+1];
arr[i-1];
arr[i+1];

5
Consider the following code for the next four questions.
public class A {
public A () {}
public int m1 () { return 1; }
public int m2 () { return 2; }
public int m3 () { return 3; }
}
public class B extends A {
public B () { super(); }
public int m1 (int k) { return k * 2; }
public int m2 () { return 5 * m1(); }
}
public class C extends B {
public C () { super(); }
public int m1 (int k) { return 10 * super.m1(k); }
public int m3 () { return m2(); }
}

16. (2 marks) Determine what would print when executing the following code fragment.
A obj1 = new B();
System.out.println(obj1.m2());

## 2 # 5 # 10 # 50
This code would cause a runtime error
# This code would cause a compiler error

17. (2 marks) Determine what would print when executing the following code fragment.
B obj2 = new C();
System.out.println(obj2.m1(7));

## 7 # 14 # 70 # 140
This code would cause a runtime error
# This code would cause a compiler error

18. (2 marks) Determine what would print when executing the following code fragment.
C obj3 = (C)(new A());
System.out.println(obj3.m1(4));

## 1 # 10 # 40 # 80
This code would cause a runtime error
# This code would cause a compiler error

19. (2 marks) Determine what would print when executing the following code fragment.
A obj4 = new C();
System.out.println(obj4.m3());

## 2 # 3 # 5 # 10
This code would cause a runtime error
# This code would cause a compiler error

6
Part II. Written Answers

20. (4 marks) Consider the following Java class:

public class A {

private static int top = 1;

private static int j = 10;

public static void main (String[] args) {

int top = 0;
int c = 1;
top = top;
for (int j = 1; j <= 2; j++) c = c + j;
m(c, top);
c = c + top + j;
System.out.println("top = " + top + " c = " + c);
}

public static void m (int c, int top) {

top = 5;
c = 2;
}

Write the program output in the box below.

7
21. Consider the following algorithm, modList(front) that manipulates a given singly-linked list, where
front is a reference to the first node of the list and each node stores an integer value. For each one of
the questions (a) and (b), you need to
(I) first, indicate whether the algorithm would either (i) terminate without crashing, (ii) crash, or
(iii) get caught in an infinite loop. If the code would crash, explain which exception would be
thrown
(II) second, show what the resulting linked list would look like when the algorithm is executed. You
must show ALL the nodes and the variables p, q, and head1 for (a) and p, q, and head2 for (b)
(if the algorithm would get caught in an infinite loop, show what the linked list would look like
after 3 iterations of the loop).
Algorithm modList(front) {
p = front
q = p
while p != null do {
if p != q do {
p.setNext(q.getNext())
p = p.getNext()
} else {
q = q.getNext()
}
}
}

head1 5 3 head2 9 2 1 7

(a) (5 marks) (I) Algorithm modList(head1) would:

(II) Show the resulting linked list after invoking modList(head1).

(b) (5 marks) (I) Algorithm modList(head2) would:

(II) Show the resulting linked list after invoking modList(head2).

8
22. (3 marks) Consider the doubly linked list and the following code fragments that acts on the list.
Hand-trace through the following code fragment. Write the program output in the box below.

front rear
4 2 8 1 −2 −3 4 −1 2

try {
p = front;
while (p != null) {
int v = p.getValue();
System.out.print("v = " + v + " ");
if (v > 0) for (int i = 0; i < v; i++) p = p.getNext();
else for (int i = v; i < 0; i++) p = p.getPrev();
}
} catch (NullPointerException e) {
System.out.print("Exception");
}

23. (7 marks) Suppose we have a Stack S that stores integers and we wish to reverse the order of the
values in the Stack using an int array, arr, to help with this process. Fill in the blank lines in the
code fragment below to complete the algorithm. Remember that S is a Stack and arr is an array so
you must access each one accordingly: only using push(), pop(), size(), and isEmpty() for S and
using the array operator [ ] to access the entries of arr and arr.length to get its length. Assume
this algorithm is NOT inside a Stack class so you cannot access any private variables or methods from
such a class in this algorithm.
public static void reverseStack (StackADT<Integer> S) {

int[] arr = new

int i = 0;

while ( ) {

arr[ ] =

i =
}

for (int j = 0; ) {

}
}

9
24. (8 marks) Consider the following class, Exceptions. Hand-trace this program and write the pro-
gram’s output in the box below. Assume that Exception1 and Exception2 are exception classes and
they do not inherit from one another (there is no parent-child relationship between Exception1 and
Exception2). However, Exception1 and Exception2 are child classes of class Exception.
public class Exceptions {
private static int q = 3;
public static void main (String[] args) throws Exception {
try {
int x = m1(10);
System.out.println("x = " + x);
int y = m2(10);
System.out.println("y = " + y);
if (x > y) y = m1(3);
else y = m2(3);
System.out.println("y = " + y);
} catch (Exception e) {
System.out.println("Caught in main.");
}
}

public static int m1 (int p) throws Exception1 {

int r = 1;
try {
if (q * 2 < p) r = m2(q);
else throw new Exception1("larger");
} catch (Exception2 e) {
System.out.print("Caught E2 in m1");
}
q--;
return p+r;
}

public static int m2 (int p) throws Exception2 {

if (p == q) throw new Exception2("equal");
return q*4;
}
}

Write in the box what the algorithm prints.

10
25. (13 marks) Consider singly-linked lists storing Integer values such that the first 1 or more nodes contain
positive values (> 0) and the last 0 or more nodes contain negative values (< 0). You can assume there
will always be at least 1 node storing positive values, but there might not be any nodes storing negative
values. No nodes with positive values exist after a node with a negative value.
Complete in Java or in detailed pseudocode like the one used in the lecture notes the following
algorithm split(front) that receives as parameter front which references the first node of a singly
linked list as just described. The algorithm must determine the place in the list where the group of
nodes storing positive values ends and the group of nodes storing negative values begins (if there are
any), and it must split the linked list into 2 distinct lists at that point so that we obtain one list of only
nodes with positive values which must still be referenced by front, and a second list of only nodes
with negative values (which might be empty). Create a node variable front2 to represent the first
node of the list of negative values or set front2 = null if there are no nodes storing negative values.
The ONLY methods you can use in this algorithm are: getValue(), getNext(), and setNext(). The
diagram below shows an example of the original list and the resulting two lists. Your algorithm must
work on ANY linked list, not just this example.

front
8 2 5
front 8 2 5 −7 −3 split

−7 −3
front2

(i) You CANNOT change the data stored in the nodes; so you CANNOT use setValue() you
must modify the node links.
(ii) You CANNOT use any auxiliary data structures (you cannot use an array, stack, queue,
another list, and so on).
(iii) You CANNOT initialize new node objects. You must use ONE variable front2 but it must be
null or reference an existing node from the original list. You CANNOT create new nodes.

If you do any of the above (i), (ii), or (iii), you will receive ZERO marks.

Algorithm split(front)
In: front is a reference to the first node of a singly linked list as described above
Out: front2 representing the front of the linked list of negative values

11
26. (16 marks) Complete in Java or in detailed pseudocode like the one used in the lecture notes the
following algorithm removeMax(arr,n) that receives as parameter arr which is an array storing n
positive integer values (> 0). The algorithm must find the maximum (largest) value in the array and
it must remove all occurrences of that maximum value in the array (i.e. it could appear multiple times
so the algorithm must remove all of them). All other values must shift over so that the array does not
contain any gaps between values and they must remain in the same order as they were originally. The
following figure shows an example of an array and the expected output.

arr 5 7 7 2 5 1 7 3 arr 5 2 5 1 3 0 0 0
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

(i) You CANNOT use any other auxiliary data structures (you cannot create a second array, a
linked list, a stack, and so on).
(ii) You CANNOT use made-up methods like arr.remove or arr.add. To access the values in the
array, you must use the array operator [ ].

If you do either of the above (i) or (ii), you will receive ZERO marks.
Your code must work on ANY array storing positive values, not just the one shown in the example
above.
Algorithm removeMax(arr, n)
In: Array arr storing n positive integer values
Out: Nothing returned, but arr is modified as described above

Hint: Scan arr and compute the value vmax and index imax of the maximum value in arr. Then, scan
again arr starting at index i = imax +1 and for each value arr[i] != vmax , shift it to position imax
(what do you with imax after you shift a value to that position? What value do you store in arr[i]?
What do you do if arr[i] = vmax ?)

12