程序代写代做 AVL algorithm graph Java CE204-5-SP

CE204-5-SP
2

Question 1

(a)
(i) Explain precisely what is meant by the statement “T(n) is O(f(n)”.
[3%]

(ii) Prove directly from the definition of big O that 7n2+9n+5 is O(n2).
[4%]
(b)
Describe the insertion sort algorithm and comment briefly on its time complexity.
[8%]
(c)
Explain what is meant by a non-computable function, and give an outline of a proof that
[10%]

such a function exists.

3 CE204-5-SP

Question 2

(a) The following interface specifies the binary tree type.
[8%]

interface BinaryTree
{ boolean isEmpty();

rootValue(); BinaryTree leftChild(); BinaryTree rightChild();
}

Write a method that takes an argument of type BinaryTree and uses a post-order traversal to calculate the sum of the lengths of all of the strings in the tree specified in the argument and return this sum as a value of type int.

(b) Provide a complete Java class that implements the interface
[17%]

interface CharStack

{ boolean isEmpty(); void push(char c); char top();

void pop();

}

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.
CE204-5-SP
4

Question 3

(a)
Show how the following undirected graph would be represented using an adjacency
[3%]

matrix.

8

A

B

9

4
7
3

CDE6
11

(b)
Describe Kruskal’s algorithm for finding minimum cost spanning trees in connected
[10%]

undirected graphs.

(c)
Show, step by step, the use of Kruskal’s algorithm to find a minimum cost spanning tree
[12%]

for the undirected graph shown in part (a) above. At each stage you should show the sets

of connected components.

5 CE204-5-SP

Question 4

(a)
Explain the meaning of the terms balanced and AVL-balanced as used to describe binary
[4%]

trees.

(b)
Give examples of binary trees containing exactly 7 nodes that are (i) neither balanced nor
[4%]

AVL-balanced, (ii) AVL-balanced but not balanced, and (iii) both balanced and AVL-

balanced. (It is not necessary to show the values at the nodes.)

(c)
Show, step by step, the results of inserting the following numbers (in the order in which
[17%]

they are listed) into an initially-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
21 8
23
35
11 17

END OF PAPER CE204-5-SP