· Answer True or False · Question 4 Suppose that we implement heapsort using a 4

Question

·         Answer True or False

·         Question 4

Suppose that we implement heapsort using a 4-way heap (each node has 4 children) instead of a binary heap. Then, in the worst case, this 4-way heapsort does a constant times fewer number of compares and exchanges than (binary) heapsort.

·         Question 5

The number of compares to heapify a reverse-sorted array of N distinct items using bottom-up heap construction is ~ N.

·         Question 6

The expected number of compares to selection sort a uniformly random array of N distinct keys is ~ 1/2 N^2.

·         Question 7

The number of compares to insertion sort an array of N/2 1s interleaved with N/2 0s (e.g., 1 0 1 0 1 0 1 0 1 0) is ~ 1/8 N^2.

·         Question 8

The number of compares to insertion sort an array of N/2 1s interleaved with N/2 0s (e.g., 1 0 1 0 1 0 1 0 1 0) is ~ 1 N lg N.

·         Question 9

Given a binary heap with N distinct keys, the result (ignoring any array resizing) of deleting the maximum key and then inserting that key back into the heap yields the original binary heap.

·         Question 10

The number of compares to insert N distinct keys in descending order into an initially empty binary heap is ~ N.

·         Question 11

The main reason for stopping the scan on equal keys in quicksorting partitioning is to ensure stability.

·         Question 12

The number of compares to quicksort an array of N equal keys is ~ N.

·         Question 13

In the best case, the number of compares to 3-way quicksort an array of N keys (not necessarily distinct) is ~ N.

·         Question 18

Immediately after each merge in mergesort, the size of each of the subarrays known to be sorted is a power of 2, except possibly for the last subarray.

·         Question 19

Bottom-up mergesort uses only a constant amount of space (other than the input array).

Suppose that we implement heapsort using a 4-way heap (each node has 4 children) instead of a binary heap. Then, in the worst case, this 4-way heapsort does a constant times fewer number of compares and exchanges than (binary) heapsort.

Explanation / Answer

4......

False   

In the worst case, this 4-way heapsort does a constant the sum of all digits of the binary representation

6....

True

The expected number of compares to selection sort a uniformly random array of N distinct keys is ~ 1/2 N^2.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.