The University of Western Ontario
CS1027 Computer Science Fundamentals II
Final Exam
April 24, 2020
For the final examination you are required to write two Java classes, specified in the following
sections. Several Java classes are provided which you must use to answer the exam. Study these
classes to see which public methods you can use. You CANNOT modify in any manner any of
the classes provided. If you modify the given classes, you will be penalized.
You CANNOT use any other Java classes than the ones provided, this includes any classes from
the standard Java libraries. To be clear, you CANNOT use any of the Java classes from the Java
libraries.
You must submit ONLY Answers.txt, Answers1.java and Answers2.java through OWL by April
28 at 11:00 am Eastern Daylight Time (time zone of London, Ontario). Late submissions will be
accepted until April 28 at 11:55 am, but submissions after April 28 at 11:00 am, will receive a late
penalty of 1 mark for each 5 minutes that they are late. So, submissions on April 28 between 11:01
am and 11:05 am will receive a late penalty of 1 mark; submissions on April 28 between 11:06 am
and 11:11 am will receive a late penalty of 2 marks, and so on. No submissions will be accepted
after April 28 at 11:55 am.
Your code must be reasonably legible; please add comments to those parts of your code that you
think might not be easy to understand. You will not be marked on your comments, but if the marker
cannot understand your code you might lose some marks.
Question 1 (26 marks)
To answer the first question, you will need to use the provided Java classes: Question1.java,
ClassA.java, ClassB.java, Exception1.java, Exception2.java and Exception3.java.
One of the files provided is called Answers1.java. In the first two lines of this file you need to write
your name and student ID. You must implement in this file a class called Answers1 such that when
program Question1.java is executed the following output is produced:
Test 1 passed
Test 2 passed
Test 3 passed
methodB1 threw the exception
methodB2 threw the exception
Test 4 passed
methodB1 threw the exception
Test 5 passed
Test 6 passed
The output must be exactly as specified above, no additional messages must be printed by your
code. Study class Question1.java to understand what functionality Answer1.java is required to
provide. Your implementation of Answer1.java must satisfy the following requirements:
o You cannot implement a method called m in Answer1.java. Line 7 of Question1.java
contains the statement var1.m(1) where var1 is a variable of type Answer1. Explain how
method m1 can be invoked in that statement even though method m1 is not implemented
in class Answer1.java. Write your answer in Answers.txt. (Hint. Study the java classes
provided, one of them implements a method called m.)
o You must implement a method called numObjectsAnswer1 with the following signature
public int numObjectsAnswer1 ()
that returns the number of objects of type Answer1 that have been created by program
Question1.java. You also need to implement the constructor for the class Answer1.java.
How can method numObjectsAnswer1 know how many objects of type Answer1 have
been created by another Java class? (Hint. Use an instance variable. What type of variable
do you need?) Write your answers in Answers.txt.
o You must also implement a method called method1. Study how this method is invoked
from Question1.java to determine what the signature of this method must be.
In this method you must declare a variable of type ClassB:
ClassB var = new ClassB();
Then you must invoke methods methodB1(test) and methodB2(test) of ClassB, where test
is the parameter of method1. Since these methods can throw exceptions, their invocations
must be placed inside a try-catch block. You can use only ONE try-catch block inside
this method, so your code will look like this:
try {
var.methodB1(test);
…
var.methodB2(test);
}
catch (…) {…}
…
o If an exception of type Exception1 is thrown inside this try-catch block, the
exception must be caught and method m(test) must be invoked.
o If an exception of type Exception2 is thrown inside this try-catch block the
exception must be caught and an exception of type Exception3 must be thrown.
o If an exception is thrown by methodB1 then the message “methodB1 threw the
exception” must be printed; if an exception is thrown by methodB2 then the
message “methodB2 threw the exception” must be printed. Your implementation
SHOULD NOT print both messages, only one message must be printed every
time that an exception is thrown when running this method. If no exception is
thrown by methodB1 or methodB2, then no message must be printed by method1.
Since both, methodB1 and methodB2 throw Exception2, how can your
implementation of method1 know which of them threw the exception? Write your
answer in Answers.txt.
Question 2
Walda the Warrior is attempting to walk through the Perdition Forest, which has a lot of forks in
the road. The forest is inhabited by two types of monsters: ogres and goblins. The roads that Walda
can use to cross the forest are represented with two binary trees with each fork in a road, bend in
a road, and end of a road indicated by a node of a tree. At each node of the first tree there is a set
of ogres; at each node of the second tree there is a set of goblins. Ogres and goblins try to prevent
Walda from getting across the forest. Walda must fight the monsters that she encounters as she
traverses a path; if she successfully defeats her foes, she can continue along the path that she has
chosen, but if she is defeated, she must turn back and try a different path. Specifications about
when Walda will win and when she will lose a battle are given below.
One of the files given to you is called Answer2.java. This class contains the signatures of 3
methods that you must implement, and which are explained below.
1. Method mergeToLinkedList (25 marks)
This method has the following signature
public LinkedList mergeToLinkedList(LinkedList list1, CircularArray list2)
Classes LinkedList and CircularArray are provided. Class LinkedList represents a linked list where
each node stores an integer value. Values are stored in increasing order in this list. Class
CircularArray represents a circular array storing integer values sorted in increasing order. Please
study these classes to learn which public methods they provide; you can use any of the public
methods in any of the provided classes in your solution. Study also class ListNode.
Note that in class CircularArray the value of front is not zero and instance variable rear is the index
of the last data item stored in the circular array. Also note method getArray returns a reference to
the array where the data items are stored.
Method mergeToLinkedList must create and return an object of the class LinkedList containing all
values in list1 and list2 stored in increasing order of value. You CANNOT use an auxiliary array,
circular array, linked list, stack, or any other data structure to implement this method. The ONLY
data structures that you can use are the LinkedList list1 and CircularArray list2. If you use any other
data structures you will be heavily penalized.
Note that class LinkedList has 3 instance variables: front, rear, and count. Once you have created
the new linked list storing in order the values from list1 and list2 you MUST use methods setFront,
setRear, and setNumDataItems from class LinkedList to set the values of the aforementioned
instance variables. You can assume that list1 and list2 do not have common values.
For example, if list1 and list2 are:
Then the merged list produced by mergeToLinkedList must be as follows
2. Method mergeTrees (25 marks)
This method has the following signature
public TreeNode mergeTrees(TreeNode r1, TreeNode r2)
Class TreeNode is provided and it represents a node of a binary tree. Please study this class to
learn the public methods that you can use. Each TreeNode object stores a data item of type either
LinkedList or CircularArray.
The first parameter of method mergeTrees is the root of a binary tree and the second parameter is
the root of a second binary tree. Method mergeTrees must merge the two trees with roots r1 and
r2 and it must return the root of the merged tree. This method MUST be recursive. The merging
must be done in the following manner:
• If r1 and r2 are null then the merged tree is null also.
• If one of r1 or r2 is null then the merged tree is the tree that is not empty. Note that the
non-empty tree might store objects of type CircularArray.
• If neither r1 nor r2 is null, then a new node n must be created to be the root of the merged
tree. The data stored in n is the combination of the data stored in r1 and the data stored in
r2 obtained by invoking method mergeToLinkedList.
Note that one of the nodes r1, r2 will store a data item of type LinkedList and the other one
will store a data item of type CircularArray. To invoke method mergeToLinkedList, first you
3 7 9 1 5
front rear
count = 2 count = 3
0 1 2 3 4
front = 3 rear = 0
array
list1 list2
1 3
front rear
count = 5
5 7 9
need to determine which node r1 or r2 stores a data item of type LinkedList and which one
stores a data item of type CircularArray. To obtain the data stored in a node use method
getData from class TreeNode. Observe that class TreeNode has a parameter T specifying
the type of data stored in a node; so, it is not obvious whether the data item stored in a node
is of type LinkedList or CircularArray. How do you determine this? Write your answer in
Answers.txt.
Once the data item to be stored in some node n has been computed, the left child of n must
be set as the tree obtained by merging the tree whose root is the left child of r1 with the
tree whose root is the left child of r2. Finally, the right child of n is the tree obtained by
merging the tree whose root is the right child of r1 with the tree whose root is the right
child of r2. Note that in the merged tree some nodes will store an object of type LinkedList
and some other nodes will store an object of type CircularArray.
The following figure shows two binary trees with roots r1 and r2 and the corresponding
merged tree with root n. Each node in the first tree stores a LinkedList object and each node
in the second tree stores a CircularArray object.
Figure 3.
3. Method defeatMonsters (24 marks)
This method has the following signature
public boolean defeatMonsters(TreeNode r, int attackValue)
This is the method that Walda the Warrior uses to determine whether she can cross the Perdition
Forest. The first parameter of this method is the root of the tree representing the forest roads and
containing information about the ogres and goblins. This tree is obtained by invoking method
mergeTrees, so each node of this tree stores an object of the class LinkedList or an object of the
class CircularArray. The root of the tree represents the entrance to the forest and each leaf of the
tree represents an exit.
If the tree is empty or if there is at least one path from the root to a leaf in which Walda is able to
defeat all the monsters that she encounters, then the method must return the value true. On the
4 8 12
10 2
4 5 9
r1 r2
n
10 2
10 2
10 2
10 1
4 8 1
2 4 8 10 12
1 4 5 9 10
1 2 4 8 10
A
E
B C
D
10 2
10 2
Merged tree
other hand, if there is no path from the root to a leaf that allows Walda to win every battle against
the monsters, then the method must return the value false.
To implement this method, you are required to perform an iterative preorder traversal of the
tree (see below). Whenever a node p of the tree is visited in this traversal, the algorithm will check
if Walda can defeat the monsters located there. To check whether Walda will be victorious against
the monsters located in this node, this method must do the following.
• The second parameter, attackValue, of this method specifies the attack value of Walda.
• If node p stores a LinkedList object L, each ListNode object in L contains an integer value
specifying the attack value of a monster that Walda must face. Otherwise, if node p stores
a CircularArray object L each integer value stored in L specifies the attack value of a
monster.
• For each attack integer value v in the list L do the following:
o If the attack value of Walda is larger than or equal to v, then Walda will win this
battle and her attack value will increase by the attack value v of the defeated
monster.
o However, if the attack value of Walda is smaller than v, then she loses the battle
against the monsters in node p and she must turn back.
• If Walda wins all the battles against the monsters stored in node p, then she can continue
the traversal of the tree. Note that if the list L is empty then Walda also can continue the
traversal of the tree.
Regardless of whether Walda wins or loses a battle against all the monsters in a node of the tree,
after the battle her attack value is restored to its initial value specified by the parameter
attackValue. For example, assume that Walda has initially attack value 2 and she faces monsters
in some node p with attack values 3, 1, and 5. These attack values are stored in increasing order of
value in the nodes of the list stored in node p. Walda will then first face and defeat the monster
with attack value 1, after which her attack value increases to 2 + 1 = 3. Then she faces and defeats
the monster with attack value 3, thus increasing her attack value to 3 + 3 = 6. Finally, she faces
and defeats the last monster as her current attack value is 6 and the attack number of the last
monster is 5. After defeating all these opponents Walda can move to the next node of the tree, but
her attack value is reset to its initial value of 2.
Consider the tree with root n in Figure 3. If the initial attack value of Walda is 2, then she will lose
the battles at nodes B, D, and E, so she cannot cross the forest and method defeatMonsters in this
case will return the value false. However, if the initial attack value of Walda is 3, she will lose the
battle at node B, but she will win the battles at nodes A, C, and D and so in this case method
defeatMonsters will return the value true.
Your implementation of this method cannot use a recursive algorithm. You are provided with a
Java class called ArrayStack that implements a stack. You can perform an iterative preorder
traversal of a tree using a stack as follows
o Create an empty stack and push into it the root of the tree.
o While the stack is not empty perform the following steps:
o Pop a node p out of the stack and visit this node p
o If p has a right child, push that child in the stack (think about why the right child is
pushed first)
o if p has a left child, push that child in the stack.
Testing your Code
You should thoroughly test your code to make sure it works as specified. Read the specifications
of all the methods carefully. To help you out and to try to make sure you understand the
specifications of the methods that you must implement we provided you with a program called
TestQuestion2.java. This program performs the following tests:
o Test method mergeToLinkedList by passing as parameter a linked list storing values 4, 8,
12 and a circular array storing values 2 and 10.
o Test method mergeTrees by passing as parameters the roots r1 and r2 of the trees in Figure
3. A second test invokes the same method but passing as first parameter r2 and second
parameter r1.
o Test method defeatMonsters by passing as parameter the root n of the third tree in Figure
3 and attack value 3. A second test of the same method on the same tree uses as attack
value 2.
Note that the above program was not intended to perform an exhaustive testing of your code. We
will perform many more tests on your code, and we will check that you followed all
specifications. So even if you pass the tests on TestQuestion2, that does not mean that you will
get 100% for this part of the exam.