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).
Write the minimum stockNode.h to support other DB classes
class stockNode
Write the minimum DBarray.h (minus add/delete/find functions) where size of array is specified during construction time.
class DBarray
Write the minimum DBdlink.h (minus add/delete/find functions)
class DBdlink
Write the minimum DBhash.h (hint: what do you need to support find by hash)
class DBhash
Write the minimum DBheap.h (hint: what do you need to store stocks in a heap)
class DBheap
Write remove_nth (remove nth node) function for DBdlink. (hint: watch for boundary conditions)
void DBdlink::remove_nth(int n) {
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) {
What is the postfix notation for a - b * ( c / (d + f )) + g
(1 pt) What is a heap?
(1 pt) In < 10 words, what’s the main benefit of using heap?
.
Assume the following list of keys: 7, 28, 40, 31, 15, 42, 20, 88 with large key has higher priority.
Show the resulting heap structure and list after it is heapified.
As a general database, name two common restrictions of hash? How do you mitigate these restrictions?
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.
(1pt) In quick sort, what is the possible pitfall of picking the first object as the pivot?
Name two advantages merge sort has over quick sort in linked list data structures?
Write the function that solves the Tower Of Hanoi problem.
void TowerOfHanoi ( int N, char Src, char Dst, char Temp) // N number of disc