CMSC 341 Midterm 2 UPDATED Questions and CORRECT Answers

CMSC 341 Midterm 2 UPDATED Questions
and CORRECT Answers
(True or False) An AVL tree is a better choice than a red-black tree if your data structure will
have more reads and writes than retrieves. - CORRECT ANSWER - False


(True or False) In a balanced binary tree, the number of nodes grows exponentially with the
height. - CORRECT ANSWER - True


(True or False) In a skew heap, Extract-Min runs in amortized O(1) time. - CORRECT
ANSWER - False (O(log n))


(True or False) Increasing load factor is a strategy for reducing the number of hash collisions. -
CORRECT ANSWER - False


(True or False) Under ideal conditions, hash tables perform their basic operations in constant
time - CORRECT ANSWER - True


(True or False) A Red-Black tree implementation of a priority queue performs enqueue and
dequeue in O(log n) time. - CORRECT ANSWER - True


(True or False) Removing a node from a red-black tree may require 𝛀(log n) trinode
restructurings. - CORRECT ANSWER - False


(True or False) When extracting the maximum value from an array-based implementation of a
max-heap, we simply shift the elements of the array left after removing the maximum element. -
CORRECT ANSWER - False


(True or False) The depth of all red nodes in a red black tree must be the same. - CORRECT
ANSWER - False

, (True or False) Priority queues dequeue the oldest item in the queue. - CORRECT
ANSWER - False



Ordered Map ADT - CORRECT ANSWER - Stores key, value pairs
Insert and retrieve by key
Ordering by keys
Used to implement self-balancing BST (red-black tree)


Unordered Map ADT - CORRECT ANSWER - Stores key, value pairs
Insert and retrieve by key
No ordering by keys
Used to implement hash table


Red-Black Trees - CORRECT ANSWER - A red-black tree is a BST with the following
properties:
1.Every node is either red or black
2.The root is black
3.No red node has a red child
4.Every root-null path (a path from the root to a null node) in the tree passes through the same
number of black nodes


How many trinode restructurings are required for insert and erase in an AVL tree vs. the number
of restructurings and recolorings in a red-black tree? - CORRECT ANSWER - Red-Black
Tree:
Insertion - 𝑂 (log 𝑛) recolorings and one trinode restructuring
Erase - 𝑂(log 𝑛) recolorings and one additional trinode restructuring.


AVL Tree: 𝑂 (log 𝑛) trinode restructures