17. Sorting - 18 Questions


17. Sorting

17. Sorting

18 Questions
Created by Y. Daniel Liang - http://www.cs.armstrong.edu/liang/index.html
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.
  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