Quiz Space

Programming, Data Structures and Algorithms using Python · Quiz 2 · 16 Aug 2026 · May 2026 term

Question 12: Which of the following approaches can improve the worst-…

Question 12

+3 marksOne correct option

Which of the following approaches can improve the worst-case running time of Quick Select to O(n)?

  1. A

    Selecting the median of a random sample of k elements (for a fixed constant k) as the pivot.

  2. B

    Selecting a uniformly random element as the pivot.

  3. C

    Selecting the median element after sorting the entire current subarray before partitioning.

  4. D

    Selecting the pivot using the Median-of-Medians algorithm.

Show answer

Correct answer

  • D

    Selecting the pivot using the Median-of-Medians algorithm.

See the whole paperTake it as a mock test

Question 12 of 16 in the IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) Quiz 2 paper sat on 16 Aug 2026, in the May 2026 term (Programming, Data Indian Institute Of Technology, Madras - Bs In Data Science And Applications Structures And Algorithms Using Python 14 Aug 26). It carries 3 marks.

More questions from this paper

  1. Q1Which of the following statements is true about Dijkstra's algorithm to find the shortest path?
  2. Q2Let G = (V, E) be an undirected graph having distinct positive edge weights. Let V be partitioned into two non-empty se…
  3. Q3Which of the following statements about the Floyd-Warshall algorithm is correct?
  4. Q4Consider a min-heap represented as the following list: What are the leaf nodes of the resultant min-heap after the foll…
  5. Q5A standard max-heap contains elements. What is the worst-case time complexity of the most efficient algorithm for findi…
  6. Q6A Binary Search Tree (BST) is initially empty. The following keys are inserted in the given order: Assume that the tree…
  7. Q7We have n distinct values stored in a height-balanced (AVL) binary search tree. Which of the following statements is al…
  8. Q8You are verifying a set of binary codes generated for a text file containing four unique characters: . Which of the fol…
  9. Q9Consider the following activities represented as (Start Time, Finish Time): Two activities are considered compatible if…
  10. Q10A text file contains 1000 characters. Originally, each character is represented using a fixed-length code of bits. Afte…
  11. Q11In the Divide-and-Conquer Closest Pair of points algorithm, why is brute force typically used when the number of points…
  12. Q13Consider the undirected, weighted graph with vertices and the following edge weights: • • • • • Let denote the total nu…
  13. Q14Assume the following definition of height: • Height of an empty tree = 0. • Height of a tree with only a root node = 1.…
  14. Q15In a list L of distinct elements, two elements and form an inversion if and . Suppose L contains exactly 15 inversions.…
  15. Q16Consider the following recurrence relations: 1. 2. 3. 4. Base Case: Which of the above recurrences have asymptotic comp…