Quiz Space

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

PDSA End Term: 3 April 2022, Set AN1 (January 2022 term)

The IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) End Term paper sat on 3 Apr 2022, in the January 2022 term, set AN1: 30 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
30
Marks
100
Duration
180 min
MCQ
22
MSQ
4
Numerical
4
Take as mock testPractise with answers

Updated

Official paper: IIT M FOUNDATION DIPLOMA ENDTERM FN1 3 Apr 2022 · No negative marking.

Question 1

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

Correct answer

  • D
Question 1 on its own page

Question 2

+3 marksOne correct option

Which of the following statements is/are true about the Quicksort algorithm? Assume that the first element in the list selected as pivot for partitioning each time.
I. The best case is when the pivot element always divides the list into two equal halves. II. The worst case is when the input list is arranged in either ascending or descending order.

  1. A

    Only I

  2. B

    Only II

  3. C

    Both I and II

  4. D

    None

Show answer

Correct answer

  • C

    Both I and II

Question 2 on its own page

Question 3

+3 marksOne correct option
  1. A

    Insertion of the new node at the front of the linked list.

  2. B

    Insertion of the new node at the end of the linked list.

  3. C

    Deletion of the first node of the linked list.

  4. D

    Deletion of the last node of the linked list.

Show answer

Correct answer

  • D

    Deletion of the last node of the linked list.

Question 3 on its own page

Question 4

+3 marksOne correct option
  1. A

    2, 3, 1, 4, 3, 4, 3, 3

  2. B

    4, 2, 2, 3, 1, 3, 3, 5

  3. C

    1, 2, 3, 1, 4, 2, 1, 2

  4. D

    1, 2, 2, 2, 2, 1, 3, 4

Show answer

Correct answer

  • C

    1, 2, 3, 1, 4, 2, 1, 2

Question 4 on its own page

Question 5

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

Correct answer

  • C
Question 5 on its own page

Question 6

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

Correct answer

  • C
Question 6 on its own page

Question 7

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

Correct answer

  • D
Question 7 on its own page

Question 8

+3 marksOne correct option

A data structure is required for storing a set of integers such that each of the following operations can be done in O(log n) time, where n is the number of elements in the set.
I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which of the following options are true?

  1. A

    A heap can be used but not a balanced binary search tree

  2. B

    A balanced binary search tree can be used but not a heap

  3. C

    Both balanced binary search tree and heap can be used

  4. D

    Neither balanced search tree nor heap can be used

Show answer

Correct answer

  • B

    A balanced binary search tree can be used but not a heap

Question 8 on its own page

Question 9

+3 marksOne correct option

Suppose the letters {a, b, c, d, e} occur with the following frequencies.

How many bits will be used to encode the letter d in the Huffman code for this alphabet?

  1. A

    1

  2. B

    2

  3. C

    3

  4. D

    4

Show answer

Correct answer

  • B

    2

Question 9 on its own page

Question 10

+3 marksOne correct option
  1. A

    2

  2. B

    3

  3. C

    4

  4. D

    5

Show answer

Correct answer

  • B

    3

Question 10 on its own page

Question 11

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

Correct answer

  • D
Question 11 on its own page

Question 12

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

Correct answer

  • A
Question 12 on its own page

Question 13

+3 marksOne correct option
  1. A

    7

  2. B

    8

  3. C

    9

  4. D

    10

Show answer

Correct answer

  • D

    10

Question 13 on its own page

Question 14

+3 marksOne correct option

Which of the following option represents the fail function (or prefix function) for pattern 'bonbon' in the Knuth-Morris-Pratt (KMP) algorithm?

  1. A

    [0, 0, 0, 1, 1, 2]

  2. B

    [0, 0, 0, 1, 2, 3]

  3. C

    [0, 0, 1, 2, 3, 3]

  4. D

    [0, 0, 0, 0, 1, 2]

Show answer

Correct answer

  • B

    [0, 0, 0, 1, 2, 3]

Question 14 on its own page

Question 15

+3 marksOne correct option

A problem in NP is NP-complete if___________

  1. A

    It can be reduced to the 3-SAT problem in polynomial time

  2. B

    It can be reduced to any other problem in NP in polynomial time

  3. C

    some problem in NP can be reduced to it in polynomial time

  4. D

    The 3-SAT problem can be reduced to it in polynomial time

Show answer

Correct answer

  • D

    The 3-SAT problem can be reduced to it in polynomial time

Question 15 on its own pageAlso asked in End Term 3 Apr 2022, End Term 11 Dec 2022

Question 16

+3 marksOne correct option

A company makes two kinds of leather belts, belt A and belt B. Belt A is a high quality belt and belt B is of lower quality. The respective profits are Rs 5 and Rs 6 per belt. The production of each of type A requires twice as much time as a belt of type B, and if all belts were of type B, the company could make 1,000 belts per day. The supply of leather is sufficient for only 800 belts per day (both A and B combined). Belt A requires a fancy buckle and only 300 of these are available per day. There are only 800 buckles a day available for belt B.
The above problem is to be formulated as a linear programming problem. Let x1 and x2 be the number of belts of type A and B, respectively, manufactured each day. Which of the following is not a valid constraint?

  1. A

    x1 ≤ 300

  2. B

    x2 ≤ 800

  3. C

    x1 + 2x2 ≤ 1000

  4. D

    2x1 + x2 ≤ 1000

Show answer

Correct answer

  • C

    x1 + 2x2 ≤ 1000

Question 16 on its own page

Question 17

+4 marksOne correct option
  1. A

    Leaves the stack S unchanged

  2. B

    Reverses the order of elements in the stack S

  3. C

    Swaps the elements of the top and bottom positions in stack S, keeping the other elements in between in the same order

  4. D

    Empties the stack S

Show answer

Correct answer

  • A

    Leaves the stack S unchanged

Question 17 on its own page

Question 18

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

Correct answer

  • C
Question 18 on its own page

Question 19

+4 marksOne correct option
  1. A

    0

  2. B

    1

  3. C

    2

  4. D

    3

Show answer

Correct answer

  • C

    2

Question 19 on its own page

Question 20

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

Correct answer

  • A
Question 20 on its own page

Question 21

+4 marksOne or more correct options

Select all that apply.

  1. A

    23, 36, 72, 12, 54, 83

  2. B

    36, 72, 23, 12, 54, 83

  3. C

    36, 23, 72, 12, 83, 54

  4. D

    36, 23, 72, 12, 54, 83

  5. E

    72, 23, 36, 54, 12, 83

Show answer

Correct answers

  • A

    23, 36, 72, 12, 54, 83

  • B

    36, 72, 23, 12, 54, 83

  • D

    36, 23, 72, 12, 54, 83

Question 21 on its own page

Question 22

+3 marksOne or more correct options

Suppose we obtain the following BFS tree rooted at node G for an undirected graph with vertices {A, B, C, D, E, F, G, H, I, J, K}.

Which of the following can not be an edge/edges in the original graph?

Select all that apply.

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

Correct answers

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

Question 23

+3 marksOne or more correct options

Which of the following statement is true about Dijkstra's algorithm to find shortest path?

Select all that apply.

  1. A

    Dijkstra’s algorithm doesn’t work for graphs with negative weights.

  2. B

    It returns the shortest path between all pair of nodes.

  3. C

    The shortest path returned by Dijkstra's algorithm always passes through the least number of vertices.

  4. D

    To decide which node to visit next, Dijkstra's algorithm selects the node with smallest known distance

  5. E

    It can find the shortest path for only acyclic graphs

Show answer

Correct answers

  • A

    Dijkstra’s algorithm doesn’t work for graphs with negative weights.

  • D

    To decide which node to visit next, Dijkstra's algorithm selects the node with smallest known distance

Question 23 on its own pageAlso asked in End Term 3 Apr 2022

Question 24

+3 marksOne or more correct options

Which of the following statements is true about binary trees? Assume that the height of the empty tree is 0.

Select all that apply.

  1. A

    If the number of nodes in the tree is n, then the maximum height of the tree can be n.

  2. B

    If the number of nodes in the tree is n, then the minimum height of the tree will be int(log(n)) + 1.

  3. C

    The number of leaf nodes is always one more than the number of non-leaf nodes.

  4. D

    If number of nodes in the tree is n, then the number of edges in the tree will be n + 1.

  5. E

    Maximum number of nodes at level L will be 2*^(L)* (if level number starts from 0(root node)).

Show answer

Correct answers

  • A

    If the number of nodes in the tree is n, then the maximum height of the tree can be n.

  • B

    If the number of nodes in the tree is n, then the minimum height of the tree will be int(log(n)) + 1.

  • E

    Maximum number of nodes at level L will be 2*^(L)* (if level number starts from 0(root node)).

Question 24 on its own page

Question 25

+4 marksNumerical answer

What is the weight of the minimum spanning tree for the given graph?
NOTE: Enter your answer to the nearest integer.

Show answer

Correct answer: 13

Question 25 on its own page

Question 26

+4 marksNumerical answer

NOTE: Enter your answer to the nearest integer.

Show answer

Correct answer: 54

Question 26 on its own page

Question 27

+4 marksNumerical answer

NOTE: Enter your answer to the nearest integer.

Show answer

Correct answer: 4

Question 27 on its own page

Question 28

+4 marksNumerical answer

NOTE: Enter your answer to the nearest integer.

Show answer

Correct answer: 17

Question 28 on its own page

Question 29

+4 marksOne correct option

Based on the above data, answer the given subquestions.

  1. A

    length of the longest strictly decreasing subsequence

  2. B

    length of the longest strictly increasing subsequence

  3. C

    length of the longest contiguous strictly decreasing sequence

  4. D

    length of the longest contiguous strictly increasing sequence

Show answer

Correct answer

  • A

    length of the longest strictly decreasing subsequence

Question 29 on its own page

Question 30

+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

  • A
Question 30 on its own page