Computer Science

Data Structure & Algorithm 

Final ExaM

 Full Name:           Student ID:

1-[6 points] Draw each of the following graphs after completing the following operations:

2-[6 points] with the help of the provided ADTs, write anO(NlogN) solution to implement the following function:

floatmedian(int array[], int n)

The median function takes anarray and it’s sizen as parameters. It sorts the array, and then returns:

I. array[n/2],n is odd. Example for {7,5,6,8,8,3,2,1,5,7,7} it sorts them first {1,2,3,5,5,6,7,7,7,8,8} then returns6.

II. ( array[(n-1)/2]  +  array[(n+1)/2] ) / 2, if size is even. Example for {7,5,6,8,8,3,2,1,5,7,7,7} it sorts them first {1,2,3,5,5,6,7,7,7,7,8,8}, then returns (6+7)/2 that is 6.5.

§ You must use at least one of ADTs in the sorting process to be considered for partial marks.

§ The implementation must be O(NlogN) to be considered for partial marks.

3-[6 points] with the help of the provided ADTs, write anO(N) solution to implement the following function:

int *removeDuplicate(intarray, intn). The function takes anarray and it’s sizen. Then it returns a pointer to an array that has the unique elements in the inputarray. Example for running it on {4,1,4,3,5,7,6,6}, it returns {1,3,4,5,6,7}.

§ Sorting is not important (e.g. previous example could also return {3,1,4,5,6,7} or {7,5,4,6,1,3).

§ You must use at least one of the ADTs to be considered for partial marks.

§ The implementation must be O(N) to be considered for partial marks.

§ Assume that the elements in thearray are generated randomly.

4-[10 points] Considering the BST implementation, answer the following question:

I. [Multiple Choice] If we add the following printing function, what is the traversing of the function?[2 points]

template <class T>

void BST<T>::print(BSTNode<T>* const node){

    if (node==nullptr) return;

    print(node->left);

    std::cout<<node->val;

    print(node->right);   }

a) In order traversing function.

b) Pre-order traversing function.

c) Level-by-Level traversing function.

d) random traversing function.

II. [Multiple Choice] What is correct from the following statements:[2 points] 

a) copy_from(BSTNode<T>* node) traverse the copied-from tree (which is rooted by the parameter node) pre-orderly.

b) clear(BSTNode<T>* node) traverse the tree pre-orderly.

c) both are in order traversing.

d) None of the above

III. Can you convertprint() function in (I.) to post-order? Please write the code for the new function:[2 points]

IV. What is the complexity for the following functions in BST:[4 points]

5-[12 points] Variety!