Give the array that results immediately after the 4-sorting phase (not necessari
ID: 3677301 • Letter: G
Question
Give the array that results immediately after the 4-sorting phase (not necessarily after 4 exchanges) of Shellsort using Knuth's 3x+1 increments (...-121-40-13-4-1) on the following array:
89 49 45 91 58 36 94 77 65 32
58 32 45 91 89 49 77 65 36 94
58 32 45 77 36 94 65 91 89 49
58 77 65 36 32 45 94 91 89 49
58 32 45 77 65 36 94 91 89 49
Give the sequence of the keys in the array that results after inserting the sequence of 3 keys
32 38 27
into the following maximum-oriented binary heap of size 10:
99 92 72 78 90 14 19 20 76 44
99 92 72 78 90 38 19 20 76 44 32 14 27
99 92 72 78 90 19 38 20 76 44 32 14 27
14 92 72 78 90 38 19 20 76 44 32 99 27
19 92 72 78 90 38 99 20 76 44 32 14 27
Give the array that results after the first 6 exchanges (not iterations!)
when insertion sorting the following array:
25 29 47 52 80 81 22 53 38 91
22 25 29 38 47 52 53 80 81 91
22 25 29 47 52 80 81 53 38 91
22 25 29 47 52 53 80 81 38 91
22 25 29 47 52 80 53 81 38 91
A programmer might prefer heapsort to mergesort because it uses only constant space (other than the input array).
True
False
The height of a complete 4-way tree (each node has 4 children) with N nodes is exactly floor(log_4 N).
True
False
In the best case, the number of compares to insert N distinct keys into an initially empty binary heap is linearithmic.
True
False
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.
True
False
In the best case, the number of compares to Shellsort (with Knuth's 3x+1 increments) an array of N distinct keys is ~ N log_3 N.
True
False
Give the array that results after the first 4 exchanges when selection sorting the following array:
72 43 88 42 66 51 52 38 93 14
14 38 42 43 66 51 52 88 93 72
14 38 42 43 51 66 52 88 93 72
14 38 42 43 51 52 66 88 93 72
14 38 42 43 51 52 66 72 88 93
The number of compares to insertion sort an array of N distinct keys is equal to the number of inversions in the array.
True
False
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.
True
False
58 32 45 91 89 49 77 65 36 94
58 32 45 77 36 94 65 91 89 49
58 77 65 36 32 45 94 91 89 49
58 32 45 77 65 36 94 91 89 49
Explanation / Answer
(a) True
(b) False
(c) True
(d) False
(e) True
(f) False
(g) True
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.