Quiz Space

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

PDSA Quiz 2: 10 July 2022 (May 2022 term)

The IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) Quiz 2 paper sat on 10 Jul 2022, in the May 2022 term: 15 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
15
Marks
50
Duration
120 min
MCQ
8
MSQ
4
Numerical
3
Take as mock testPractise with answers

Updated

Official paper: IIT M DIPLOMA QUIZ2 EXAM QPE1 10 July 2022 · No negative marking.

Question 1

+3 marksOne correct option
  1. A

    1

  2. B

    3

  3. C

    4

  4. D

    5

Show answer

Correct answer

  • C

    4

Question 1 on its own page

Question 2

+3 marksOne correct option
  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • B
Question 2 on its own page

Question 3

+3 marksOne correct option
  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • C
Question 3 on its own page

Question 4

+3 marksOne correct option

Which one of the following can not be a possible sequence of elements in the path from the root to any leaf in a binary search tree?

  1. A

    70, 60, 20, 50, 30, 46

  2. B

    50, 10, 36, 40, 31, 46

  3. C

    20, 75, 58, 30, 55, 46

  4. D

    60, 10, 40, 50, 42, 46

Show answer

Correct answer

  • B

    50, 10, 36, 40, 31, 46

Question 4 on its own page

Question 5

+3 marksOne correct option
  1. A

    A-2, B-4, C-3, D-1

  2. B

    A-2, B-3, C-4, D-1

  3. C

    A-2, B-3, C-1, D-4

  4. D

    A-3, B-2, C-4, D-1

Show answer

Correct answer

  • B

    A-2, B-3, C-4, D-1

Question 5 on its own page

Question 6

+4 marksOne correct option
  1. A

    A-3, B-3, C-5, D-1, E-5, F-4

  2. B

    A-3, B-2, C-5, D-2, E-5, F-4

  3. C

    A-3, B-3, C-5, D-2, E-5, F-4

  4. D

    A-3, B-2, C-5, D-1, E-5, F-4

Show answer

Correct answer

  • D

    A-3, B-2, C-5, D-1, E-5, F-4

Question 6 on its own page

Question 7

+3 marksOne or more correct options

Which of the following statement(s) is/are true?

Select all that apply.

  1. A

    Given a graph where all edges have positive weights, the shortest path produced by Dijkstra's and Bellman-Ford algorithm may be different, but the path weight would be the same.

  2. B

    Given a graph where weights of all edges are unique, there is always a unique shortest path from a source to destination in such a graph.

  3. C

    Bellman-Ford and Floyd-Warshall's algorithm can calculate the shortest path correctly if the graph has negative edge weights but does not have negative weight cycles.

  4. D

    The time complexity of Floyd-Warshall isO(V²), where V is the number of vertices in the graph.

Show answer

Correct answers

  • A

    Given a graph where all edges have positive weights, the shortest path produced by Dijkstra's and Bellman-Ford algorithm may be different, but the path weight would be the same.

  • C

    Bellman-Ford and Floyd-Warshall's algorithm can calculate the shortest path correctly if the graph has negative edge weights but does not have negative weight cycles.

Question 7 on its own page

Question 8

+3 marksOne or more correct options

Let G = (V,E) be an undirected connected graph with more than two vertices where each edge has a distinct weight, and e is a particular edge of G. Which of the following statement(s) is/are always true about the minimum cost spanning trees (MCSTs) of G ?

Select all that apply.

  1. A

    If e is the lightest weight edge of some cycle in G, then MCST of G includes e

  2. B

    If e is the heaviest weight edge of some cycle in G, then MCST of G excludes e

  3. C

    If e is the heaviest weight edge in G, then MCST of G excludes e

  4. D

    If e is the lightest weight edge in G, then MCST of G includes e

Show answer

Correct answers

  • B

    If e is the heaviest weight edge of some cycle in G, then MCST of G excludes e

  • D

    If e is the lightest weight edge in G, then MCST of G includes e

Question 8 on its own page

Question 9

+3 marksOne or more correct options

Which of the following statement(s) is/are true?

Select all that apply.

  1. A

    The smallest element in a max-heap is always at a leaf node

  2. B

    The smallest element in a max-heap is always at the lowest level

  3. C

    The second-largest element in a max-heap is always a child of the root node

  4. D

    Finding a minimum element in max-heap takes O(logn) time

  5. E

    Insert a new element in max-heap takes O(logn) time in worst case

Show answer

Correct answers

  • A

    The smallest element in a max-heap is always at a leaf node

  • C

    The second-largest element in a max-heap is always a child of the root node

  • E

    Insert a new element in max-heap takes O(logn) time in worst case

Question 9 on its own page

Question 10

+4 marksOne or more correct options

Select all that apply.

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answers

  • A
  • C
  • D
Question 10 on its own page

Question 11

+4 marksNumerical answer

While inserting the elements 60, 20, 68, 10, 45, 50, 30, 47, and 85 in an empty binary search tree (BST) in the sequence shown, the height of the created binary search tree is__________. Assume that the height of the empty tree is 0.

Show answer

Correct answer: 5

Question 11 on its own page

Question 12

+4 marksNumerical answer
Show answer

Correct answer: 6

Question 12 on its own page

Question 13

+4 marksNumerical answer
Show answer

Correct answer: 6

Question 13 on its own page

Question 14

+3 marksOne correct option

Based on the above data, answer the given subquestions.

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • D
Question 14 on its own page

Question 15

+3 marksOne correct option

Based on the above data, answer the given subquestions.

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • D
Question 15 on its own page