CE204-5-SP
2
SECTION A
Candidates must answer Question 1 in Section A.
Question 1
(a)
[2%]
Explain what is meant by the term binary tree.
(ii)
Explain the difference between pre-order, post-order and in-order traversals for
[4%]
binary trees.
(iii)
The following interface specifies the binary tree type.
[8%]
interface BinaryTree
{ boolean isEmpty();
rootValue(); BinaryTree
}
Write a method that takes an argument of type BinaryTree
(b) Describe what is meant by the halting problem and give a brief outline of how it can be [12%] proven that it has no algorithmic solution.
(c) Describe the mergesort algorithm and comment briefly on its time complexity.
[7%]
Question 1 continues…
3 CE204-5-SP
Question 1 continued.
(d) The following grammar describes a simple language of arithmetic expressions.
[7%]
exp lp exp rp | exp op exp | number
op plus | minus | times
The symbols, lp, rp, plus, minus and times refer to the lexemes (, ), +, – and * respectively and the symbol number refers to any non-negative integer.
Provide a declaration for a set of Java classes that could be used to store parse trees for this grammar. The methods of the classes do not have to be declared.
END OF SECTION A
CE204-5-SP
4
SECTION B
Candidates must answer TWO questions from Section B.
Question 2
(a) Provide a complete Java class that implements the interface
[28%]
interface StringQueue
{ boolean isEmpty(); void add(String i);
String frontValue();
void removeFront();
}
The class should provide an implementation of a standard first-in-first-out queue. The objects in the queue should be stored in a linked list of objects of type QueueCell. QueueCell should be written as an inner class. If applied to an empty queue the frontValue and removeFront methods should throw an exception – you may
assume that an appropriate QueueException class has been declared. A no-argument constructor should be provided to ensure that a newly-created queue will be empty.
(b) Comment briefly on the time complexity of the operations provided in your answer to [2%] part (a).
5 CE204-5-SP
Question 3
(a) Explain what is meant by the terms connected and acyclic as used to describe undirected [2%] graphs.
(b) Explain what is meant by a spanning tree for a connected undirected graph.
[3%]
(c) Describe Kruskal’s algorithm for finding minimum cost spanning trees in connected [9%] undirected graphs.
(d) Show, step by step, the use of Kruskal’s algorithm to find a minimum cost spanning [16%] tree for the graph shown below. At each stage you should show the connection sets.
10
9
A
B
C
4
3
7
2
D
E
F
5
6
CE204-5-SP
6
Question 4
(a) A class to implement binary search trees of strings is given by the declarations
[12%]
class BTNode
{ T value;
BTNode
}
public class BST
{ private BTNode
public BST() {………}
public void insert(String i) {………}
public boolean find(String i) {………}
}
Provide a complete body for the insert method; it should do nothing if the argument string is already present in the tree.
(b) Show, step by step, the results of inserting the following numbers into an initially- [18%] empty binary search tree, using the AVL rebalancing algorithm when necessary in
order to ensure that the tree is AVL-balanced after each insertion
3 5 16 36 27 1114
END OF SECTION B
END OF PAPER CE204-5-SP