.
Algorithms Final Exam Study Guide
The min-heap property states that for every node i other than the root, A[PAERENT(i)] ≤ A[i].
A.
True
B.
False
Correct Answer
A. True
Explanation
The min-heap property states that for every node i other than the root, the value of its parent
node (A[PAERENT(i)]) is less than or equal to the value of the node itself (A[i]). This means that
in a min-heap, the smallest element is always at the root, and for any other node, its value is
greater than or equal to its parent's value. Therefore, the given statement is true.
Rate this question:
2.
,An array constructed with the values [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] is a max heap.
A.
True
B.
False
Correct Answer
B. False
3.
For a node A at index i in a heap, the right child of A can be computed as 2*i.
A.
True
B.
False
Correct Answer
B. False
Explanation
The given statement is false. The right child of a node A in a heap can be computed as 2*i + 1,
not 2*i. This is because in a heap, the left child of a node is located at index 2*i, and the right
child is located at index 2*i + 1.
,Rate this question:
4.
The master method can be used to solve all recurrence equations that have the form T(n) =
aT(n/b) + f(n).
A.
True
B.
False
Correct Answer
B. False
Explanation
The master method can only be used to solve recurrence equations that have the form T(n) =
aT(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is an asymptotically positive function. Therefore, the
statement "The master method can be used to solve all recurrence equations that have the
form T(n) = aT(n/b) + f(n)" is false.
Rate this question:
1
5.
Quicksort has a worst-case running time of θ(n^2).
A.
, True
B.
False
Correct Answer
A. True
Explanation
Quicksort has a worst-case running time of θ(n^2) because in certain scenarios, the algorithm
can make poor pivot choices, resulting in highly unbalanced partitions. When the pivot is
consistently chosen as the smallest or largest element, the algorithm performs poorly, taking
quadratic time to sort the array. However, on average, Quicksort has a time complexity of θ(n
log n) due to its efficient partitioning and recursive nature.
Rate this question:
6.
One good reason for using a hash table would be to reduce storage requirements.
A.
True
B.
False
Correct Answer
Algorithms Final Exam Study Guide
The min-heap property states that for every node i other than the root, A[PAERENT(i)] ≤ A[i].
A.
True
B.
False
Correct Answer
A. True
Explanation
The min-heap property states that for every node i other than the root, the value of its parent
node (A[PAERENT(i)]) is less than or equal to the value of the node itself (A[i]). This means that
in a min-heap, the smallest element is always at the root, and for any other node, its value is
greater than or equal to its parent's value. Therefore, the given statement is true.
Rate this question:
2.
,An array constructed with the values [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] is a max heap.
A.
True
B.
False
Correct Answer
B. False
3.
For a node A at index i in a heap, the right child of A can be computed as 2*i.
A.
True
B.
False
Correct Answer
B. False
Explanation
The given statement is false. The right child of a node A in a heap can be computed as 2*i + 1,
not 2*i. This is because in a heap, the left child of a node is located at index 2*i, and the right
child is located at index 2*i + 1.
,Rate this question:
4.
The master method can be used to solve all recurrence equations that have the form T(n) =
aT(n/b) + f(n).
A.
True
B.
False
Correct Answer
B. False
Explanation
The master method can only be used to solve recurrence equations that have the form T(n) =
aT(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is an asymptotically positive function. Therefore, the
statement "The master method can be used to solve all recurrence equations that have the
form T(n) = aT(n/b) + f(n)" is false.
Rate this question:
1
5.
Quicksort has a worst-case running time of θ(n^2).
A.
, True
B.
False
Correct Answer
A. True
Explanation
Quicksort has a worst-case running time of θ(n^2) because in certain scenarios, the algorithm
can make poor pivot choices, resulting in highly unbalanced partitions. When the pivot is
consistently chosen as the smallest or largest element, the algorithm performs poorly, taking
quadratic time to sort the array. However, on average, Quicksort has a time complexity of θ(n
log n) due to its efficient partitioning and recursive nature.
Rate this question:
6.
One good reason for using a hash table would be to reduce storage requirements.
A.
True
B.
False
Correct Answer
