1. The following code implements a linked-list Node:

struct Node {

int data;

Node *next;

};

Node *A;

a) Write a newfunction to delete the Nth element in the linked-list.

The new function's prototype is:

bool DeleteNthNode(Node * & listpointer, int nth_element);

If the  deletion  is  completed, the  function  should return true. If the linked-list has  less than N elements, then the function should return false.

Make  sure that your  code  covers  all  cases:  when  the  list  is  empty, when the  list  only has  one element, or two elements etc. [3 marks]

b) Write a function that searches for an item in a linked-list. If the search finds the item, then it should return true. If the search does not find the item, then the function should return false.             The function's prototype should be:

bool SearchItem(Node * listpointer, int item); [3 marks]

c) Draw a diagram of the linked-list mylist, produced after the following calls to the functions AddNode_type1() and AddNode_type2() seen in the following code snippets:

...

void AddNode_type1(Node * & listpointer, int newitem) {

Node *temp;

temp = new Node;

temp->data = newitem;

temp->next = listpointer;

listpointer = temp;

}

void AddNode_type2(Node * & listpointer, int newitem) {

Node *current;

current=listpointer;

if(current!=NULL){

while (current->next!=NULL){

current=current->next;

}

Node *temp;

temp = new Node;

temp->data = newitem;

temp->next = NULL;

if(current!=NULL) current->next = temp;

else listpointer=temp;

}

...

main(){

...

Node * mylist=NULL;

AddNode_type2(mylist, 8);

AddNode_type1(mylist, 7);

AddNode_type2(mylist, 6);

AddNode_type1(mylist, 1);

AddNode_type2(mylist, 2);

AddNode_type2(mylist, 3);

AddNode_type1(mylist, 4);

} [2 marks]

a) Draw the threads for the tree above considering that they are for speeding up the in-order traversals. [1 marks]

b) Redraw the diagram of the BST above after deleting the node with key=90.

(copy the diagram in the blue answer book) [1 marks]

c) Redraw the diagram of the BST above after inserting a node with key=47.

(copy the diagram in the blue answer book) [1 marks]

d) Given the Tree class declaration written below, write the C++ method to search a node in a BST. Your code can be either recursive or non-recursive. If the key is found, the method should return true, if it fails to find that key value, than it should return false.

class Tree {

private :

int key;

Tree *leftptr, *rightptr;

public :

Tree(int newkey, Tree* L, Tree* R);

~Tree() { }

int RootData() { return key;}

Tree* Left() { return leftptr;}

Tree* Right() { return rightptr;}

//write the code for the method below

bool Search(int item);

}; [3 marks]

5. Consider the following class for a Heap:

class Heap {

private :

int data[MAXSIZE];

int last;

public :

Heap(){ last=-1; };

~Heap() { };

void InsertHeap(int newthing);

int DeleteRoot();

};

a) Write the C++ method InsertHeap(int newthing). [4 marks]

b) For the Heap in the figure above draw the state of the Heap after inserting a node with key = 64. Draw also the state of the array. (copy the diagrams in the blue answer book). [2 marks]

c) For the Heap in the figure above draw the state of the Heap after deleting the root node. Draw also the state of the array. (copy the diagrams in the blue answer book). [2 marks]

6.  Given the Tree C++ class below, answer questions a) and b):

class Tree {

private :

char data;

Tree *leftptr, *rightptr;

public :

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

~Tree() { }

char RootData() { return data; }

Tree* Left() { return leftptr; }

Tree* Right() { return rightptr; }

};

a) Write a C++ function for the post-order traversal of a binary tree.

Note 1: you can use any of the methods available on the Tree class inside the function. Note 2: it is easier to write a recursive function. [1 marks]

b) Using a Queue as a supporting ADT, write a C++ function to print a Binary Tree by level, root first (aka Breadth-first traversal). The class declaration for the Binary Tree is listed below.

Note: the queue should contain pointers to the Tree nodes. Do not write the queue class itself, nor its methods, just consider using the well-known methods Join(), Leave(), Front() and isEmpty(). [2 marks]

c) Draw a B-Tree with order 3, where the following elements were inserted in the following order: 21,  3,  4,  7,  23,  25,  6,  20, 1, 5, 2

(copy the diagram in the blue answer book). [3 marks]

7. Consider the following representation of a graph:

a) Complete the adjacency matrix below (in the blue answer book).

[1 marks]

b) Using Kruskal algorithm, find the Minimum Cost Spanning Tree for the graph above. [2 marks]

c) Write the pseudo-code for Dijkstra's algorithm. Using the algorithms, what is the shortest path from A to all other nodes? Show all the work based on the pseudo-code (use the same variable names). [5 marks]

8.

a) The code for a Bubble sort function is shown below:

swapping = true ;

while (swapping) {

swapping = false ;

for (i = 0; i < n-1; i++) {

if (data[i] > data[i+1]) {

swap(data[i], data[i + 1]);

swapping = true ;

}

}

}

This algorithm works, but it can be improved. We know that part of the array data[] (at the end of the array) is already sorted because at every iteration the 'bubble' drags the larger keys to the right side of the array. Devise a modification to the algorithm that avoids computing steps where the    elements are already sorted. (tip: it is easier to modify the algorithm by drawing a small example  using 4 or 5 numbers). [2 marks]

b) Use Cichelli's method to devise a perfect hash function for the following words: TREE, STACK, QUEUE, GRAPH, HEAP, LINKEDLIST, VECTOR, SET

Tips: for the hash function, use: H() =( length + g(first letter) + g(last letter) ) % 8

Write the final hash table for the words above (do not forget to test if each index is unique). [4 marks]

c) The following two C++ codes are implementations of two different sorting algorithms. The code SortingA() has a runtime of about 2 miliseconds for a problem size N=100.

The code SortingB() has a runtime of about 5 miliseconds for a problem size N=100.

For a very large problem, e.g. N=1000000, which of the two algorithms is more likely to have the shortest runtime?

Explain the reasons for your choice and write the average complexity of the two algorithms.

Note: the SortingB is a recursivefunction.