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