CE204-5-SP
2
SECTION A
Candidates must answer ALL questions in Section A.
Question 1
(a)
(i)
Explain precisely what is meant by the statement “T(n) is O(f(n))” and explain its
[5%]
relevance when estimating the running times of programs.
(ii)
Prove directly from the definition of big O that 5n2+8n+1 is O(n2).
[3%]
(b)
Give an example of a non-computable function, with an outline of a proof that it can
[12%]
not be computable.
(c)
Describe the insertion sort algorithm and comment briefly on its time complexity.
[8%]
(d)
(i)
Explain what is meant by pre-order, post-order and in-order in relation to
[4%]
traversals of binary trees.
(ii)
The following interface specifies the binary tree type.
[8%]
interface BinaryTree
{ boolean isEmpty(); T rootValue(); BinaryTree
BinaryTree
}
Write a method that takes an argument of type BinaryTree
END OF SECTION A
3
SECTION B
Candidates must answer TWO questions from Section B.
Question 2
Provide a complete Java class that implements the interface
interface CharStack
{ boolean isEmpty(); void push(char i);
void pop();
char top();
}
CE204-5-SP
[20%]
The class should provide an implementation of a first-in-last-out stack and use a linked list to store the contents of the stack. The linked list must be implemented using list cells (i.e. you are not allowed to use the LinkedList class from the collections framework); the cell class should be written as an inner class. If applied to an empty stack the pop and top methods should throw an exception – you may assume that an appropriate StackException class has been declared. A no-argument constructor should be provided to ensure that a newly-created stack will be empty.
Write a method that takes a string argument and checks whether brackets and [10%] parentheses in the string are correctly nested. You may assume that a method public static boolean matches(char c1, char c2), which checks whether its arguments form a matching pair of brackets or parentheses, has been provided.
CE204-5-SP
4
Question 3
Show how the following graph would be represented using:
(i) an adjacency matrix; and
[4%]
(ii) adjacency lists.
[4%]
9
B
1
A
C
3
5
2
4
D
E
F
9
3
(b) Describe Prim’s algorithm for finding minimum cost spanning trees in connected [8%] undirected graphs.
(c) Show, step by step, the use of Prim’s algorithm to find the minimum cost spanning tree [14%] for the graph shown in part (a) above. Use vertex A as the starting point.
5CE204-5-SPQuestion 4
(a) Explain what is meant by the terms binary tree and binary search tree.
[5%]
(b)(i) State the meaning of the terms balanced and AVL-balanced as used to describe
[4%]
binary trees.
(ii) Give an example of a binary tree that is AVL-balanced but not balanced.
[2%]
(c) Show, step by step, the results of inserting the following numbers into an initially-
[19%]
empty binary search tree, using the AVL rebalancing algorithm when necessary in
order to ensure that the tree is AVL-balanced after each insertion
719925381113
END OF SECTION B
END OF PAPER CE204-5-SP