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) Write a new function to add a node after a certain element in the linked­list. The new function's prototype is:

AddNodeAfter(Node*& listpointer, int newthing, int searchedthing);

If the searched element does not exist in the linked­list, then the newthing should be added to the tail of the linked­list. [5 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” . [1 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 T>

class List {

private:

struct Node {

T data;

Node *next, *previous;

};

Node *front, *current,  *tail;

public:

List();

~List();

bool FirstItem(T & item);

bool NextItem(T & item);

};

template <class T>

bool List<T>::FirstItem(T & item) {

if (front == NULL) { return false; }

item = front­>data;

current = front;

return true;

}

template <class T>

bool List<T>::NextItem(T & item) {

current = current­>next;

if (current == NULL) { return false; }

item = current­>data;

return true;

}

a) Write  a function  that  traverses  and  prints  the  List.  The  function  needs  to  rely  on FirstItem() and NextItem() methods to work. Assume that the data is integer, i.e., that the instance of the List is:     List<int> mylist; [2 marks]

b) Write a new method called TraverseListForward() that traverses the list from front to tail. Note: do not use FirstItem() or NextItem() methods, as the method can access the private variables directly. [2 marks]

c) Write a new method called TraverseListReverse() that traverses the list in reverse order.   Note: the class already contains a node with a previous pointer, and there is a tail pointer as well. [2 marks]

4. Consider the following binary tree for questions a), b) and c):

a) Write the pre­order and post­order traversals. [2 marks]

b) Is the tree above a Binary Search Tree (BST)? Why or why not? [2 marks]

c) Write an algorithm (pseudo­code) that returns the value of the smallest key in a Binary Search Tree (BST). Demonstrate that your algorithm works using it on the tree above. [2 marks]

d) AVL trees are trees that are always balanced. Explain why it is important to balance trees when adding or deleting nodes from it. [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 method to return the value of the left child, given the index of its parent. [2 marks]

b) Write a method to return the value of the parent, given the index of its right child. [2 marks]

c)  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);

}

[4 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) Draw the threads to help the in­order traversal in the following tree:

Note: copy the tree on the blue answer book

 [2 marks]

b) Write a function for the in­order traversal of a threaded tree. In your implementation you can use the function NextNode(Tree*N) below:

Tree *NextNode(Tree *N) {

Tree *temp;

if (N­>RightThread()) { return N­>Right(); }

temp = N­>Right();

while (temp­>LeftThread() == false) {

temp = temp­>Left();

}

return temp;

}

[4 marks]