Figure from the original question paper Consider a max-heap of size\ consisting of distinct elements and implemented using an array. Figure from the original question paper Which of the following operations can be performed in\ time?

(B) Deleting the maximum element

(D) Update the value at the known index

(C) Option figure from the original question paper Merging with another max-heap of size

The height of a binary search tree is defined as the number of nodes in the longest path from the Figure from the passage in the original paper Figure from the passage in the original paper Figure from the passage in the original paper root to the leaf (both included). Consider a binary search tree\ of height\ . Note that need not be balanced.\ Based on the above data, answer the given subquestions. Figure from the original question paper What is the worst-case running time complexity of the searching operation in\ ?

(B) Option figure from the original question paper

(A) Option figure from the original question paper

(C) Option figure from the original question paper

(D) Option figure from the original question paper

Consider the following recurrences and choose the correct option. Figure from the original question paper 1. Figure from the original question paper 2. Figure from the original question paper Base Case:

(C) Option figure from the original question paper Option figure from the original question paper and

(A) Option figure from the original question paper Option figure from the original question paper and

(B) Option figure from the original question paper Option figure from the original question paper and

(D) Option figure from the original question paper Option figure from the original question paper and

September 2025 term · Programming, Data Structures and Algorithms using Python · BSCS2002

Programming, Data Structures and Algorithms using Python Quiz 2: 23 November 2025 (September 2025 term)

The IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) Quiz 2 paper sat on 23 Nov 2025, in the September 2025 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
MCQ: 9
Numerical: 4
MSQ: 3

Take as mock test Practise with answers

Updated 25 Sept 2026

Official paper: IIT M DIPLOMA AN EXAM QDD2 23 Nov 2025 NEW · No negative marking.

Question 1

+3 marksOne correct option

In the given graph, if we try to find the shortest path from node P to all other nodes using

Dijkstra’s algorithm, which node is the
node to be included in the visited set? Consider that P is the 1st visited node.

Show answer

Correct answer

Question 1 on its own page

Question 2

+3 marksOne correct option

Consider the following algorithm to solve the single source shortest path problem for a graph (directed or undirected) with positive integer edge weights and a source vertex s.Replace each edge (u,v) of weight w in the graph with a path of length w consisting of unit-weight edges from u to v (by introducing new intermediate vertices).
For example: edge (u, v) with weight w = 3

Run BFS on this modified graph from the source s to find the shortest path to each of the original vertices in the graph.
Which of the following statements is/are true?
I. The algorithm solves the single source shortest path problem correctly.
II. Although the size of the modified graph is larger than the original graph, the algorithm is as efficient as Dijkstra’s algorithm.

A
I is True but II is False
B
I is False but II is True
C
Both I and II are False
D
Both I and II are True

Show answer

Correct answer

A
I is True but II is False

Question 2 on its own page

Question 3

+3 marksNumerical answer

What is the weight of a minimum spanning tree in the graph given below?

Show answer

Correct answer: 10

Question 3 on its own page

Question 4

+3 marksOne correct option

Let
be a connected undirected graph with distinct positive edge weights.Consider

a partition (cut) of the vertex set
into two non-empty subsets
and
such that:

•
, and

•

Let
be the minimum-weight edge among all edges that cross this cut, i.e., and

.
Which of the following statements is/are true?

I. For every pair of nodes
such that
and
, the edge
must lie on the shortest

path from
to
.

II. The edge
must be part of the minimum spanning tree (MST) of
.

A
I is True but II is False
B
I is False but II is True
C
Both I and II are False
D
Both I and II are True

Show answer

Correct answer

B
I is False but II is True

Question 4 on its own page

Question 5

+3 marksOne or more correct options

Consider a max-heap of size
consisting of distinct elements and implemented using an array.

Which of the following operations can be performed in
time?

Select all that apply.

A
Inserting a new element
B
Deleting the maximum element
C
Merging with another max-heap of size
D
Update the value at the known index

Show answer

Correct answers

A
Inserting a new element
B
Deleting the maximum element
D
Update the value at the known index

Question 5 on its own page

Question 6

+3 marksOne or more correct options

Consider a max-heap of size
consisting of distinct elements and implemented using an array.Which of the following statements is/are true about the max-heap?

Select all that apply.

A
The smallest element in the max-heap is always at a leaf node.
B
The smallest element in the max-heap is always located at one of the leaf nodes in the last level of the heap.
C
The second largest element in the max-heap must be located in the level immediately below the root (i.e., among the root’s children).
D
Finding the smallest element in the max-heap takes O(log n) time.

Show answer

Correct answers

A
The smallest element in the max-heap is always at a leaf node.
C
The second largest element in the max-heap must be located in the level immediately below the root (i.e., among the root’s children).

Question 6 on its own page

Question 7

+3 marksOne correct option

The height of a binary search tree is defined as the number of nodes in the longest path from the

root to the leaf (both included). Consider a binary search tree
of height
. Note that need not be balanced.
Based on the above data, answer the given subquestions.

What is the worst-case running time complexity of the searching operation in
?

Show answer

Correct answer

Question 7 on its own page

Question 8

+3 marksOne or more correct options

The height of a binary search tree is defined as the number of nodes in the longest path from the

root to the leaf (both included). Consider a binary search tree
of height
. Note that need not be balanced.
Based on the above data, answer the given subquestions.

Suppose the number of elements in
is
. Which of the following statement(s) is/are correct?

Select all that apply.

Show answer

Correct answers

Question 8 on its own page

Question 9

+3 marksNumerical answer

What is the minimum number of nodes possible in an AVL tree of height 6 ? Consider the tree with a single node having height 1.

Show answer

Correct answer: 20

Question 9 on its own page

Question 10

+4 marksOne correct option

After inserting the following elements into an empty AVL Tree:
30, 20, 10, 28, 25, 40
Which of the following nodes will be the root in the final AVL Tree?

A
25
B
20
C
30
D
28

Show answer

Correct answer

D
28

Question 10 on its own page

Question 11

+4 marksNumerical answer

Given below is a set of characters and their frequencies:

Using Huffman encoding, construct the Huffman tree for this set of characters. What is the maximum number of bits needed to encode any character?

Show answer

Correct answer: 3

Question 11 on its own page

Question 12

+3 marksOne correct option

Consider a problem scenario where you have to conduct
job interviews
. Each candidate is available only between start_time and end_time. If any interview finishes at time T, then the other interviews can be started at time T or afterwards.
Which of the following greedy strategies would you apply to schedule the interviews such that the maximum number of candidates can be interviewed without any conflicts?

A
Always choose the candidate whose start_time is at the earliest.
B
Always choose the candidate who is available for the shortest time.
C
Always choose the candidate whose availability overlaps with the minimum number of other candidates.
D
Always choose the candidate whose end_time is the earliest.

Show answer

Correct answer

D
Always choose the candidate whose end_time is the earliest.

Question 12 on its own page

Question 13

+3 marksNumerical answer

In an integer list L of length n, two elements L[i] and L[j] form an inversion if L[i] > L[j] and i < j.

Consider a list L of length n in which all elements are distinct and the list L has
inversions. The minimum possible value of n is ___.

Show answer

Correct answer: 9

Question 13 on its own page

Question 14

+3 marksOne correct option

Which of the following statements is incorrect?

A
The worst case running time of Quick select algorithm to find the k^(th) largest number is O(n).
B
The time taken to find the median in an unsorted list using the Median of Medians (MoM) algorithm is O(n).
C
Quick select algorithm is an example of the divide-and-conquer approach to solving problems.
D
Using Fast Select (Quick Select using MoM for pivot selection) strategy, the worst-case running time will be O(n).

Show answer

Correct answer

A
The worst case running time of Quick select algorithm to find the k^(th) largest number is O(n).

Question 14 on its own page

Question 15

+3 marksOne correct option

Consider the following recursive function to return the minimum element in the list L of size n. def find_min(L, low, high):
if low == high:
return L[low]
mid = (low + high) // 2
min1 = find_min(L, low, mid)
min2 = find_min(L, mid+1, high)
return min(min1, min2)
Which of the following represents the correct recurrence relation for the given function find_min?

Show answer

Correct answer

Question 15 on its own page

Question 16

+3 marksOne correct option

Consider the following recurrences and choose the correct option.

Base Case:

A
and
B
and
C
and
D
and

Show answer

Correct answer

C
and

Question 16 on its own page