Question 1

If a min-heap has 1024 nodes, what is its height?
A) 10
B) 11
C) 12
D) impossible to determine

Accepted Answer

A min-heap is a complete binary tree, and the height of a complete binary tree with n nodes is ⌊log2(n)⌋. For 1024 nodes, the height is ⌊log2(1024)⌋ = 10. However, since the height is counted from 0, the height is 10, not 11.

Question 2

Given the MinHeap class discussed in section 17.6, select the statement(s) needed to complete the following method, which displays the n smallest values in the parameter array. public static void nSmallestValues(Comparable[] array, int n)
{
MinHeap h = new MinHeap();
For(Comparable value : array)
{
h.add(value);
}
System.out.print(n + " smallest value(s): ");
For(int i = 0; i < n; ++i)
{
___________________________
}
}
A) System.out.println(h.remove());
B) System.out.println(h.peek());
C) System.out.println(array[i]);
D) System.out.println(h.elements.get(i));

Accepted Answer

The method should remove the smallest element from the MinHeap using `h.remove()` and print it, as this operation retrieves and removes the smallest element from the heap.

Question 3

What is the complexity of adding an element to a heap? A) O(1) B) O(log (n)) C) O(n log (n)) D) O(n²)

Accepted Answer

Adding an element to a heap involves placing the element at the end and then performing an "up-heap" or "bubble-up" operation, which takes O(log n) time in the worst case.

Question 4

Which action(s) will invalidate a min-heap so that, it may no longer have the properties of a min-heap?
I change the value of the root node
II remove the lowest level, right-most node
III remove the lowest level, left-most node
A) III
B) I and II
C) II and III
D) I and III

Accepted Answer

Changing the value of the root node (I) or removing the lowest level, left-most node (III) will invalidate a min-heap.

Question 5

What is the complexity of removing an element from a heap? A) O(1) B) O(log (n)) C) O(n log (n)) D) O(n²)

Accepted Answer

Removing an element from a heap involves removing the root and then re-heapifying, which takes O(log(n)) time due to the need to maintain the heap property by sifting down the new root.

Question 6

What is the efficiency of the heapsort algorithm? A) O(1) B) O(log (n)) C) O(n log (n)) D) O(n²)

Accepted Answer

The answer of What is the efficiency of the heapsort...

Question 7

When we map a min-heap with n elements to an array with n + 1 elements, we ignore array element 0, and place the root value at which array index?
A) 1
B) 2
C) n
D) n+1

Accepted Answer

In a min-heap mapped to an array, the root value is placed at index 1 when ignoring index 0.

Question 8

If we have a heap with n elements, and we add another n elements to it, what is the maximum increase of height associated with the binary tree representation of the heap?
A) 1
B) 2
C) n-1
D) n

Accepted Answer

The height of a binary heap is determined by the number of levels needed to accommodate all elements. Adding n elements to a heap with n elements can at most increase the height by 1, as the heap grows in a balanced manner.

Question 9

When we map a min-heap with n elements to an array with n + 1 elements, the right child of the root is stored at which array index?
A) 1
B) 2
C) 3
D) 4

Accepted Answer

In a 1-based index array representation of a min-heap, the right child of the root (which is at index 1) is stored at index 3.

Question 10

How many times during the heapsort algorithm does the fixHeap method need to be called for a max-heap with n elements?
A) log(n)
B) n-1
C) n
D) n+1

Accepted Answer

Title How many times during the heapsort algorithm does the fixHeap method need to be called for a max-heap with n elements?

Quiz 17: Tree Structures

If a min-heap has 1024 nodes, what is its height?

What is the complexity of adding an element to a heap?

Which action(s) will invalidate a min-heap so that, it may no longer have the properties of a min-heap? I change the value of the root node II remove the lowest level, right-most node III remove the lowest level, left-most node

What is the complexity of removing an element from a heap?

What is the efficiency of the heapsort algorithm?

When we map a min-heap with n elements to an array with n + 1 elements, we ignore array element 0, and place the root value at which array index?

If we have a heap with n elements, and we add another n elements to it, what is the maximum increase of height associated with the binary tree representation of the heap?

When we map a min-heap with n elements to an array with n + 1 elements, the right child of the root is stored at which array index?

How many times during the heapsort algorithm does the fixHeap method need to be called for a max-heap with n elements?