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

CE204-5-SP
2

Question 1

(a)
Explain precisely what is meant by the statement “T(n) is O(f(n))” and explain its
[4%]

relevance to the estimation of running times of algorithms.

(b)
Explain what is meant by a non-computable function, and give an outline of a proof that
[11%]

such a function exists.

(c)
Describe the selection 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 traversals
[4%]

of binary trees.

(ii) The following Java 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, uses a pre-order traversal to count the number of strings of length greater than 3 in the tree specified in the argument, and returns the count.

.
3 CE204-5-SP

Question 2

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

interface StringStack

{ boolean isEmpty(); void push(String s);

String 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, each of which contains a string and a reference to the next cell in the list; the cell class should be written as an inner class. (You should not use the LinkedList class from the Collections Framework.) 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

Consider the following undirected graph.

7

1

A

B

C

2
3
4

6

DEF45(a)
Show how the above graph would be represented using an adjacency matrix.
[3%]
(b)
Describe Prim’s algorithm for finding a minimum cost spanning tree for a connected
[8%]

undirected graph and comment briefly on its time complexity.

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

for the graph shown above. Vertex A should be used as the starting point.

5 CE204-5-SP

Question 4

(a)
Explain what is meant by the terms balanced and AVL-balanced as used to describe
[4%]
binary trees.(b)
Show, step by step, the results of inserting the following numbers (in the order in which
[19%]

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.325935451217

END OF PAPER CE204-5-SP