I need the answers to these Multiple Choice questions 1.Give the array that resu
ID: 3677369 • Letter: I
Question
I need the answers to these Multiple Choice questions
1.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
A.58 32 45 91 89 49 77 65 36 94
B.58 32 45 77 36 94 65 91 89 49
C.58 77 65 36 32 45 94 91 89 49
D.58 32 45 77 65 36 94 91 89 49
2.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.99 92 72 78 90 38 19 20 76 44 32 14 27
B.99 92 72 78 90 19 38 20 76 44 32 14 27
C.14 92 72 78 90 38 19 20 76 44 32 99 27
D.19 92 72 78 90 38 99 20 76 44 32 14 27
3.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 38 47 52 53 80 81 91
B.22 25 29 47 52 80 81 53 38 91
C.22 25 29 47 52 53 80 81 38 91
D.22 25 29 47 52 80 53 81 38 91
4.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
A.14 38 42 43 66 51 52 88 93 72
B.14 38 42 43 51 66 52 88 93 72
C.14 38 42 43 51 52 66 88 93 72
D.14 38 42 43 51 52 66 72 88 93
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
A.44 55 65 72 74 98 16 22 36 54 18 52
B.44 55 65 72 74 98 16 22 54 52 36
18
C.44 55 65 72 74 98 16 22 54 36 52 18
D.44 55 65 72 74 98 16 18 22 36 52 54
6.Give the array that results after applying the standard 2-way partitioning subroutine from lecture to the following array:
58 47 90 27 82 83 99 16 41 57 22 13
A.16 47 13 27 22 57 41 58 99 83 82 90
B.13 16 22 27 41 47 57 58 82 83 90 99
C.16 47 13 22 27 57 41 58 99 83 82 90
D.16 47 13 27 22 57 41 58 99 82 83 90
7.Give the array that results after applying the standard 2-way partitioning subroutine from lecture to the following array:
B B B A B B B A A B B A
A.A A B B A A B B B B B B
B.A A B A B A B B B B B B
C.A A A A B B B B B B B B
D.A A B A B B A B B B B B
8.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 88 83 87 35 67 73 23 43 30
A.83 43 73 35 30 67 23
B.83 73 43 30 35 67 23
C.83 43 73 30 35 67 23
D.83 43 73 30 35 23 67
A.58 32 45 91 89 49 77 65 36 94
B.58 32 45 77 36 94 65 91 89 49
C.58 77 65 36 32 45 94 91 89 49
D.58 32 45 77 65 36 94 91 89 49
Explanation / Answer
Number of compares used by shellsort with the 3x+1 increments is at most by a small multiple of N times the number of increments used.
After 4th iteration The array is :
A.58 32 45 91 89 49 77 65 36 94
2)
After obtaining three keys we vobtain
C.14 92 72 78 90 38 19 20 76 44 32 99 27
3)after 6 exchanges in insertion sort
D.22 25 29 47 52 80 53 81 38 91
4)
A.14 38 42 43 66 51 52 88 93 72
5)
A.44 55 65 72 74 98 16 22 36 54 18 52
6)
B.13 16 22 27 41 47 57 58 82 83 90 99
7)
C. A A A A B B B B B B B B
8)
B.83 73 43 30 35 67 23