Final F19

SJSU CMPE 126 F19 Final Exam

First:________________ Last:________________ Last 4 id:_____

• 1. (1pt) Heap is a tree, but it can be stored as an array. Why?

  2. (2pt) A heap node X is stored at index n of the array.

  3. The array index of X's right child is ________________, index of X's parent is ___________________

  4. (3pt) The worst case complexity of quicksort is ______________. The worst case complexity of mergesort is ______________. In <15 words, under what conditions, quicksort is the preferred sorting method?

  5. (1pt) Name one advantage of searching in hash table comparing with searching in an array.

  6. (1pt) Name one disadvantage of searching in hash table comparing with searching in an array

  7. (2pt) Following is the declaration for queue of stock. Implement its copy constructor.

class queue

{ private:

stock *array;

int front, back;

int maxSize;

public:

queue(int maxsize);

~queue();

queue(queue&); //copy constructor

bool add(stock); // return true if success, false otherwise

stock delete();

}

• 1. (2pt) Continue with previous queue problem, Implement the add queue routine

  2. (3pt) Assume the following list of objects with keys: 7, 28, 40, 31, 5

The hash table size is 10 and the hash function is modulo 3. With quadratic probing method, show the resulting hash table.

• 1. (2pt) Following is a function to return the middle element of a forward linked list. The head of the linked list is passed as a parameter to it. But the code contains a bug. Find and describe the bug and correct the code.

ListNode* middleNode(ListNode* head)

{

ListNode *fast, *slow;

fast = head;

slow = head;

while(fast!=NULL)

{

slow = slow->next;

fast = fast->next->next;

}

return slow;

}

• 1. (3pt) Assume an array has the following list of keys: 15, 7, 48, 30, 31, 5, 20, 88, 52

Using quicksort with middle as the pivot to sort from small to large. Show the resulting list after one call to the partition procedure.

<<scratch area>>

• 1. (3pt) Complete the insertion sort routine for stock array A with ascending key, assuming Stock has > and < operator overloading.

void insertionSort( Stock A[], int n ) {

• 1. (2pt) Write an iterative function to perform binary search on an integer array. The function gets the following parameters: the stock array, the first and last index of the array and the element to be searched. It returns the index of the element if found.

int binarySearchIterative(int list[], int first ,int last, int item)

{

• 1. (2pt) Write a recursive function to perform binary search on an integer array. The function gets the following parameters: the stock array, the first and last index of the array and the element to be searched. It returns the index of the element if found.

int binarySearchRecursive(int list[], int first ,int last, int item)

{