Design & Analysis of Algorithm logo

DAA Unit 2 Part 2 MCQs

PREV
NEXT
Menu
Unit 2

Sorting:- Type of Sorting, Bubble Sort, Selection Sort, Insertion Sort, Binary Insertion Sort, Shell Sort, Quick Sort, Merge Sort, Heap, Heap Sort. Sorting in Linear Time:- Counting Sort, Radix Sort, Bucket Sort.

Q21 – When sorting method depends on comparison of two elements to decide relative elements then that is known as ___________.
  1. In-place Sort
  2. Stable Sort
  3. Comparison Sort
  4. External Sort

Ans – (3)

Q22 – In sorting if there is no extra space required to solve a given array then that is known as __________.
  1. In-place Sort
  2. Stable Sort
  3. Comparison Sort
  4. External Sort

Ans – (1)

Q23 – If two elements are equal Ai = Aj. After sorting Ai and Aj are placed at u and v position respectively, where u < v, then that sort is known as _________.
  1. External Sorting
  2. Efficiency Sorting
  3. In-place Sorting
  4. Stable Sorting

Ans – (4)

Q24 – If time and space complexity is minimum then this is called __________.
  1. External Sorting
  2. Efficiency Sorting
  3. Data Sensitive Sorting
  4. Stable Sorting

Ans – (2)

Q25 – When sorting method is applied only on main memory or when set of elements can be stored completely in main memory then that sort known as __________.
  1. Internal Sort
  2. Stable Sort
  3. In-place Sort
  4. External Sort

Ans – (1)

Q26 – When sorting method is applied on main memory as well as secondary memory then that sort known as __________.
  1. Internal Sort
  2. Stable Sort
  3. In-place Sort
  4. External Sort

Ans – (4)

Q27 – If time complexity of any sorting method is not similar in best case and worst case then that sort is known as __________.
  1. External Sorting
  2. Efficiency Sorting
  3. Data Sensitive Sorting
  4. Stable Sorting

Ans – (3)

Q28 – Selection sort worst case time complexity is
  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n2)

Ans – (4)

Q29 – A sorting algorithm works by inserting elements from an unsorted array into a sorted subsection of the array, one item in the iteration.
  1. Bubble Sort
  2. Insertion Sort
  3. Selection Sort
  4. Counting Sort

Ans – (3)

Explanation –

Selection sort search minimum element per iteration and insert it into sorted subsection array.

 

Q30 – Imagine you are playing a card game. There are 10 cards in the floor with face down and you have to pick one card at a time and sort it into another hand. What type of sorting is this
  1. Bubble Sort
  2. Insertion Sort
  3. Selection Sort
  4. Counting Sort

Ans – (2)

Explanation – 

https://compgeek.co.in/insertion-sort/ to know more.

Q31 – A sorting works by splitting the input in half, recursively sorting each half, and then merging the sorted halves back together.
  1. Quick Sort
  2. Selection Sort
  3. Merge Sort
  4. Heap Sort

Ans – (3)

Explanation – Merge sort uses divide and conquer approach. Input splits in half till individual element is not there. 

Q32 – A sorting algorithm works by recursively dividing the input into two smaller arrays around a pivot item: one half has items smaller than the pivot, the other has larger items.
  1. Quick Sort
  2. Selection Sort
  3. Merge Sort
  4. Heap Sort

Ans – (1)

Q33 – Quick sort’s ______ case complexity of _________ is observed when the input to be sorted is in decreasing order or increasing order (if the first element is the pivot element).
  1. Worst, O(nlogn)
  2. Average, O(n2)
  3. Average, O(nlogn)
  4. Worst, O(n2)

Ans – (4)

Explanation – Quick sort has worst case running time of O(n2). 

Q34 – _______ sort is a generalization of insertion sort that overcomes insertion sort’s drawbacks by comparing elements separated by several positions.
  1. Bubble Sort
  2. Shell Sort
  3. Bucket Sort
  4. Selection Sort

Ans – (2)

Explanation – https://compgeek.co.in/shell-sort/ to know more.

Q35 – Shell sort best case time complexity is
  1. O(nlogn)
  2. θ(n log(n)^2)
  3. O(n log(n)^2)
  4. O(n log(n))

Ans – (1)

Q36 – Shell sort average case time complexity is
  1. O(nlogn)
  2. θ(n log(n)^2)
  3. O(n log(n)^2)
  4. O(n2)

Ans – (3)

Q37 – Shell sort worst case time complexity is
  1. O(nlogn)
  2. θ(n log(n)^2)
  3. O(n log(n)^2)
  4. O(n2)

Ans – (4)

Q38 – Some algorithms, such as _____, ______ and _______ run faster and take linear time, but they require a special assumption about the input sequence to sort.
  1. Counting Sort, Radix Sort, and Bucket Sort
  2. Counting Sort, Radix Sort, and Bubble Sort
  3. Counting Sort, Heap Sort, and Bucket Sort
  4. Shell Sort, Radix Sort, and Bucket Sort

Ans – (1)

Q39 – What sorting algorithm here is used

Radix Sort

  1. Counting sort
  2. Radix sort
  3. Selection sort
  4. Bubble sort

Ans – (2)

Explanation – Pass 1: Sort the list according to the digits at 0’s place.

Pass 2: Sort the list according to the digits at 10’s place.

Pass 3: Sort the list according to the digits at 100’s place.

Pass 4: Sort the list according to the digits at 1000’s place.

Q40 – Radix sort worst case time complexity is (k is the range of input)
  1. Ω(nk)
  2. Θ(nk)
  3. O(nk)
  4. O(n+k)

Ans – (3)

Explanation – If k is equal to n, then it will give rise to O(n2). But in the terms of n we always write O(nk) and said to be linear sorting.

PREV
NEXT

BOOKS

Algorithm T H CoremanAlgorithm by Udit AgarwalAlgorithm Ellis HorowitzData Structure & Algorithm Made Easy Narasimha

 

GATE Study Material
Previous Year Paper
Subjective Questions