Question 1
Here is a function to return the count of odd numbers in the list. There is a logical error in this function.
Select the input list for which bad_count_odd produces incorrect output.
[5,31,71,41]
[15,7,3,6,8,34]
[11,3,15,31]
[5,4,13,30]
Programming, Data Structures and Algorithms using Python End Term: 21 December 2025 (September 2025 term)
The IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) End Term paper sat on 21 Dec 2025, in the September 2025 term: 50 questions for 200 marks in 180 minutes. Every question is below with its answer. Take it as a timed mock test to be marked, or read it through first.
- 50
- 200
- 180 min
- 32
- 4
- 14
Show answer
Correct answer
[5,4,13,30]
Question 2
Here is a function to return the count of even numbers in the list. There is a logical error in this function.
Select the input list for which bad_count_even produces incorrect output.
[56,4,70,40]
[6,8,34,13,5,9]
[6,11,4,30]
[6,4,2,30]
Show answer
Correct answer
[6,11,4,30]
Question 3
Match the correct asymptotic complexity for each function.
1-b, 2-c, 3-a, 4-d, 5-e
1-a, 2-d, 3-b, 4-c, 5-e
1-e, 2-c, 3-b, 4-a, 5-d
1-a, 2-c, 3-b, 4-d, 5-e
Show answer
Correct answer
1-a, 2-c, 3-b, 4-d, 5-e
Question 4
Match the correct asymptotic complexity for each function.
1-b, 2-c, 3-d, 4-e, 5-a
1-a, 2-c, 3-d, 4-e, 5-b
1-b, 2-c, 3-e, 4-d, 5-a
1-a, 2-c, 3-e, 4-d, 5-b
Show answer
Correct answer
1-b, 2-c, 3-d, 4-e, 5-a
Question 5
Consider the below function for selection sort algorithm.
Assume that the list L=[25, 17, 20, 10, 15] is passed to the function selectionsort() as parameter. What will be the list L after the second pass of selection sort?
[10, 15, 20, 25, 17]
[10, 25, 20, 17, 15]
[10, 15, 25, 20, 17]
[25, 17, 20, 10, 15]
Show answer
Correct answer
[10, 15, 20, 25, 17]
Question 6
Consider the below function for selection sort algorithm.
Assume that the list L=[15, 12, 18, 13, 11] is passed to the function selectionsort() as parameter.
What will be the list L after the second pass of selection sort?
[11, 15, 18, 13, 12]
[15, 12, 18, 13, 11]
[11, 12, 18, 13, 15]
[11, 12, 13, 15, 18]
Show answer
Correct answer
[11, 12, 18, 13, 15]
Question 7
Which of the following scenarios is an example where linear search is more practical or efficient than the binary search?
The list has only 3–4 elements.
The list is unsorted and searching must be done immediately.
The element being searched is at the middle index of a large sorted list.
The list changes frequently, making it expensive to maintain sorted order.
The list is sorted and stored in an array with random access available.
Show answer
Correct answers
The list has only 3–4 elements.
The list is unsorted and searching must be done immediately.
The list changes frequently, making it expensive to maintain sorted order.
Question 8
Which of the following scenarios is an example where linear search is more practical or efficient than binary search?
Searching for an element in linked list.
Searching for an element in an unsorted list.
Searching for an element in a very large sorted list.
Searching element is at the first index position of the list.
The searching element is at the last index position of the list
Show answer
Correct answers
Searching for an element in linked list.
Searching for an element in an unsorted list.
Searching element is at the first index position of the list.
Question 9
Consider the following class Node:
Consider an implementation of a linked list where each node is created using the given class Node. Suppose head points to the first node of the linked list. Assume that the linked list is in sorted order.
What is an efficient way to count duplicate values in the linked list?
Traverse the linked list once, comparing each node with its immediate successor and count duplicates.
Traverse the linked list once and store each node’s value in a hash table to count duplicates.
Use a nested loop to compare each node with all other nodes and count duplicates.
Recursively traverse the linked list from the tail and count duplicates.
Show answer
Correct answer
Traverse the linked list once, comparing each node with its immediate successor and count duplicates.
Question 10
Suppose we are sorting a list of eight integers using quicksort, and we have just finished the first partitioning. The list looks like this: [12, 18, 25, 7, 30, 55, 60, 40]
Suppose the first element in the list is selected as the pivot for partitioning each time. Which of the following could have been the pivot for the first partitioning?
25
30
7
40
Show answer
Correct answer
30
Question 11
If you have an empty stack and you perform the following sequence of operations:
What is the value of the top element on the stack?
Show answer
Correct answer: 70
Question 12
Consider the following class Node:
Consider an implementation of a linked list where each node is created using the given class Node. Suppose head points to the first node of the linked list. Assume that the linked list is in sorted order.
What is an efficient way to remove all duplicate values in the linked list?
Recursively remove duplicates from the tail of the linked list.
Iterate through the linked list and use a nested loop to find duplicate values.
Traverse the linked list once, comparing each node with its immediate successor.
Traverse the linked list once and store non-duplicate elements in a new linked list.
Show answer
Correct answer
Traverse the linked list once, comparing each node with its immediate successor.
Question 13
A directed graph G has 7 vertices. What is the maximum number of edges in G?
Show answer
Correct answer: 42
Question 14
If you have an empty stack and you perform the following sequence of operations:
What is the value of the top element on the stack?
Show answer
Correct answer: 150
Question 15
Consider the following DAG.
How many valid topological sorts exist?
Show answer
Correct answer: 6
Question 16
There are 8 systems (0,..,7) connected in network as shown in the figure given below.
Which edge should we add to the network so that the network stays connected when one of the systems is down?
(4,7)
(5,7)
(0,3)
(0,7)
Show answer
Correct answer
(0,7)
Question 17
There are 7 systems (0,..,6) connected in a network as shown in the figure given below.
Which of the following system (node) failures will result in the network being disconnected?
0
2
4
3
Show answer
Correct answer
4
Question 18
Consider the following DAG.
How many valid topological sorts exist?
Show answer
Correct answer: 2
Question 19
Consider a directed graph given below:
Vertices: {0,1,2,3}
Edge weights: (0, 1) = 1 (0, 2) = 4 (1, 2) = 2 (1, 3) = 6 (2, 3) = 3
What is the shortest distance from node 0 to node 3 ?
9
8
7
6
Show answer
Correct answer
6
Question 20
Show answer
Correct answer
Question 21
In the Floyd–Warshall algorithm, which of the following are true?
It uses dynamic programming.
It can detect negative cycles.
It maintains a predecessor matrix for path reconstruction (when implemented with one).
It cannot be applied to undirected graphs.
Show answer
Correct answers
It uses dynamic programming.
It can detect negative cycles.
It maintains a predecessor matrix for path reconstruction (when implemented with one).
Question 22
Consider the following graph.
What is the shortest distance from node 0 to node 5?
7
8
9
11
Show answer
Correct answer
7
Question 23
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 2, 5, 7, 9, 12, 14. The maximum possible total weight that a minimum weight spanning tree of G can have is __.
Show answer
Correct answer: 16
Question 24
Suppose we run the Bellman-Ford algorithm on a graph with non-negative edges. Then compared to Dijkstra's algorithm, the Bellman-Ford algorithm will ___?
Run faster
Run slower
Produce wrong results
Detect the cycle
Show answer
Correct answer
Run slower
Question 25
Consider a binary tree with 21 nodes, where the number of nodes with two children is 9. The number of nodes with one child node is _____.
4
3
2
1
Show answer
Correct answer
2
Question 26
Some of the edges in G must have the same weight.
All edges in G must have the same weight.
Show answer
Correct answer
Some of the edges in G must have the same weight.
Question 27
Consider the following max-heap.
Which of the following cannot be the last element inserted into the heap?
77
10
31
17
36
Show answer
Correct answers
31
17
Question 28
Consider a binary tree with 15 nodes, where the number of nodes with two children is 6. The number of nodes with one child node is _______.
2
3
4
5
Show answer
Correct answer
2
Question 29
If we perform the following operations in the given order on the min-heap [12, 25, 18, 40, 35, 30, 28, 50, 45] then the resulting min-heap would be__.
[18, 20, 28, 40, 25, 30, 50, 45, 35]
[18, 25, 20, 40, 35, 30, 28, 50, 45]
[18, 20, 28, 25, 35, 30, 40, 50, 45]
[18, 25, 20, 35, 40, 28, 30, 50, 45]
Show answer
Correct answer
[18, 20, 28, 25, 35, 30, 40, 50, 45]
Question 30
If we perform the following operations in the given order on the max-heap [89, 62, 31, 45, 51, 29, 30, 42, 34] then the resulting max-heap would be__.
[78, 62, 51, 31, 34, 29, 30, 42, 45]
[78, 62, 31, 51, 34, 29, 30, 45, 42]
[78, 62, 31, 51, 34, 30, 29, 45, 42]
[78, 62, 31, 51, 34, 29, 30, 42, 45]
Show answer
Correct answer
[78, 62, 31, 51, 34, 29, 30, 42, 45]
Question 31
What is the maximum number of nodes in an AVL tree of height 9? Consider that the height of the empty tree is 0.
Show answer
Correct answer: 511
Question 32
What is the minimum number of nodes in an AVL tree of height 7? Consider that the height of the empty tree is 0.
Show answer
Correct answer: 33
Question 33
Show answer
Correct answer: 45
Question 34
Show answer
Correct answer: 132
Question 35
For which of the following coin denominations does the Greedy strategy of choosing the largest coin that does not exceed the target fail to produce the minimum number of coins to make the amount 8?
{1, 4, 6}
{1, 3, 4}
{1, 5, 7}
{1, 2, 6}
Show answer
Correct answer
{1, 4, 6}
Question 36
For which of the following coin denominations does the Greedy strategy of choosing the largest coin that does not exceed the target fail to produce the minimum number of coins to make the amount 6?
{1, 2, 5}
{1, 3, 4}
{1, 4, 5}
{1, 2, 3}
Show answer
Correct answer
{1, 3, 4}
Question 37
In a list L, two elements L[i] and L[j] form an inversion if L[i] > L[j] and i < j . The total number of inversions for L = [3, 4, 2, 1, 5] is___
5
4
3
2
Show answer
Correct answer
5
Question 38
In a list L, two elements L[i] and L[j] form a significant inversion if L[i] > 2 * L[j] and i < j . The total number of significant inversions for L = [5, 4, 1, 2, 3] is___.
5
4
3
2
Show answer
Correct answer
3
Question 39
Show answer
Correct answer
Question 40
Show answer
Correct answer
Question 41
Consider the following function MoM.
What median value will be returned by the given MoM function for the following list? [1, 3, 7, 4, 3, 2, 7, 9, 15, 12, 19, 25, 16, 17, 11, 17, 21, 28, 18, 30]
Show answer
Correct answer: 17
Question 42
Consider the following function MoM.
Show answer
Correct answer: 16
Question 43
Consider the function mystery() that takes strings X and Y as input. What will mystery('ABCDFGH','ACDFHBG') return? LCS(X,Y) returns the length of the longest common subsequence of X and Y.
10
9
8
7
Show answer
Correct answer
9
Question 44
Consider the function mystery() that takes strings X and Y as input. What will mystery('XYITCRT','WTXITRY') return? LCS(X,Y) returns the length of the longest common subsequence of X and Y.
10
9
8
7
Show answer
Correct answer
10
Question 45
Consider the following grid.
Show answer
Correct answer: 22
Question 46
Consider the following grid.
Show answer
Correct answer: 18
Question 47
Show answer
Correct answer
Question 48
Show answer
Correct answer
Question 49
16
15
14
13
Show answer
Correct answer
15
Question 50
9
10
11
12
Show answer
Correct answer
11