Quiz Space

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

PDSA End Term: 1 September 2024, Set QDF3 (May 2024 term)

The IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) End Term paper sat on 1 Sept 2024, in the May 2024 term, set QDF3: 25 questions for 100 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.

Questions
25
Marks
100
Duration
180 min
MCQ
14
Numerical
5
MSQ
6
Take as mock testPractise with answers

Updated

Official paper: IIT M FOUNDATION DIPLOMA AN EXAM QDF3 01 Sep 2024 · No negative marking.

Question 1

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

Correct answer

  • B
Question 1 on its own page

Question 2

+4 marksOne correct option
  1. A

    10

  2. B

    11

  3. C

    12

  4. D

    13

Show answer

Correct answer

  • C

    12

Question 2 on its own page

Question 3

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

Correct answer

  • B
Question 3 on its own page

Question 4

+4 marksOne correct option

What is recurrence and time complexity for the worst case of Quick Sort ? Consider that algorithm select last element as pivot element.

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

Correct answer

  • B
Question 4 on its own page

Question 5

+4 marksOne correct option
  1. A

    I

  2. B

    F

  3. C

    E

  4. D

    H

  5. E

    G

Show answer

Correct answer

  • C

    E

Question 5 on its own page

Question 6

+4 marksOne correct option

Consider the following graph

Which of the following vertex sequence is the correct BFS traversal on the graph started from node 7? Assume that when a node has multiple neighbours, BFS would visit the numerically smaller valued node first.

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

Correct answer

  • D
Question 6 on its own page

Question 7

+4 marksOne correct option

Which of the following statements is true about Dijkstra's algorithm to find the shortest path? I. The shortest path returned by Dijkstra's algorithm always passes through the least number of vertices.
II. To decide which node to visit next, Dijkstra's algorithm selects the node with maximum known distance.

  1. A

    Only I is correct

  2. B

    Only II is Correct

  3. C

    Both I and II are correct

  4. D

    Both I and II are incorrect

Show answer

Correct answer

  • D

    Both I and II are incorrect

Question 7 on its own page

Question 8

+4 marksOne correct option

Which of the following is/are always true about the Bellman-Ford algorithm?
I. It can not detect negative weight cycles in graph.
II. It works correctly if the graph has negative edge weights but does not have negative weight cycles.
III. It finds the shortest paths from a single source vertex to all other vertices in the graph.

  1. A

    Only statement I and II are correct

  2. B

    Only statement I and III are correct

  3. C

    Only statement II and III are correct

  4. D

    All statements are correct

  5. E

    All statements are incorrect

Show answer

Correct answer

  • C

    Only statement II and III are correct

Question 8 on its own page

Question 9

+4 marksOne correct option
  1. A

    12

  2. B

    11

  3. C

    8

  4. D

    14 is a leaf node.

Show answer

Correct answer

  • D

    14 is a leaf node.

Question 9 on its own page

Question 10

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

Correct answer

  • B
Question 10 on its own page

Question 11

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

Correct answer

  • B
Question 11 on its own page

Question 12

+4 marksOne correct option

Let Z be an NP-complete problem and X and Y be two other problems not known to be in NP. X is polynomial time reducible to Z and Z is polynomial-time reducible to Y. Which one of the following statements is true?

  1. A

    Y is NP-complete

  2. B

    Y is NP-hard

  3. C

    X is NP-complete

  4. D

    X is NP-hard

Show answer

Correct answer

  • B

    Y is NP-hard

Question 12 on its own pageAlso asked in End Term 1 Sept 2024

Question 13

+4 marksNumerical answer
Show answer

Correct answer: 4

Question 13 on its own page

Question 14

+4 marksNumerical answer
Show answer

Correct answer: 19

Question 14 on its own page

Question 15

+4 marksNumerical answer
Show answer

Correct answer: 6

Question 15 on its own page

Question 16

+4 marksNumerical answer
Show answer

Correct answer: 5

Question 16 on its own page

Question 17

+4 marksNumerical answer
Show answer

Correct answer: 43

Question 17 on its own page

Question 18

+4 marksOne or more correct options

Select all that apply.

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

Correct answers

  • B
  • C
  • D
Question 18 on its own page

Question 19

+4 marksOne or more correct options

A baker is preparing an elaborate cake M. The recipe includes preparing several other components, each of which has its dependencies. The order in which these components must be prepared is given below:
1. Component X is used to make components P and Q.
2. Component Y is added to prepare components R and S.
3. Component T is prepared by mixing components Q and R.
4. Component Y is made by blending X.
5. Component U is made by mixing P and T.
6. Component V is made by adding sugar to component S.
7. The cake M is assembled by layering components U and V together.
The baker has enough assistants to prepare multiple components simultaneously, allowing the cake M to be completed in the minimum number of steps, considering all dependencies. Each step represents a time unit during which one or more components can be prepared in parallel. The component(s) prepared in the 3rd step is/are ___.

Select all that apply.

  1. A

    Q

  2. B

    T

  3. C

    R

  4. D

    U

  5. E

    S

Show answer

Correct answers

  • C

    R

  • E

    S

Question 19 on its own page

Question 20

+4 marksOne or more correct options

Consider a binary min-heap implemented using list. Which of the following lists represents a binary min-heap?

Select all that apply.

  1. A

    [6, 8, 15, 20, 12, 17, 21]

  2. B

    [6, 8, 17, 20, 12, 15, 21]

  3. C

    [6, 8, 15, 20, 17, 12, 21]

  4. D

    [6, 8, 17, 12, 15, 20, 21]

Show answer

Correct answers

  • A

    [6, 8, 15, 20, 12, 17, 21]

  • D

    [6, 8, 17, 12, 15, 20, 21]

Question 20 on its own page

Question 21

+4 marksOne or more correct options

Which of the following are possible valid codes for the character set S = {A, B, C, D, E, F}, generated using the Huffman algorithm?

Select all that apply.

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

Correct answers

  • B
  • D
Question 21 on its own page

Question 22

+4 marksOne or more correct options

Select all that apply.

  1. A
  2. B
  3. C
  4. D
  5. E
  6. F
Show answer

Correct answers

  • A
  • B
  • E
Question 22 on its own page

Question 23

+4 marksOne or more correct options

Consider the network given below with source s and sink t, with the numbers on the edges denoting maximum capacity across a particular edge.

Which of the following edges form a valid min cut in the given network?

Select all that apply.

  1. A

    Edges {ce, cd}

  2. B

    Edges {ac, ce, de}

  3. C

    Edges {fg, fi, hi}

  4. D

    Edges {fg, fh}

  5. E

    Edges {ij, ik}

Show answer

Correct answers

  • C

    Edges {fg, fi, hi}

  • E

    Edges {ij, ik}

Question 23 on its own page

Question 24

+4 marksOne correct option

Based on the above data, answer the given subquestions.

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

Correct answer

  • A
Question 24 on its own page

Question 25

+4 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 25 on its own page