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

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 leftChild(); BinaryTree rightChild();
}

Write a method that takes an argument of type BinaryTree and uses a pre-order traversal to calculate and return the number of upper-case letters in the tree specified in the argument.

(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 left, right;

}

public class BST
{ private BTNode root;
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