Quesiton 3 Give the sequence of the keys in the array that results after inserti
ID: 3843336 • Letter: Q
Question
Quesiton 3
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
a.14 92 72 78 90 38 19 20 76 44 32 99 27
b. 99 92 72 78 90 38 19 20 76 44 32 14 27
c,19 92 72 78 90 38 99 20 76 44 32 14 27
d. 99 92 72 78 90 19 38 20 76 44 32 14 27
Quesiton 4
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
a.22 25 29 47 52 80 81 53 38 91
b.22 25 29 38 47 52 53 80 81 91
c.22 25 29 47 52 80 53 81 38 91
d.22 25 29 47 52 53 80 81 38 91
Quesiton 5
Give the array that results immediately after the 7th call (and return) from merge() when top-down mergesorting the following array of size 12:
74 72 55 65 98 44 22 16 54 36 52 18
Question 10
Give the sequence of keys in the array that results after performing 3 successive delete-the-max operations on the following maximum-oriented binary heap of size 10:
94 83 49 58 59 31 23 12 57 25
a.58 57 49 12 25 23 31
b.58 57 49 12 31 25 23
c.58 57 49 25 12 31 23
d.58 57 49 12 25 31 23
Question 11
Give the array that results after applying Dijkstra's 3-way partitioning subroutine from lecture to the following array:
52 37 65 44 78 52 83 99 52 52
a.37 44 52 65 78 52 83 99 52 52
b.37 44 52 52 52 52 65 78 83 99
c.37 44 52 52 52 52 83 78 99 65
d.37 44 52 52 52 52 99 83 78 65
Question 12
Give the array that results after applying the standard 2-way partitioning subroutine from lecture to the following array:
65 99 47 32 57 86 68 10 76 34 63 69
a.10 63 47 32 57 34 65 68 69 76 86 99
b.10 47 63 32 57 34 65 68 76 86 99 69
c.10 63 47 32 57 34 65 68 76 86 99 69
d.10 63 47 32 57 65 34 68 76 86 99 69
Question 13
Give the array that results after the first 4 exchanges when selection sorting the following array:
62 83 27 88 42 84 36 47 10 45
a.10 27 36 42 84 88 83 47 62 45
b.10 27 36 42 88 84 83 47 62 45
c.10 27 36 42 47 62 45 88 84 83
d.10 27 36 42 47 45 62 88 84 83
Question 14
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:
32 38 37 23 50 35 48 27 19 29
a.19 29 37 23 35 32 48 27 38 50
b.19 29 32 35 37 23 48 27 50 38
c.19 23 29 32 35 37 48 27 50 38
d.19 29 37 23 32 35 48 27 50 38
Quesiton 19
Give the array that results after applying Dijkstra's 3-way partitioning subroutine from lecture to the following array:
46 22 67 85 23 64 54 46 81 46
a.22 23 46 46 46 54 64 81 85 67
b.22 23 46 46 46 54 64 67 81 85
c.22 46 67 23 46 46 54 64 81 85
d.22 23 46 46 46 54 81 64 85 67
a.14 92 72 78 90 38 19 20 76 44 32 99 27
b. 99 92 72 78 90 38 19 20 76 44 32 14 27
c,19 92 72 78 90 38 99 20 76 44 32 14 27
d. 99 92 72 78 90 19 38 20 76 44 32 14 27
Explanation / Answer
Quesiton 3
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
b. 99 92 72 78 90 38 19 20 76 44 32 14 27 is the answer.
Quesiton 4
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
a.22 25 29 47 52 80 81 53 38 91
Quesiton 5
Give the array that results immediately after the 7th call (and return) from merge() when
top-down mergesorting the following array of size 12:
74 72 55 65 98 44 22 16 54 36 52 18
b.44 55 65 72 74 98 16 22 54 36 52 18
Question 10
Give the sequence of keys in the array that results after performing 3 successive
delete-the-max operations on the following maximum-oriented binary heap of size 10:
94 83 49 58 59 31 23 12 57 25
d.58 57 49 12 25 31 23