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

CE204-5-SP
2

SECTION A

Candidates must answer Question 1 in Section A.

Question 1

(a) (i)
Prove directly from the definition of big O that 8n2+5n+2 is O(n2).
[3%]
(ii)
State with reasons a big O estimate for the worst-case time complexity of the following
[5%]

function.

int myfunc(int n)
{ int result =
0;

for (int i =
0; i

{ boolean isEmpty(); T rootValue(); BinaryTree leftChild();
BinaryTree rightChild();
}

Write a method that takes an argument of type BinaryTree, uses a post-order traversal to count the number of lower-case letters in the tree specified in the argument, and returns the count.

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.

(b) Write a Java method that takes a string argument and uses a stack to check whether [10%] brackets and 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

(a)
Show how the following undirected graph would be represented using an adjacency
[3%]
matrix.61ABC
2
3
3

5

DEF44(b)
Explain what is meant by a spanning tree for a connected undirected graph.
[3%]
(c)
Describe Prim’s algorithm for finding minimum cost spanning trees in a directed graph
[10%]

and comment briefly on its time complexity.

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

for the graph shown in part (a) above. Vertex A should be used 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 (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.31553645711

END OF SECTION B

END OF PAPER CE204-5-SP