Introduction to Java Programming, Seventh Edition, Y. Daniel Liang
Chapter 26 Sorting
Section 26.2 Bubble Sort
1
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
2
The best-time complexity for bubble sort is _____________.
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
3
The worst-time complexity for bubble sort is _____________.
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
Section 26.3 Merge Sort
4
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)
5
The worst-time complexity for merge sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
6
The average-time complexity for merge sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
Section 26.4 Quick Sort
7
What is correct about a pivot?
A.
A pivot divides a list into two sublists of equal size.
B.
A pivot can be chosen arbitrarily.
C.
A pivot divides a list into two sublists, the elements in the first list are no larger than the pivot and the elements in the second list are larger than the pivot.
D.
You should always choose a pivot that divides the list evenly.
8
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
9
The worst-time complexity for quick sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
10
The average-time complexity for quick sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
Section 26.5 Heap Sort
11
A heap is represented using an array. Is the array {1 2 4 5 9 3} a heap?
A.
Yes
B.
No
12
A heap is represented using an array. Is the array {64 42 59 32 39 44} a heap?
A.
Yes
B.
No
13
The worst-time complexity for heap sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
14
The average-time complexity for heap sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)