1.

Explain the following terms in the context of the tree Abstract Data Type:

• Height
• Complete binary tree
• Multiway Tree
• Height Balanced Tree

2.

Design a class TreeNode for a Binary Search Tree containing employees of a company. The information to be stored in each node is the employee's name, and their pay-rate. Include constructor(s) and the appropriate methods for the class.

3.

Construct a binary search tree from the following integers:

40 35 60 20 35 15 65 55

Show the effect of deleting integers 20 and 40 from the binary search tree. Use the inorder successor for deletion where necessary.

4.

Construct a binary code using Huffman's algorithm for the following symbols and their corresponding probabilities. Show graphically each step in the process.

E 0.30

X 0.10

T 0.18

R 0.14

A 0.27

5.

Define what is meant by the Balancing Factor of a node in a Binary search tree. What are the acceptable balancing factor values for nodes in an AVL tree?

6.

Insert the following keys in turn to construct an AVL tree. Show at each step how (and why) the tree is restructured to maintain its height balance. Indicate in each instance which type of rotation is being performed.

C

COBOL

ADA

LISP

JAVA

MODULA

PACSAL

FORTRAN

7.

Insert the following keys into a red-black tree. Show how the tree is restructured to maintain its height balance indicating which type of rotation is being performed and why the restructuring is necessary. Use diagrams to show the tree at each point in its evolution.

4 7 12 15 5 14 18

8.

Design a function bubblsSort() to sort an array or integers.

9.

Design, using JAVA code an algorithm quickSort() to sort an array of integers.

10.

Explain the term prefix code. Describe how a Binary code tree specifies a prefix code.

11.

Show, using diagrams, how Quicksort works on the following list of integers:

35 40 5 15 45 25

12.

What is the average and worst case performance of the Quicksort algorithm?

13.

Write short notes on the concept of NP-completeness, explaining the issues of non-determinism, and polynomial and exponential computational complexity.

14.

Comment on the relationship of NP-completeness to other types of problem.