Skip to content

Data Structure

SWE · Final · Fall 24

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

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 Software Engineering Faculty of Science & Information Technology Final Examination, Fall 2024 Course Code: SE131; Course Title: Data Structure Level: 2, Term: 1, Sections & Teachers: A, B, C, D, E, F, G, H, I, J, K, L, M, N Modality: Physical Instructor: AB, DMA, MSP, FRR, AAM, MJ, AAS, SAM Marks: 40 Time: 2:00 Hrs 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. A library has a book management system where books are organized in a database based on the year they were published. To optimize search operations, they decide to sort the books in a Binary Search Tree (BST), using the publication year as the key (elements). Below is the list of books along with their publication years: A Study in Scarlet(1887) (Root) The Warden(1855) Moondyne(1879) Laughter in the Dark(1932) White Oleander(1999) Himur Moddho Dupur(2009) Clarissa(1747) War and Peace(1867) Shesher Kabita(1929) a) Sketch the BST. Show the difference between a Binary Tree and a Binary Search Tree? [Marks-3] b) The admin of the system wants to see the books in sorted manner. We have pre-order, in-order, post-order method for the traversing. Examine which traversal should they deploy, and show the output? [Marks-3] c) In November, a new book named Kuhelika(1931) was added, Show the BST to reflect this addition. In December, A Study in Scarlet(1887) was sold out. Show the BST again to reflect this removal. [Marks-4] 2. Suppose you have this scenario, Moon wants to travel to Cox Bazar. For that reason, she started the journey in these directions with the following weight. At First, she started her journey from her 'Home' to 'Bus Stand' which cost 50 TK. Then, 'Bus Stand' to 'Comilla' cost 200 TK. After that, 'Comilla' to 'Feni' cost 220 TK. Then, 'Feni' to 'Chattrogram' which cost 250 TK. Finally, 'Chattrogram' to 'Cox Bazar' cost 350 TK. On the other hand, Moon can directly travel from 'Bus Stand' to 'Chattrogram' which costs 550 TK and from 'Home' to 'Feni' which costs 400 TK. After finishing her trip, she decided to come back with these directions from 'Cox Bazar' to 'Chattrogram' which cost 300 TK. Then, 'Chattrogram' to 'Home' which cost 600 TK. On the other hand, she can come back from 'Cox Bazar' to 'Comilla' which costs 700 TK then 'Comilla' to 'Home' which costs 220 TK. Besides that, she can directly come back to home from 'Cox Bazar' to 'Home' via a private car which costs 5000 TK. a) Draw the Directed graph by mentioning its types. [Marks-3] b) Show the Adjacency Matrix representation of the graph which you have just drawn in the previous question. [Marks-2] c) Show the Adjacency List representation of the graph which you have just drawn in the first question. [Marks-3] d) Illustrate the BSF Traversal 'Bus Stand' to 'Feni'. [Marks-2] 3. Consider this as an Empty Queue, initially Front and Rear values set to be as "-1". [Figure: A circular queue with numbers 0 to 7] a) Sketch the Queue after Enquiring the elements S, H, A, H, R, I, A and R. Show the front and rear values accordingly. [Marks-1] b) Now illustrate the Queue after performing a delete operation for three elements. Update the front and rear values accordingly. [Marks-1] c) Show the front and rear values after inserting M, G, O and N to the queue. [Marks-1] d) Demonstrate the final state of the Queue after a delete operation for four elements. Update the front and rear values accordingly. [Marks-1] e) Illustrate a Priority Queue and a Double-Ended Queue with relevant examples. [Marks-4] f) Simulate the basic part of the C program that demonstrates the Queue operations step by step, including Insert, Delete, along with handling Overflow and Underflow situation. [Marks-4] 4. You are developing a memory management system for a real-time multiplayer gaming platform. The system needs to efficiently manage a dynamic list of player Names connected to a game server. The Player Names are: Alice, Bob, Charli, David The memory cells available for storing scores are: 3001, 3002, 3003, 3004, 3005 a) Construct a double-way linked list using the available memory cells and store data elements in the list following the above instructions, and sketch the available linked lists. [Marks-2] b) After constructing the double-way linked list, as done in question 'a', insert "Tina" as the 1st element and "Mina" as the 3rd element and "Rina" as the last element of the list, and sketch the resulting linked list. [Marks-2] c) After constructing the double-way linked list, as done in question 'b', delete "Bob" from the linked list. Sketch the resulting linked list. [Marks-1] d) Construct a circular linked list with sentinel value using the available memory cells and store data elements in the list following the above instructions, and sketch the available linked lists. [Marks-1] e) After constructing a circular linked list with sentinel value in the question number "d", insert "Woe" as the last element. Sketch the resulting linked list. [Marks-1] f) Construct a circular linked list with flags using the available memory cells and store data elements in the list following the above instructions, and sketch the available linked lists. [Marks-1]