### Introduction to Programming Using Python, Y. Daniel Liang

This quiz is for students to practice. A large number of additional quiz is available for instructors from the Instructor's Resource Website.

### Chapter 17 Sorting

Section 17.2 Bubble Sort
17.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

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

17.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 17.3 Merge Sort
17.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)

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

17.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 17.4 Quick Sort
17.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.

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

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

17.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 17.5 Heap Sort
17.11  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.

17.12  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

17.13  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

17.14  A heap is represented using a list. Is the list [1, 2, 4, 5, 9, 3] a heap?
A. Yes
B. No

17.15  A heap is represented using a list. Is the list [64, 42, 59, 32, 39, 44] a heap?
A. Yes
B. No

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

17.17  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 17.6 Bucket Sort and Radix Sort
17.18  The most efficient algorithm for sorting integer keys is __________.
A. quick sort
B. merge sort
C. heap sort