Chapter 23

Question 1

The best-time complexity for insertion sort is _____________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 1

C.O(n)

Question 2

The worst-time complexity for insertion sort is _____________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 2

E.O(n*n)

Question 3

Suppose a list is {2, 9, 5, 4, 8, 1}. After the first pass of bubble sort, the list becomes

		A.
2, 9, 5, 4, 8, 1
		B.
2, 9, 5, 4, 1, 8
		C.
2, 5, 9, 4, 8, 1
		D.
2, 5, 4, 8, 1, 9
		E.
2, 1, 5, 4, 8, 9

Answer 3

D.2, 5, 4, 8, 1, 9

Question 4

The best-time complexity for bubble sort is
_____________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 4

C.O(n)

Question 5

The worst-time complexity for bubble sort is _____________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 5

E.O(n*n)

Question 6

The time to merge two sorted lists of size n is _________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 6

C.O(n)

Question 7

The worst-time complexity for merge sort is _________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 7

D.O(nlogn)

Question 8

The average-time complexity for merge sort is _________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 8

D.O(nlogn)

Question 9

Suppose you choose the first element as a pivot in the list {5 2 9 3 8 4 0 1 6 7}. Using the partition algorithm in the book, what is the new list after the partition?

		A.
5 2 9 3 8 4 0 1 6 7
		B.
4 2 3 0 1 5 6 7 9 8
		C.
4 2 1 3 0 5 8 9 6 7
		D.
2 3 4 0 1 5 9 8 6 7
		E.
2 3 4 0 1 5 6 7 8 9

Answer 9

C.

4 2 1 3 0 5 8 9 6 7

Question 10

The worst-time complexity for quick sort is _________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 10

E.O(n*n)

Question 11

The average-time complexity for quick sort is _________.

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 11

D.O(nlogn)

Question 12

Using the partition algorithm to partition an array {5, 8, 10, 3, 4, 19, 2} for a quick sort, what is the resulting array after the partition?

		A.
{5, 8, 10, 3, 4, 19, 2}
		B.
{2, 3, 4, 5, 8, 10, 19}
		C.
{2, 3, 4, 5, 10, 19, 8}
		D.
{3, 2, 4, 5, 10, 19, 8}
		E.
{3, 2, 4, 5, 8, 10, 19}

Answer 12

D.{3, 2, 4, 5, 10, 19, 8}

Question 13

To remove the root, you need to start a process by first placing _______ to the place of the root and move it down to maintain the heap property.

		A.
one of the root's children
		B.
the larger child of the root
		C.
the smaller child of the root
		D.
the last node in the heap

Answer 13

D.the last node in the heap

Question 14

To add a new node, you need to start a process by first placing it as _______ and move it up to maintain the heap property.

		A.
the new root
		B.
the last node in the heap
		C.
the left child of the root
		D.
the right child of the root

Answer 14

B.the last node in the heap

Question 15

A heap is represented using an array. Is the array {1 2 4 5 9 3} a heap?

	A. Yes
	B. No

Answer 15

B. No

Question 16

A heap is represented using an array. Is the array {64 42 59 32 39 44} a heap?

	A. Yes
	B. No

Answer 16

A. Yes

Question 17

The worst-time complexity for heap sort is _________

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 17

D.O(nlogn)

Question 18

The average-time complexity for heap sort is _________

		A.
O(1)
		B.
O(logn)
		C.
O(n)
		D.
O(nlogn)
		E.
O(n*n)

Answer 18

D.O(nlogn)

Question 19

Suppose a heap is stored in an array list as follows: {100, 55, 92, 23, 33, 81}. The parent of 81 is _______.

		A.
100
		B.
55
		C.
92
		D.
23
		E.
33

Answer 19

C.92

Question 20

Suppose a heap is stored in an array list as follows: {100, 55, 92, 23, 33, 81}. After inserting 103, what is the content of the array list?

		A.
{100, 55, 92, 23, 33, 81, 103}
		B.
{100, 55, 103, 23, 33, 92, 81}
		C.
{103, 55, 92, 23, 33, 81, 92}
		D.
{103, 55, 100, 23, 33, 81, 92}
		E.
{103, 55, 92, 23, 33, 81, 100}

Answer 20

D.{103, 55, 100, 23, 33, 81, 92}

Question 21

The most efficient algorithm for sorting integer keys is __________.

		A.
quick sort
		B.
merge sort
		C.
heap sort
		D.
radix sort

Answer 21

D.radix sort

Question 22

The __________ algorithm does not compare keys.

		A.
quick sort
		B.
merge sort
		C.
heap sort
		D.
radix sort

Answer 22

D.radix sort