CMPSC 465 Data Structures & Algorithms
Fall 2021 Antonio Blanca and David Koslicki Quiz 2 Solutions
Monday, Sep 13, 2021
1. (2 pts.) Any non-root node can simply be deleted
from a binary min-heap without any extra steps
needed.
(a) True
(b) False
Answer False
To delete a node, its value is swapped with the
value of the last node on the heap, and then we
many need to run Heapify-UP or Heapify-Down.
2. (2 pts.) The array A = [10,20,50,30,80,60,70]
is a min heap.
(a) True
(b) False
Answer (a) True
This is a full binary tree where all the parent nodes
are less than their respective children.
3. (2 pts.) It is possible to compute all the Fi-
bonacci numbers up to the n-th one with an algo-
rithm whose running time is O(n2).
(a) True
(b) False
Answer (a) True
4. (2 pts.) Heapify-up and Heapify-down each may
require O(logn) swaps.
(a) True
(b) False
Answer (a) True.
Proof derived in class.
5. (2 pts.) With an array representation of binary
heap, how do you get the position of the parent
of a node at position p?
(a) b p−12 c
(b) b p+12 c
(c) d p−12 e
(d) d p+12 e
Answer b p−12 c
Discussed in class.
CMPSC 465, Fall 2021, Quiz 2 Solutions 1