· Need the answers for these true or false questions Answer True or False 4-19 ·

Question

· Need the answers for these true or false questions

Answer True or False 4-19

·         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. TRUE

5. FALSE

6. TRUE

7. TRUE

8. FALSE

9. TRUE

10. FALSE

11. TRUE

12. FALSE

13. FALSE

18. TRUE

19. TRUE

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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