Introduction to Java Programming, Sixth Edition, Y. Daniel Liang
Chapter 23 Algorithm Efficiency and Sorting
Section 23.2 Estimating Algorithm Efficiency
1
Estimating algorithm efficiency is ________
A.
to measure their actual execution time.
B.
to estimate their execution time.
C.
to estimate their growth function.
2
What is the number of iterations in the following loop:
int count = 5;
while (count < n) {
count = count + 3;
}
A.
n - 5
B.
n - 3
C.
n / 3 - 1
D.
(n - 5) / 3
E.
the ceiling of (n - 5) / 3
3
An input that results in the shortest execution time is called the _____________.
A.
best-case input
B.
worst-case input
C.
average-case input
4
Why is the analysis often for the worst case?
A.
Best-case is not representative,
B.
Worst-case is not representative,but worst-case analysis is very useful. You can show that the algorithm will never be slower than the worst-case.
C.
Average-case analysis is ideal, but difficult to perform, because it is hard to determine the relative probabilities and distributions of various input instances for many problems.
5
O(1) is ________.
A.
constant time
B.
logarithmic time
C.
linear time
D.
log-linear time
6
Which of the following complexity is O(nlogn)
A.
300n + 400n*n
B.
23nlogn + 50
C.
45n + 45nlogn + 503
D.
n*n*n + nlogn
7
On an average, linear search searches
A.
the whole list
B.
half of the list
C.
just one element in the list
D.
one fourth of the list
8
For a sorted list of 1024 elements, a binary search takes at most _______ comparisons.
A.
11
B.
100
C.
512
D.
6
9
A list is sorted by selecting the largest element in the list and swap it with the last one. This technique is called _____.
A.
insertion sort
B.
selection sort
C.
bubble sort
D.
merge sort
E.
quick sort
Section 23.3 Bubble Sort
10
Suppose a list is {2, 9, 5, 4, 8, 1}. After the first pass, 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
11
The best-time complexity for bubble sort is _____________.
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
12
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 23.4 Merge Sort
13
The time to merge two sorted list of size n is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
14
The worst-time complexity for merge sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
15
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 23.5 Quick Sort
16
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.
17
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
18
The worst-time complexity for quick sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
19
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 23.6 Heap Sort
20
A heap is represented using an array. Is the array {1 2 4 5 9 3} a heap?
A.
Yes
B.
No
21
A heap is represented using an array. Is the array {64 42 59 32 39 44} a heap?
A.
Yes
B.
No
22
The worst-time complexity for heap sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)
23
The average-time complexity for heap sort is _________
A.
O(1)
B.
O(logn)
C.
O(n)
D.
O(nlogn)
E.
O(n*n)