Scribd Logo
Upload

Welcome to Scribd!

  • 203 views

    MCQs On Sorting

    Uploaded by

    Elijah Ibsa
    This document provides 30 multiple choice questions about sorting algorithms, their properties, time complexities, and applications. Some of the key sorting algorithms covered include merge sort, quicksort, heap sort, insertion sort, selection sort, counting sort, radix sort, and bucket sort. The questions test understanding of concepts like stable vs unstable sorting, comparison vs non-comparison sorting, worst case time complexities, and applicability of different algorithms based on input properties.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd

    MCQs On Sorting

    Uploaded by

    Elijah Ibsa
    203 views16 pages
    This document provides 30 multiple choice questions about sorting algorithms, their properties, time complexities, and applications. Some of the key sorting algorithms covered include merge sort, quicksort, heap sort, insertion sort, selection sort, counting sort, radix sort, and bucket sort. The questions test understanding of concepts like stable vs unstable sorting, comparison vs non-comparison sorting, worst case time complexities, and applicability of different algorithms based on input properties.

    Original Title

    MCQs on Sorting

    Copyright

    © © All Rights Reserved

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides 30 multiple choice questions about sorting algorithms, their properties, time complexities, and applications. Some of the key sorting algorithms covered include merge sort, quicksort, heap sort, insertion sort, selection sort, counting sort, radix sort, and bucket sort. The questions test understanding of concepts like stable vs unstable sorting, comparison vs non-comparison sorting, worst case time complexities, and applicability of different algorithms based on input properties.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    203 views16 pages

    MCQs On Sorting

    Uploaded by

    Elijah Ibsa
    This document provides 30 multiple choice questions about sorting algorithms, their properties, time complexities, and applications. Some of the key sorting algorithms covered include merge sort, quicksort, heap sort, insertion sort, selection sort, counting sort, radix sort, and bucket sort. The questions test understanding of concepts like stable vs unstable sorting, comparison vs non-comparison sorting, worst case time complexities, and applicability of different algorithms based on input properties.

    Copyright:

    © All Rights Reserved
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 16

    MCQs on Sorting with answers

    1. Which of the following is not a stable sorting algorithm?

    a) Insertion sort

    b) Selection sort

    c) Bubble sort

    d) Merge sort

    View Answer / Hide Answer

    ANSWER: B

    2. Which of the following is a stable sorting algorithm?

    a) Merge sort

    b) Typical in-place quick sort

    c) Heap sort

    d) Selection sort

    View Answer / Hide Answer

    ANSWER: A
    3. Which of the following is not an in-place sorting algorithm?

    a) Selection sort

    b) Heap sort

    c) Quick sort

    d) Merge sort

    View Answer / Hide Answer

    ANSWER: D

    4. Running merge sort on an array of size n which is already sorted is

    a) O(n)

    b) O(nlogn)

    c) O(n2)

    d) None

    View Answer / Hide Answer


    ANSWER: B

    5. The time complexity of a quick sort algorithm which makes use of median, found by an O(n)
    algorithm, as pivot element is

    a) O(n2)

    b) O(nlogn)

    c) O(nloglogn)

    d) O(n)

    View Answer / Hide Answer

    ANSWER: B

    6. Which of the following is not a noncomparison sort?

    a) Counting sort

    b) Bucket sort

    c) Radix sort

    d) Shell sort

    View Answer / Hide Answer


    ANSWER: D

    7. The time complexity of heap sort in worst case is

    a) O(logn)

    b) O(n)

    c) O(nlogn)

    d) O(n2)

    View Answer / Hide Answer

    ANSWER: C

    8. If the given input array is sorted or nearly sorted, which of the following algorithm gives the best
    performance?

    a) Insertion sort

    b) Selection sort

    c) Quick sort

    d) Merge sort
    View Answer / Hide Answer

    ANSWER: A

    9. Which of the following algorithm pays the least attention to the ordering of the elements in the input
    list?

    a) Insertion sort

    b) Selection sort

    c) Quick sort

    d) None

    View Answer / Hide Answer

    ANSWER: B

    10. Consider the situation in which assignment operation is very costly. Which of the following sorting
    algorithm should be performed so that the number of assignment operations is minimized in general?

    a) Insertion sort

    b) Selection sort
    c) Heap sort

    d) None

    View Answer / Hide Answer

    ANSWER: B

    11. Time complexity of bubble sort in best case is

    a) θ (n)

    b) θ (nlogn)

    c) θ (n2)

    d) θ (n(logn) 2)

    View Answer / Hide Answer

    ANSWER: A

    12. Given a number of elements in the range [0….n3]. which of the following sorting algorithms can sort
    them in O(n) time?

    a) Counting sort
    b) Bucket sort

    c) Radix sort

    d) Quick sort

    View Answer / Hide Answer

    ANSWER: C

    13. Which of the following algorithms has lowest worst case time complexity?

    a) Insertion sort

    b) Selection sort

    c) Quick sort

    d) Heap sort

    View Answer / Hide Answer

    ANSWER: D

    14. Which of the following sorting algorithms is/are stable


    a) Counting sort

    b) Bucket sort

    c) Radix sort

    d) All of the above

    View Answer / Hide Answer

    ANSWER: D

    15. Counting sort performs …………. Numbers of comparisons between input elements.

    a) 0

    b) n

    c) nlogn

    d) n2

    View Answer / Hide Answer

    ANSWER: A

    16. The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base 10
    representation is
    a) θ (n)

    b) θ (nlogn)

    c) θ (n2)

    d) none

    View Answer / Hide Answer

    ANSWER: B

    17. The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base n
    representation is

    a) θ (n)

    b) θ (nlogn)

    c) θ (n2)

    d) None

    View Answer / Hide Answer

    ANSWER: A
    18. Which of the following sorting algorithm is in-place

    a) Counting sort

    b) Radix sort

    c) Bucket sort

    d) None

    View Answer / Hide Answer

    ANSWER: B

    19. The radix sort does not work correctly if each individual digit is sorted using

    a) Insertion sort

    b) Counting sort

    c) Selection sort

    d) Bubble sort

    View Answer / Hide Answer

    ANSWER: C
    20. Which of the following sorting algorithm has the running time that is least dependant on the initial
    ordering of the input?

    a) Insertion sort

    b) Quick sort

    c) Merge sort

    d) Selection sort

    View Answer / Hide Answer

    ANSWER: D

    21. Time complexity to sort elements of binary search tree is

    a) O(n)

    b) O(nlogn)

    c) O(n2)

    d) O(n2logn)

    View Answer / Hide Answer

    ANSWER: A
    22. The lower bound on the number of comparisons performed by comparison-based sorting algorithm
    is

    a) Ω (1)

    b) Ω (n)

    c) Ω (nlogn)

    d) Ω (n2)

    View Answer / Hide Answer

    ANSWER: C

    23. Which of the following algorithm(s) can be used to sort n integers in range [1…..n3] in O(n) time?

    a) Heap sort

    b) Quick sort

    c) Merge sort

    d) Radix sort

    View Answer / Hide Answer

    ANSWER: D
    24. Which of the following algorithm design technique is used in the quick sort algorithm?

    a) Dynamic programming

    b) Backtracking

    c) Divide-and-conquer

    d) Greedy method

    View Answer / Hide Answer

    ANSWER: C

    25. Merge sort uses

    a) Divide-and-conquer

    b) Backtracking

    c) Heuristic approach

    d) Greedy approach

    View Answer / Hide Answer

    ANSWER: A
    26. For merging two sorted lists of size m and n into sorted list of size m+n, we require comparisons of

    a) O(m)

    b) O(n)

    c) O(m+n)

    d) O(logm + logn)

    View Answer / Hide Answer

    ANSWER: C

    27. A sorting technique is called stable if it

    a) Takes O(nlogn) times

    b) Maintains the relative order of occurrence of non-distinct elements

    c) Uses divide-and-conquer paradigm

    d) Takes O(n) space

    View Answer / Hide Answer


    ANSWER: B

    28. In a heap with n elements with the smallest element at the root, the seventh smallest element can
    be found in time

    a) θ (nlogn)

    b) θ (n)

    c) θ (logn)

    d) θ (1)

    View Answer / Hide Answer

    ANSWER: A

    29. What would be the worst case time complexity of the insertion sort algorithm, if the inputs are
    restricted to permutation of 1…..n with at most n inversion?

    a) θ (n2)

    b) θ (nlogn)

    c) θ (n1.5)

    d) θ (n)
    View Answer / Hide Answer

    ANSWER: D

    30. In a binary max heap containing n numbers, the smallest element can be found in time

    a) θ (n)

    b) θ (logn)

    c) θ (loglogn)

    d) θ (1)

    View Answer / Hide Answer

    ANSWER: A

    You might also like