CS 101 FINAL EXAM QUESTIONS AND VERIFIED
ANSWERS
worst time complexity for min/max heap - Answers - O(1)
worst time complexity for inserting/deleting from heap - Answers - O(log n)
worst time complexity for queues and queue functions (ex. enQueue, deQueue): -
Answers - O(1)
worst time complexity for heapsort - Answers - O(n log n)
worst time complexity for inserting/deleting in Binary Search Tree: - Answers - O(n)
worst time complexity for push/pop on stack (array implementation) - Answers - O(1)
worst time complexity for inserting in hash table - Answers - O(n)
goal time complexity for inserting in hash table - Answers - O(1)
Binary Search Tree pre-order - Answers - root, left, right
Binary Search Tree post-order - Answers - left, right, root
Binary Search Tree in-order - Answers - left, root, right
enQueue() - Answers - adds new node after rear and moves rear to next node
deQueue() - Answers - removes front node and moves front to next node
parent equation for a 0 indexed heap - Answers - (i-1) / 2
left child equation for a 0 indexed heap - Answers - 2i + 1
right child equation for a 0 indexed heap - Answers - 2i + 2
where in memory is a pointer stored - Answers - the runtime stack
where in memory is an object stored - Answers - the heap
a good hash function should: - Answers - spread the input values over the range of
integer outputs
, which operation do hash tables not support efficiently: - Answers - sorting
which operation do min ordered heaps not support efficiently: - Answers - search
Huffman codes will provide the most benefit when: - Answers - 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. - Answers - false
(T or F) For a function that may contain a throw, the function's statements must be
surrounded by a try block. - Answers - 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. - Answers - true
(T or F) The big three functions for classes include a destructor, copy constructor, and
default constructor. - Answers - false
What is the minimum height of a BST with 10,000 nodes? - Answers - 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;"? - Answers - Copy
Constructor
How many steps does it take to build a BST, via repeated insertion? - Answers - O(n^2)
The worst-case to grow the size of a dynamic array by 1 is _____ steps? - Answers -
O(n)
The amortized cost to grow the size of a dynamic array by 1 is _____ steps? - Answers
- 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; - Answers - O(n)
What is the time complexity of this code fragment?
for (K=0; K< n; K=K+2)
sum += K; - Answers - O(n)
ANSWERS
worst time complexity for min/max heap - Answers - O(1)
worst time complexity for inserting/deleting from heap - Answers - O(log n)
worst time complexity for queues and queue functions (ex. enQueue, deQueue): -
Answers - O(1)
worst time complexity for heapsort - Answers - O(n log n)
worst time complexity for inserting/deleting in Binary Search Tree: - Answers - O(n)
worst time complexity for push/pop on stack (array implementation) - Answers - O(1)
worst time complexity for inserting in hash table - Answers - O(n)
goal time complexity for inserting in hash table - Answers - O(1)
Binary Search Tree pre-order - Answers - root, left, right
Binary Search Tree post-order - Answers - left, right, root
Binary Search Tree in-order - Answers - left, root, right
enQueue() - Answers - adds new node after rear and moves rear to next node
deQueue() - Answers - removes front node and moves front to next node
parent equation for a 0 indexed heap - Answers - (i-1) / 2
left child equation for a 0 indexed heap - Answers - 2i + 1
right child equation for a 0 indexed heap - Answers - 2i + 2
where in memory is a pointer stored - Answers - the runtime stack
where in memory is an object stored - Answers - the heap
a good hash function should: - Answers - spread the input values over the range of
integer outputs
, which operation do hash tables not support efficiently: - Answers - sorting
which operation do min ordered heaps not support efficiently: - Answers - search
Huffman codes will provide the most benefit when: - Answers - 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. - Answers - false
(T or F) For a function that may contain a throw, the function's statements must be
surrounded by a try block. - Answers - 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. - Answers - true
(T or F) The big three functions for classes include a destructor, copy constructor, and
default constructor. - Answers - false
What is the minimum height of a BST with 10,000 nodes? - Answers - 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;"? - Answers - Copy
Constructor
How many steps does it take to build a BST, via repeated insertion? - Answers - O(n^2)
The worst-case to grow the size of a dynamic array by 1 is _____ steps? - Answers -
O(n)
The amortized cost to grow the size of a dynamic array by 1 is _____ steps? - Answers
- 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; - Answers - O(n)
What is the time complexity of this code fragment?
for (K=0; K< n; K=K+2)
sum += K; - Answers - O(n)
