Indian Institute of Technology Madras
BS Degree Programme · Examination & Study Paper
Programming, Data Structures and Algorithms using Python
End Term · 22 Dec 2024 (Afternoon)
Examination Instructions & Guidelines
- Solve on notebook/paper first before checking solutions.
- MCQ: Exactly 1 option is correct. Negative marking applies.
- MSQ: One or more options correct. Select all to score.
- NAT: Numerical response. No negative marking.
- Scientific calculator allowed for all calculations.
- Official answer key is sealed at the end of this sheet.
- Q1MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q2MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q3MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q4MCQ4 Marks·Choose one option
- A55
- B58
- C60
- D48
- Q5MCQ4 Marks·Choose one option
- A0.5
- B0.33
- C0.17
- D0.83
- Q6MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q7MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q8MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q9MCQ4 Marks·Choose one option
- AOnly 1
- BOnly 2
- CBoth 1 and 2
- DNeither 1 nor 2
- Q10MCQ4 Marks·Choose one option
- AOnly statement I is true
- BOnly statement II is true
- CBoth statements are true
- DBoth statements are not true
- Q11MCQ4 Marks·Choose one option
Consider a complete binary tree with n nodes, where the left and the right subtrees of the root are min heaps. The upper bound to convert the tree to a min heap by an efficient algorithm is _______.
- A
- B
- C
- D
- A
- Q12MCQ4 Marks·Choose one option
Which of the following statement(s) is/are correct about the traversals in a binary search tree? 1. The root of the tree is always the first element of the inorder traversal. 2. The root of the tree is always the last element of the postorder traversal.
- AOnly statement 1 is correct
- BOnly statement 2 is correct
- CBoth the statements are correct
- DNone of the statements are correct
- Q13MCQ4 Marks·Choose one option
- A6
- B7
- C8
- D9
- Q14MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q15MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
- Q16MCQ4 Marks·Choose one option
- A1000
- B1500
- C2000
- D2500
- Q17MCQ4 Marks·Choose one option
A popular conference is being held, and there are several types of seats: VIP, Regular, and Economy. Each type of seat has a limited number of available spots. Each attendee has a preference for the type of seat they want, and the total number of attendees is greater than the number of available seats. The goal is to allocate the seats to attendees such that each attendee is assigned to their preferred seat type, and no seat type exceeds its capacity. How can the given problem of allocating seats to attendees based on their preferences and seat type capacities be effectively solved?
- AUsing a greedy algorithm to assign seats based on attendee preferences.
- BModeling the problem as a maximum flow network with capacities representing seat limits and flows representing the number of attendees assigned to each seat type.
- CImplementing a first-come, first-serve approach without considering the preferences or seat type capacities.
- DAssigning all attendees to the VIP seats first and distributing the remaining attendees among Regular and Economy seats.
- Q18MCQ4 Marks·Choose one option
Consider the following statements. 1. If an NP-hard problem A is polynomial time reducible to another problem B, then B belongs to the class NP. 2. If an NP-hard problem A is polynomial time reducible to another problem B, then B is NP- complete. Which of the following option is correct?
- AOnly statement 1 is true
- BOnly statement 2 is true
- CBoth statements 1 and 2 are true
- DBoth statements 1 and 2 are false
- Q19NAT4 Marks·Write the number
Your answer: - Q20NAT4 Marks·Write the number
Your answer: - Q21NAT4 Marks·Write the number
Your answer: - Q22NAT4 Marks·Write the number
Your answer: - Q23NAT4 Marks·Write the number
Your answer: - Q24NAT4 Marks·Write the number
Your answer: - Q25MSQ4 Marks·Choose all correct options
- A
- B
- C
- D
- A