uiz Space

May 2026 term · Programming, Data Structures and Algorithms using Python · BSCS2002

Programming, Data Structures and Algorithms using Python Quiz 2: 16 August 2026 (May 2026 term)

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: 16 questions for 50 marks in 120 minutes. Every question is below with its answer. Take it as a timed mock test to be marked, or read it through first.

Questions
16
Marks
50
Duration
120 min
MSQ
2
MCQ
11
Written
3
Take as mock testPractise with answers

Updated

Official paper: Programming, Data Indian Institute Of Technology, Madras - Bs In Data Science And Applications Structures And Algorithms Using Python 14 Aug 26 · No negative marking.

Question 1

+3 marksOne or more correct options

Which of the following statements is true about Dijkstra's algorithm to find the shortest path?

Select all that apply.

  1. A

    Dijkstra’s algorithm may fail for graphs with negative weights because it does not reconsider a node once it marks it as visited, even if there is a shorter path than the previous one.

  2. B

    The shortest path between two vertices and in a graph always remains unaltered when all the edges of are incremented by an equal amount.

  3. C

    The shortest path between two vertices and in a graph always remains unaltered when all the edges of are multiplied by a positive integer.

  4. D

    To decide which node to visit next, Dijkstra's algorithm selects the unvisited node with the smallest known distance.

Show answer

Correct answers

  • A

    Dijkstra’s algorithm may fail for graphs with negative weights because it does not reconsider a node once it marks it as visited, even if there is a shorter path than the previous one.

  • C

    The shortest path between two vertices and in a graph always remains unaltered when all the edges of are multiplied by a positive integer.

  • D

    To decide which node to visit next, Dijkstra's algorithm selects the unvisited node with the smallest known distance.

Question 1 on its own page

Question 2

+3 marksOne correct option

Let G = (V, E) be an undirected graph having distinct positive edge weights. Let V be partitioned into two non-empty sets X and Y. Let e = (s, t) be the minimum cost edge, with s belonging to X and t belonging to Y. Which of the following statement(s) is/are true? 1. The edge e must belong to each path from s to t. 2. The edge e must belong to the minimum cost spanning tree of G.

  1. A

    Only 1

  2. B

    Only 2

  3. C

    Both 1 and 2

  4. D

    Neither 1 nor 2

Show answer

Correct answer

  • B

    Only 2

Question 2 on its own pageAlso asked in Quiz 2 3 Dec 2023

Question 3

+3 marksOne correct option

Which of the following statements about the Floyd-Warshall algorithm is correct?

  1. A

    It can compute shortest paths only in graphs with non-negative edge weights.

  2. B

    It computes shortest paths from a single source vertex to all other vertices.

  3. C

    It computes shortest paths between every pair of vertices and can handle negative edge weights, provided there is no negative cycle.

  4. D

    It requires the graph to be acyclic.

Show answer

Correct answer

  • C

    It computes shortest paths between every pair of vertices and can handle negative edge weights, provided there is no negative cycle.

Question 3 on its own page

Question 4

+3 marksOne correct option

Consider a min-heap represented as the following list: What are the leaf nodes of the resultant min-heap after the following operations are done on it? 1. delete_min() 2. insert(6)

  1. A

    18, 15, 19, 20, 25

  2. B

    7, 18, 19, 20, 25

  3. C

    6, 18, 19, 20, 25

  4. D

    15, 18, 19, 7, 25

Show answer

Correct answer

  • A

    18, 15, 19, 20, 25

Question 4 on its own page

Question 5

+3 marksOne correct option

A standard max-heap contains elements. What is the worst-case time complexity of the most efficient algorithm for finding the minimum element in a standard max-heap?

  1. A

    —

  2. B

    —

  3. C

    —

  4. D

    —

Show answer

Correct answer

  • C

    —

Question 5 on its own page

Question 6

+3 marksOne correct option

A Binary Search Tree (BST) is initially empty. The following keys are inserted in the given order: Assume that the tree is a standard BST and no balancing operations are performed after insertion. How many comparisons are required to search for the key 60 in the resulting BST?

  1. A

    2

  2. B

    3

  3. C

    4

  4. D

    5

Show answer

Correct answer

  • B

    3

Question 6 on its own page

Question 7

+3 marksOne correct option

We have n distinct values stored in a height-balanced (AVL) binary search tree. Which of the following statements is always true?

  1. A

    The value at each node is the median of the values in the subtree rooted at that node.

  2. B

    The shortest path between any pair of nodes is at most .

  3. C

    For any node, the difference between the size of the left subtree and the size of the right subtree is at most 3.

  4. D

    The number of leaf nodes is greater than or equal to the number of internal nodes.

Show answer

Correct answer

  • B

    The shortest path between any pair of nodes is at most .

Question 7 on its own page

Question 8

+3 marksOne correct option

You are verifying a set of binary codes generated for a text file containing four unique characters: . Which of the following code allocations is invalid because it violates the fundamental prefix property required by Huffman coding?

  1. A

    —

  2. B

    —

  3. C

    —

  4. D

    —

Show answer

Correct answer

  • A

    —

Question 8 on its own page

Question 9

+3 marksOne correct option

Consider the following activities represented as (Start Time, Finish Time):

Two activities are considered compatible if the start time of one activity is greater than or equal to the finish time of the previously selected activity. A greedy algorithm is used to select the maximum number of non-overlapping activities. How many activities will be selected?

Consider the following activities represented as (Start Time, Finish Time):
  1. A

    3

  2. B

    4

  3. C

    5

  4. D

    6

Show answer

Correct answer

  • B

    4

Question 9 on its own page

Question 10

+3 marksOne correct option

A text file contains 1000 characters. Originally, each character is represented using a fixed-length code of bits. After applying Huffman coding, the average code length becomes bits per character. What percentage reduction in storage is achieved?

  1. A

    20

  2. B

    25

  3. C

    30

  4. D

    33.33

Show answer

Correct answer

  • B

    25

Question 10 on its own page

Question 11

+3 marksOne correct option

In the Divide-and-Conquer Closest Pair of points algorithm, why is brute force typically used when the number of points in a subproblem is at most 3?

  1. A

    Brute force is asymptotically faster than divide-and-conquer

  2. B

    Dynamic programming cannot be applied

  3. C

    The closest pair is always known in advance

  4. D

    The overhead of further recursive division outweighs its benefit for very small inputs

Show answer

Correct answer

  • D

    The overhead of further recursive division outweighs its benefit for very small inputs

Question 11 on its own page

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.

Question 12 on its own page

Question 13

+4 marksWritten answer

Consider the undirected, weighted graph with vertices and the following edge weights: • • • • • Let denote the total number of distinct Minimum Spanning Trees (MSTs) of , and let denote the total weight of any such Minimum Spanning Tree. What is the value of ?

Show answer

A written answer, not marked automatically.

Question 13 on its own page

Question 14

+3 marksWritten answer

Assume the following definition of height: • Height of an empty tree = 0. • Height of a tree with only a root node = 1. What is the height of a complete binary tree that contains nodes?

Show answer

A written answer, not marked automatically.

Question 14 on its own page

Question 15

+3 marksWritten answer

In a list L of distinct elements, two elements and form an inversion if and . Suppose L contains exactly 15 inversions. The minimum possible length of L is ___.

Show answer

A written answer, not marked automatically.

Question 15 on its own page

Question 16

+4 marksOne or more correct options

Consider the following recurrence relations: 1. 2. 3. 4. Base Case: Which of the above recurrences have asymptotic complexity ?

Select all that apply.

  1. A

    —

  2. B

    —

  3. C

    —

  4. D

    —

Show answer

Correct answers

  • A

    —

  • C

    —

  • D

    —

Question 16 on its own page