CS 101 FINAL EXAM QUESTIONS & ANSWERS
worst time complexity for min/max heap - Answer -O(1)
worst time complexity for inserting/deleting from heap - Answer -O(log n)
worst time complexity for queues and queue functions (ex. enQueue, deQueue): -
Answer -O(1)
worst time complexity for heapsort - Answer -O(n log n)
worst time complexity for inserting/deleting in Binary Search Tree: - Answer -O(n)
worst time complexity for push/pop on stack (array implementation) - Answer -O(1)
worst time complexity for inserting in hash table - Answer -O(n)
goal time complexity for inserting in hash table - Answer -O(1)
Binary Search Tree pre-order - Answer -root, left, right
Binary Search Tree post-order - Answer -left, right, root
Binary Search Tree in-order - Answer -left, root, right
enQueue() - Answer -adds new node after rear and moves rear to next node
deQueue() - Answer -removes front node and moves front to next node
parent equation for a 0 indexed heap - Answer -(i-1) / 2
left child equation for a 0 indexed heap - Answer -2i + 1
right child equation for a 0 indexed heap - Answer -2i + 2
where in memory is a pointer stored - Answer -the runtime stack
where in memory is an object stored - Answer -the heap
a good hash function should: - Answer -spread the input values over the range of
integer outputs
which operation do hash tables not support efficiently: - Answer -sorting
which operation do min ordered heaps not support efficiently: - Answer -search
, Huffman codes will provide the most benefit when: - Answer -there is a skewed
distribution of characters
(T or F) After an exception is thrown and a catch block executes, execution resumes
after the throw statement. - Answer -false
(T or F) For a function that may contain a throw, the function's statements must be
surrounded by a try block. - Answer -false
(T or F) A key advantage of a class template is relieving the programmer from having to
write redundant code that differs only by type. - Answer -true
(T or F) The big three functions for classes include a destructor, copy constructor, and
default constructor. - Answer -false
What is the minimum height of a BST with 10,000 nodes? - Answer -height = log base
2 (n)
height = log base 2 (10,000)
height = 13.28
= 13
Assuming "myClass prevObj" has already been declared, which special member
function will be called by the statement "myClass obj2 = prevObj;"? - Answer -Copy
Constructor
How many steps does it take to build a BST, via repeated insertion? - Answer -O(n^2)
The worst-case to grow the size of a dynamic array by 1 is _____ steps? - Answer -
O(n)
The amortized cost to grow the size of a dynamic array by 1 is _____ steps? - Answer -
O(1)
What is the time complexity of this code fragment?
for (J=n; J>0; J /= 2)
for (K=0; K<J; K++)
sum += K; - Answer -O(n)
What is the time complexity of this code fragment?
for (K=0; K< n; K=K+2)
sum += K; - Answer -O(n)
What is the time complexity of this code fragment?
for(i = 1; i < (n*n); i *= 2)
cout << i; - Answer -O(log n)
worst time complexity for min/max heap - Answer -O(1)
worst time complexity for inserting/deleting from heap - Answer -O(log n)
worst time complexity for queues and queue functions (ex. enQueue, deQueue): -
Answer -O(1)
worst time complexity for heapsort - Answer -O(n log n)
worst time complexity for inserting/deleting in Binary Search Tree: - Answer -O(n)
worst time complexity for push/pop on stack (array implementation) - Answer -O(1)
worst time complexity for inserting in hash table - Answer -O(n)
goal time complexity for inserting in hash table - Answer -O(1)
Binary Search Tree pre-order - Answer -root, left, right
Binary Search Tree post-order - Answer -left, right, root
Binary Search Tree in-order - Answer -left, root, right
enQueue() - Answer -adds new node after rear and moves rear to next node
deQueue() - Answer -removes front node and moves front to next node
parent equation for a 0 indexed heap - Answer -(i-1) / 2
left child equation for a 0 indexed heap - Answer -2i + 1
right child equation for a 0 indexed heap - Answer -2i + 2
where in memory is a pointer stored - Answer -the runtime stack
where in memory is an object stored - Answer -the heap
a good hash function should: - Answer -spread the input values over the range of
integer outputs
which operation do hash tables not support efficiently: - Answer -sorting
which operation do min ordered heaps not support efficiently: - Answer -search
, Huffman codes will provide the most benefit when: - Answer -there is a skewed
distribution of characters
(T or F) After an exception is thrown and a catch block executes, execution resumes
after the throw statement. - Answer -false
(T or F) For a function that may contain a throw, the function's statements must be
surrounded by a try block. - Answer -false
(T or F) A key advantage of a class template is relieving the programmer from having to
write redundant code that differs only by type. - Answer -true
(T or F) The big three functions for classes include a destructor, copy constructor, and
default constructor. - Answer -false
What is the minimum height of a BST with 10,000 nodes? - Answer -height = log base
2 (n)
height = log base 2 (10,000)
height = 13.28
= 13
Assuming "myClass prevObj" has already been declared, which special member
function will be called by the statement "myClass obj2 = prevObj;"? - Answer -Copy
Constructor
How many steps does it take to build a BST, via repeated insertion? - Answer -O(n^2)
The worst-case to grow the size of a dynamic array by 1 is _____ steps? - Answer -
O(n)
The amortized cost to grow the size of a dynamic array by 1 is _____ steps? - Answer -
O(1)
What is the time complexity of this code fragment?
for (J=n; J>0; J /= 2)
for (K=0; K<J; K++)
sum += K; - Answer -O(n)
What is the time complexity of this code fragment?
for (K=0; K< n; K=K+2)
sum += K; - Answer -O(n)
What is the time complexity of this code fragment?
for(i = 1; i < (n*n); i *= 2)
cout << i; - Answer -O(log n)
