Introduction to Programming with C++, Third 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.

Many questions in this edition have been updated in the new edition. Please check with the publisher on the newest edition.

Chapter 19 Sorting


Section 19.2 Insertion Sort
19.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)

19.2  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 19.3 Bubble Sort
19.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

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

19.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 19.4 Merge Sort
19.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)

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

19.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 19.5 Quick Sort
19.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.

19.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

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

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

Section 19.6 Heap Sort
19.13  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.

19.14  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

19.15  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

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

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

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

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

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

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