CS计算机代考程序代写 data structure algorithm CMPSC 465 Data Structures & Algorithms

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