The IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) Quiz 2 paper sat on 24 Mar 2024, in the January 2024 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.
In the context of the Floyd-Warshall algorithm, what does it mean if the distance matrix has a negative value in its diagonal?
The graph has a negative-weight cycle.
The graph has negative-weight on edge but no negative-weight cycle.
The graph is acyclic.
The graph has a disconnected component.
Correct answer
The graph has a negative-weight cycle.
P, Q, R, U, T, S
P, Q, R, S, T, U
P, Q, R, S, U, T
P, Q, R, U, S, T
Correct answer
P, Q, R, U, S, T
You have a max-heap with the following set of elements:
{10, 5, 15, 3, 8, 12}
Which of the following elements is guaranteed to be a child of the element 15?
10
5
12
8
Correct answer
12
Consider the following sequence of numbers inserted into an empty Binary Search Tree(BST): 50, 30, 20, 40, 70, 60, 80, 35
What will be the height of the resulting BST? Consider that the height of empty binary search tree is 0.
3
4
5
6
Correct answer
4
Which of the following traversals would visit the nodes of a binary search tree in the following order?
10, 5, 3, 8, 15, 12, 20
In-order traversal
Pre-order traversal
Post-order traversal
Correct answer
Pre-order traversal
Apply the divide and conquer strategy to find the closest pair of points in a set. After dividing the set into two halves and recursively finding the closest pairs in each half, what additional step is required?
Combine the results directly
Perform a linear search for the closest pair
Consider pairs that span both halves
Sort the points by their distances
Correct answer
Consider pairs that span both halves
Correct answer
a, e, b, c, d, g, h, f
a, e, b, c, g, h, d, f
a, e, b, d, c, h, g, f
a, e, b, d, c, g, f, h
Correct answer
a, e, b, c, d, g, h, f
For a set of symbols with probabilities of occurrence, which of the following statement(s) about the Huffman tree is/are correct?
Symbols with higher probabilities are generally closer to the root of the tree
Symbols with lower probabilities are generally closer to the root of the tree
The Huffman tree is always a complete binary tree
It generates prefix codes (no code is a prefix of another).
Correct answers
Symbols with higher probabilities are generally closer to the root of the tree
It generates prefix codes (no code is a prefix of another).
Define the slope of a node as the absolute difference in height between the left subtree and the right subtree of the node. Consider that the height of the empty tree is 0.
Consider the below AVL Tree.
After inserting 19 in the given AVL tree (before applying rotation), which of the following node's slopes will become greater than 1? Select all that are correct.
38
56
14
18
23
Correct answers
14
23
Consider the following statements and choose the correct ones.
Correct answers
If all given weights are distinct, then only one unique MST is possible.
If w1 and w2 are the same and largest among all weights and other weights are distinct, then only one unique MST is possible.
If w1 and w3 are the same and largest among all weights and other weights are distinct, then only one unique MST is possible.
If w1 and w4 are the same and smallest among all weights and other weights are distinct, then only one unique MST is possible.
Correct answers
If all given weights are distinct, then only one unique MST is possible.
If w1 and w3 are the same and largest among all weights and other weights are distinct, then only one unique MST is possible.
If w1 and w4 are the same and smallest among all weights and other weights are distinct, then only one unique MST is possible.
Consider a binary tree with 21 nodes. The maximum number of leaves possible in tree is ___________.
Correct answer: 11
Correct answer: 16
Correct answer: 5
Correct answer: 4
