DSA FINAL EXAM QUESTIONS AND
ANSWERS
Complexity of Singly Linked-List: time complexity of search - Correct Answers -O(n) -
Worst case: element is at the end, Best case: element is at the beginning
Complexity of Doubly Linked-List: time complexity of search - Correct Answers -O(n) -
worst case: need to traverse whole list, best case: key is head or tail
Complexity of Singly Linked-List: time complexity of adding to head/tail - Correct
Answers -adding to head - O(1) - Same for both best and worst case
adding to tail - O(n) - traverse to tail
Complexity of Doubly Linked-List: time complexity of adding to head/tail - Correct
Answers -head - O(1) - more steps than singly, but same complexity
tail - O(1) - tail pointer
Complexity of Singly Linked-List: time complexity of removing from head/tail - Correct
Answers -head - O(1) - Same for both best and worst case
tail - O(n) - traverse to tail
Complexity of Doubly Linked-List: time complexity of removing from head/tail - Correct
Answers -head - O(1) - more steps than singly, but same complexity
tail - O(1) - tail pointer
Complexity of Both Linked-List: space complexity for storing n nodes - Correct Answers
-O(n) - Linear space complexity
Complexity of Stack and Queue: time complexity for pushing
Assume singly linked list based stack and doubly linked list based queue - Correct
Answers -O(1) - Same for both best and worst case = add head of linked list
Complexity of Stack and Queue: time complexity for popping
Assume singly linked list based stack and doubly linked list based queue - Correct
Answers -O(1) - Same for both best and worst case = remove list head (stack) or list tail
(queue)
Complexity of Stack and Queue: space complexity for storing n objects in linked-list
based implementation
,Assume singly linked list based stack and doubly linked list based queue - Correct
Answers -O(n) - linked list space complexity
*for array-based implementation, space depends on array size (may be > n).
Complexity of Hash Table DAT: time complexity for search - Correct Answers -O(1) -
constant time complexity
Complexity of Hash Table SC: time complexity for search - Correct Answers -O(m) - m:
size of the longest chain, often m = O(n)
Complexity of Hash Table LP: time complexity for search - Correct Answers -O(h) - h:
table size, not necessarily dependent on n
Complexity of Hash Table DAT: time complexity for insertion - Correct Answers -O(1) -
Same for both best and worst case
Complexity of Hash Table SC: time complexity for insertion - Correct Answers -if add
key to head - add to list head - O(1)
if add key to tail - add to list tail - O(m)
m: size of the longest chain
Complexity of Hash Table LP: time complexity for insertion - Correct Answers -worst
case - only empty cell is above so check h cells
- check if cell is empty (T1)
- update index to next cell (T2)
total probing time is (T1 + T2) * n + T1 = O(n)
- after probing, add to empty cell (T3 = O(1))
- total time = O(n) + O(1) = )(n+1) = O(n)
(at most check n + 1 cells before
Complexity of Hash Table DAT: time complexity for deletion - Correct Answers -O(1) -
Same for both best and worst case
Complexity of Hash Table SC: time complexity for deletion - Correct Answers -- search
for node ... time O(m)
- remove node = delete on linked list = O(1)
Complexity of Hash Table LP: time complexity for deletion - Correct Answers -first apply
search ... O(h) in worst case
then delete target node O(1)
total time is O(h + 1) = O(h)
h: table size
Complexity of Hash Table DAT: space complexity for storing n elements - Correct
Answers -O(h) - which is O(k) if h = k + 1
, k: largest key
Complexity of Hash Table SC: space complexity for storing n elements assuming table
stores pointer - Correct Answers -table of h pointers, each 1 space (h * M1)
n nodes outside the table, each
- key integer (M2)
- next pointer (M3)
- any satellite data (M4 in total)
- in total, (M2 + M3 + M4) * n
in total, h * M1 + n * (M2 + M3 + M4) = O(h + n)
h: table size
Complexity of Hash Table SC: space complexity for storing n elements assuming table
stores nodes only - Correct Answers -n nodes outside the table, each
- key integer (M2)
- next pointer (M3)
- any satellite data (M4 in total)
- in total, (M2 + M3 + M4) * n
in total, n * (M2 + M3 + M4) = O(n)
h: table size
Complexity of Hash Table LP: space complexity for storing n elements - Correct
Answers -- no matter how many nodes, we always need to maintain a table size of size
"h".
- assume each object consumes M1 space
- in total, consumes M1 * h = O(h) space
* Space does not necessarily depend on n. However, if we further assume the smallest
necessary table size (which is n), then h = O(n) and therefore space is O(h) = O(n).
Binary tree height h = ? - Correct Answers -h = O(n) = Ω(log 2 n)
Space complexity for list based binary tree - Correct Answers -each node object
consumes space M = M1 + 3*M2
M1: space for interger
M2: space for node pointer
a tree of n nodes consumes space n*M = n*(M1+3*M2) = O(n)
Space complexity for array based binary tree - Correct Answers -space = array size *
cell space
each array cell stores a node object, which consumes M space (same as list based)
array size = max node index + 1
ANSWERS
Complexity of Singly Linked-List: time complexity of search - Correct Answers -O(n) -
Worst case: element is at the end, Best case: element is at the beginning
Complexity of Doubly Linked-List: time complexity of search - Correct Answers -O(n) -
worst case: need to traverse whole list, best case: key is head or tail
Complexity of Singly Linked-List: time complexity of adding to head/tail - Correct
Answers -adding to head - O(1) - Same for both best and worst case
adding to tail - O(n) - traverse to tail
Complexity of Doubly Linked-List: time complexity of adding to head/tail - Correct
Answers -head - O(1) - more steps than singly, but same complexity
tail - O(1) - tail pointer
Complexity of Singly Linked-List: time complexity of removing from head/tail - Correct
Answers -head - O(1) - Same for both best and worst case
tail - O(n) - traverse to tail
Complexity of Doubly Linked-List: time complexity of removing from head/tail - Correct
Answers -head - O(1) - more steps than singly, but same complexity
tail - O(1) - tail pointer
Complexity of Both Linked-List: space complexity for storing n nodes - Correct Answers
-O(n) - Linear space complexity
Complexity of Stack and Queue: time complexity for pushing
Assume singly linked list based stack and doubly linked list based queue - Correct
Answers -O(1) - Same for both best and worst case = add head of linked list
Complexity of Stack and Queue: time complexity for popping
Assume singly linked list based stack and doubly linked list based queue - Correct
Answers -O(1) - Same for both best and worst case = remove list head (stack) or list tail
(queue)
Complexity of Stack and Queue: space complexity for storing n objects in linked-list
based implementation
,Assume singly linked list based stack and doubly linked list based queue - Correct
Answers -O(n) - linked list space complexity
*for array-based implementation, space depends on array size (may be > n).
Complexity of Hash Table DAT: time complexity for search - Correct Answers -O(1) -
constant time complexity
Complexity of Hash Table SC: time complexity for search - Correct Answers -O(m) - m:
size of the longest chain, often m = O(n)
Complexity of Hash Table LP: time complexity for search - Correct Answers -O(h) - h:
table size, not necessarily dependent on n
Complexity of Hash Table DAT: time complexity for insertion - Correct Answers -O(1) -
Same for both best and worst case
Complexity of Hash Table SC: time complexity for insertion - Correct Answers -if add
key to head - add to list head - O(1)
if add key to tail - add to list tail - O(m)
m: size of the longest chain
Complexity of Hash Table LP: time complexity for insertion - Correct Answers -worst
case - only empty cell is above so check h cells
- check if cell is empty (T1)
- update index to next cell (T2)
total probing time is (T1 + T2) * n + T1 = O(n)
- after probing, add to empty cell (T3 = O(1))
- total time = O(n) + O(1) = )(n+1) = O(n)
(at most check n + 1 cells before
Complexity of Hash Table DAT: time complexity for deletion - Correct Answers -O(1) -
Same for both best and worst case
Complexity of Hash Table SC: time complexity for deletion - Correct Answers -- search
for node ... time O(m)
- remove node = delete on linked list = O(1)
Complexity of Hash Table LP: time complexity for deletion - Correct Answers -first apply
search ... O(h) in worst case
then delete target node O(1)
total time is O(h + 1) = O(h)
h: table size
Complexity of Hash Table DAT: space complexity for storing n elements - Correct
Answers -O(h) - which is O(k) if h = k + 1
, k: largest key
Complexity of Hash Table SC: space complexity for storing n elements assuming table
stores pointer - Correct Answers -table of h pointers, each 1 space (h * M1)
n nodes outside the table, each
- key integer (M2)
- next pointer (M3)
- any satellite data (M4 in total)
- in total, (M2 + M3 + M4) * n
in total, h * M1 + n * (M2 + M3 + M4) = O(h + n)
h: table size
Complexity of Hash Table SC: space complexity for storing n elements assuming table
stores nodes only - Correct Answers -n nodes outside the table, each
- key integer (M2)
- next pointer (M3)
- any satellite data (M4 in total)
- in total, (M2 + M3 + M4) * n
in total, n * (M2 + M3 + M4) = O(n)
h: table size
Complexity of Hash Table LP: space complexity for storing n elements - Correct
Answers -- no matter how many nodes, we always need to maintain a table size of size
"h".
- assume each object consumes M1 space
- in total, consumes M1 * h = O(h) space
* Space does not necessarily depend on n. However, if we further assume the smallest
necessary table size (which is n), then h = O(n) and therefore space is O(h) = O(n).
Binary tree height h = ? - Correct Answers -h = O(n) = Ω(log 2 n)
Space complexity for list based binary tree - Correct Answers -each node object
consumes space M = M1 + 3*M2
M1: space for interger
M2: space for node pointer
a tree of n nodes consumes space n*M = n*(M1+3*M2) = O(n)
Space complexity for array based binary tree - Correct Answers -space = array size *
cell space
each array cell stores a node object, which consumes M space (same as list based)
array size = max node index + 1
