Final S17

SJSU CMPE 126 S17 Final Exam

First:________________ Last:________________ Last 4 id:_____

Each problem earns 2 pt for correct answer, 0 pt for no answer, -1 pt for random mumbling. No partial point for 1 pt questions.

Assume there is a stock class and a stockNode class. The stock class supports streaming operator <<, equal operator ==, and less than operator < . The stockNode class is inherited from stock class.

Further assume there are classes for storing collection of stocks as follows:

DBarray.. stores stocks in a dynamic array

DBdlink.. stores stocks in a doubly-linked list

DBhash.. stores stocks in a hash table

DBheap.. stores stocks in a heap

Each DB class has add(stock&), delete(stock&), find(stock&) functions. In the following questions, DO NOT include these three functions in your answer (pt reduced if you do). But, do include all other required minimum functions and/or data members (pt reduced if you don’t).

• 1. Write the minimum stockNode.h to support other DB classes

class stockNode

• 1. Write the minimum DBarray.h (minus add/delete/find functions) where size of array is specified during construction time.

class DBarray

• 1. Write the minimum DBdlink.h (minus add/delete/find functions)

class DBdlink

• 1. Write the minimum DBhash.h (hint: what do you need to support find by hash)

class DBhash

• 1. Write the minimum DBheap.h (hint: what do you need to store stocks in a heap)

class DBheap

• 1. Write remove_nth (remove nth node) function for DBdlink. (hint: watch for boundary conditions)

void DBdlink::remove_nth(int n) {

• 1. One way to keep DBarray sorted is to insert every element in-order. Write the implement code (cpp code) for the insert-in-order function void DBarray::insert-in-order(stock& s).

void DBarray::insert-in-order(stock & s) {

• 1. What is the postfix notation for a - b * ( c / (d + f )) + g

• 1. (1 pt) What is a heap?

• 1. (1 pt) In < 10 words, what’s the main benefit of using heap?

.

• 1. Assume the following list of keys: 7, 28, 40, 31, 15, 42, 20, 88 with large key has higher priority.

  2. Show the resulting heap structure and list after it is heapified.

• 1. As a general database, name two common restrictions of hash? How do you mitigate these restrictions?

• 1. Assume the following list of keys: 7, 28, 31, 40, 8, 20, 18 and we use hash with quadratic probing. If hash table size is 11 and hash function is modulo 10, show the resulting hash table.

• 1. (1pt) In quick sort, what is the possible pitfall of picking the first object as the pivot?

• 1. Name two advantages merge sort has over quick sort in linked list data structures?

• 1. Write the function that solves the Tower Of Hanoi problem.

void TowerOfHanoi ( int N, char Src, char Dst, char Temp) // N number of disc