1. The following code implements a linked­list with a function AddNode():

struct Node {

int data;

Node *next;

};

Node *A;

void AddNode(Node * & listpointer, int newthing) {

Node *temp;

temp = new Node;

temp­>data = newthing;

temp­>next = listpointer;

listpointer = temp;

}

a) Modify the AddNode() function to add a node to the tail of a circular linked­list. [4 marks]

b) The following code implements a reverse function for the linked­list:

void ReverseLL(Node * &listpointer) {

Node *current;

Node *reversedcopy=NULL;

Node *temp;

current = listpointer;

while (current!=NULL) {

AddNode(reversedcopy,current­>data);

current = current­>next;

}

listpointer=reversedcopy;

}

Based on the code, explain the problem called“memory leaking”. [2 marks]

c) Modify the above function ReverseLL() in such a way that it avoids the memory leaking problem. [2 marks]

3. The following class implements a List using a linked­list.

template 

class List {

private:

struct Node {

T data;

Node *next, *previous;

};

Node *front, *current,  *tail;

public:

List();

~List();

//other methods ...

void UnknownMethod();

};

template 

void List::UnknownMethod(List &L){

Node * temp;

temp=front;

while(temp!=NULL){

L.AddtoTail(temp­>data);

temp=temp­>next;

}

}

a) Describe briefly what the UnknownMethod() does. [2 marks]

b) Write a new method called PreviousItem(T & item) to recover the previous item when the current pointer is pointing to a certain element in the List. [2 marks]

c) Write a method that traverses the list in reverse order. [2 marks]

4.

a) Consider the following binary tree:

Write the in­order and post­order traversals. [2 marks]

b) Write an algorithm that returns the height of a binary tree. [2 marks]

c) Draw the resulting BST after numbers are entered in the following order: 5, 3, 4, 1, 2, 6, 8 [2 marks]

d) Write a function that returns the value of the largest key in a Binary Search Tree (BST). [2 marks]

5. Considering that a Heap class is implemented with an array:

class Heap {

private:

unsigned int data[MAXSIZE];

int last;

public:

Heap(){ last=­1; };

~Heap() { };

void InsertHeap(unsigned int newthing);

int DeleteRoot();

};

a) Write a simple equation to find the left child, given the index of its parent. [1 marks]

b) Write a simple equation to find the right child, given the index of its parent. [1 marks]

c) Write a simple equation to find the parent, given the index of its right child. [1 marks]

d) Consider that the InsertHeap() method is implemented  correctly. Using the main() function below, draw the array that contains the Heap considering that the MAXSIZE=10;

main(){

InsertHeap(2);

InsertHeap(3);

InsertHeap(5);

InsertHeap(4);

InsertHeap(1);

InsertHeap(7);

InsertHeap(6);

InsertHeap(8);

}

[5 marks]

6. The following code implements a Threaded Binary Tree class:

class Tree {

private:

char

Tree

bool

public:

data;

*leftptr, *rightptr;

lthread, rthread;  // two new variables

Tree(char newthing, Tree* L, Tree* R);

~Tree() { }

char RootData() { return data; }  // inline functions

Tree* Left() { return leftptr; }

Tree* Right() { return rightptr; }

bool IsEmpty();

bool LeftThread() { return lthread; }  // two new methods

bool RightThread() { return rthread; }

};

a) The threaded tree above had its treads written for in­order traversal. The same threaded tree has now to be traversed, although inefficiently, in post­order traversal. Modify the following recursive function so that it works with the Tree class implemented above.

void PostOrder(Tree *T) {

if (T == NULL) { return; }

PostOrder(T­>Left());

PostOrder(T­>Right());

printf("%c ", T­>RootData());

}

[2 marks]

b) Draw the threads to help the in­order traversal in the following tree:

Note: copy the tree on the blue answer book

[2 marks]

c) Explain what are AVL trees and what are the advantages of using them. [2 marks]