17. Sorting - 18 Questions # 17. Sorting

18 Questions
Created by Y. Daniel Liang
Free
##### Sorting is ordering a list of objects. We can distinguish two types of sorting. If the number of objects is small enough to fits into the main memory, sorting is called internal sorting. If the number of objects is so large that some of them reside on external storage during the sort, it is called external sorting. This Python quiz is aimed at students, enthusiasts and job seekers with little or no programming experience. It aims to provide them with an understanding of the role of computers and python programming language. Build a Resume for FREE, that gets you a Job.
1. Suppose a list is [2, 9, 5, 4, 8, 1]. After the first pass of bubble sort, the list becomes

2, 9, 5, 4, 8, 1
2, 9, 5, 4, 1, 8
2, 5, 9, 4, 8, 1
2, 5, 4, 8, 1, 9

View Answer | Discuss in forum
2. The best-time complexity for bubble sort is _____________.

O(1)
O(logn)
O(n)
O(nlogn)

View Answer | Discuss in forum
3. The worst-time complexity for bubble sort is _____________.

O(logn)
O(n)
O(nlogn)
O(n*n)

View Answer | Discuss in forum
4. The time to merge two sorted lists of size n is _________

O(1)
O(logn)
O(n)
O(nlogn)

View Answer | Discuss in forum
5. The worst-time complexity for merge sort is _________

O(1)
O(logn)
O(n)
O(nlogn)

View Answer | Discuss in forum
6. The average-time complexity for merge sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

View Answer | Discuss in forum
7. What is correct about a pivot?

1. A pivot divides a list into two sublists of equal size.
2. A pivot can be chosen arbitrarily.
3. 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.
4. You should always choose a pivot that divides the list evenly.

1 & 2
2 & 3
3 & 4
1 & 4

View Answer | Discuss in forum
8. The worst-time complexity for quick sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

View Answer | Discuss in forum
9. The average-time complexity for quick sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

View Answer | Discuss in forum
10. Which of the following statements are true?

1. A heap is a complete binary tree.
2. Each node is greater than or equal to any of its children.
3. 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.
4. A heap is a full binary tree.

1, 2, 3
2, 3, 4
3, 4, 1
1, 2, 4

View Answer | Discuss in forum
11. 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.

one of the root's children
the larger child of the root
the smaller child of the root
the last node in the heap

View Answer | Discuss in forum
12. 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.

the new root
the last node in the heap
the left child of the root
the right child of the root

View Answer | Discuss in forum
13. A heap is represented using a list. Is the list [1, 2, 4, 5, 9, 3] a heap?

yes
no
can't say
none of these

View Answer | Discuss in forum
14. A heap is represented using a list. Is the list [64, 42, 59, 32, 39, 44] a heap?

yes
no
can't say
none of these

View Answer | Discuss in forum
15. The worst-time complexity for heap sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

View Answer | Discuss in forum
16. The average-time complexity for heap sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

View Answer | Discuss in forum
17. The most efficient algorithm for sorting integer keys is __________.

quick sort
merge sort
heap sort
radix sort

View Answer | Discuss in forum
18. The __________ algorithm does not compare keys.

quick sort
merge sort
heap sort
radix sort

View Answer | Discuss in forum