Introduction to Java Programming, Includes Data Structures, Eleventh Edition, Y. Daniel Liang

This quiz is for students to practice. A large number of additional quiz is available for instructors using Quiz Generator from the Instructor's Resource Website. Videos for Java, Python, and C++ can be found at https://yongdanielliang.github.io/revelvideos.html.

Chapter 23 Sorting


Section 23.2 Insertion Sort
23.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)

23.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)

Section 23.3 Bubble Sort
23.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

23.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)

23.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)

Section 23.4 Merge Sort
23.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)

23.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)

23.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)

Section 23.5 Quick Sort
23.9  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.

23.10  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

23.11  The worst-time complexity for quick sort is _________.
A. O(1)
B. O(logn)
C. O(n)
D. O(nlogn)
E. O(n*n)

23.12  The average-time complexity for quick sort is _________.
A. O(1)
B. O(logn)
C. O(n)
D. O(nlogn)
E. O(n*n)

23.13  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}

Section 23.6 Heap Sort
23.14  Which of the following statements are true?
A. A heap is a complete binary tree.
B. Each node is greater than or equal to any of its children.
C. A binary tree is complete if every level of the tree is full except that the last level may not be full and all the leaves on the last level are placed left-most.
D. A heap is a full binary tree.

23.15  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

23.16  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

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

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

23.19  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.20  The average-time complexity for heap sort is _________
A. O(1)
B. O(logn)
C. O(n)
D. O(nlogn)
E. O(n*n)

23.21  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

23.22  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}

Section 23.7 Bucket Sort and Radix Sort
23.23  The most efficient algorithm for sorting integer keys is __________.
A. quick sort
B. merge sort
C. heap sort
D. radix sort

23.24  The __________ algorithm does not compare keys.
A. quick sort
B. merge sort
C. heap sort
D. radix sort