Data Structures
CSE · Final · Fall 24
Paper 2 of 3Batch ALL · Mehedi Hasan RifatSwitch
Batch ALL
Paper 2 of 3
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Department of Computer Science and Engineering
Faculty of Science & Information Technology
Semester Final Examination, Fall 2024
Course Code: CSE123, Course Title: Data Structures
Level: 1 Term: 2 Batch: ALL
Time: 2 Hours
Marks: 40
Answer ALL Questions
[The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.]
1. The Election Commission of Bangladesh is analyzing the connectivity between polling stations in a district to optimize ballot transportation. Each polling station is represented as a node, and each road connecting two polling stations is represented as an edge with a weight (time in minutes). The connectivity is stored using an adjacency matrix.
The current connectivity graph is represented as follows:
Station A B C D
A 0 10 15 0
B 10 0 5 20
C 15 5 0 25
D 0 20 25 0
Problem Statement:
Question a: Graph Representation (3 Marks):
- Explain how the above adjacency matrix represents the graph.
- How would you interpret the value 15 in the matrix at position (A, C)?
Question b: Path Analysis (4 Marks):
- If Station A is selected as the starting point, list all directly connected stations and the respective travel times.
- Write the pseudocode for finding all directly connected stations for any given station in this adjacency matrix.
Question c: Why Graph data structure plays a vital role in computing. (3 marks)
2. You are a software engineer working for the Election Commission of Bangladesh to develop digital solutions for efficient election management. With the upcoming elections, the Election Commission needs help managing electoral divisions, organizing candidate data, and optimizing routes between polling stations.
The Election Commission manages a large amount of candidate data organized by unique candidate IDs. To enable fast retrieval and management, you need to store candidate data in a Binary Search Tree (BST).
Question a: Design a Binary Search Tree (BST) in C to store candidate IDs, where each node represents a candidate.
Question b: Implement the following functions:
1. Insert a new candidate ID into the BST.
2. Search for a candidate by ID to determine if they are in the system.
3. Display all candidate IDs in in-order traversal (ascending order of IDs).
3. An emergency response team uses a priority queue to handle incoming incidents based on their severity. Incidents with higher priority values are addressed first. The system is implemented using a Max-Heap. Each incident is represented by a priority value.
The following two functions handle the core operations of the priority queue:
1. Insert: Adds a new incident to the heap while maintaining the Max-Heap property.
2. Extract Max: Removes and returns the incident with the highest priority from the heap.
Here's the initial state of the heap:
Heap: [40, 30, 20, 15, 10]
Size: 5
After inserting a new incident with priority 35, the heap is updated.
Question a: Show the step-by-step transformation of the heap after inserting 35. Explain how the Max-Heap property is restored. (3 Marks)
The highest-priority incident is now resolved, and the Extract Max operation is performed.
Question b: Show the heap after removing the highest-priority element. Explain how the heap is adjusted to restore the Max-Heap property. (4 Marks)
4. Reflecting on your course project experience in Data Structures, describe how you applied a specific data structure (such as a linked list, stack, queue, or binary tree) to solve a problem within your project. In your answer, include:
Question a: Description of the Problem (2 Marks): Briefly explain the problem or requirement that led you to select this particular data structure.
Question b: Data Structure Selection (2 Marks): Explain why you chose this data structure over others. What advantages did it offer for solving the problem?
Question c: Implementation and Challenges (3 Marks): Describe the implementation approach you followed and any challenges you faced. How did you overcome these challenges?