Skip to content

Data Structure

SWE · Final · Spring 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, Spring 2024 Course Code: SE 131, Course Title: Data Structure Level: 1 Term: 3 Section: A, B, C, D, E, F, G, H, I Instructor: AB-A,B,E, RMS-C,D, MHS-F, SI-G,H,I Modality: Close Book Exam Date: Thursday 2 June 2024 Time: 12:00 PM - 02:00 PM Two hours (2:00) Marks: 40 Directions: - Students need to go through the CASE STUDY shown in this exam paper. - Analyze and answer specific sections based on your own thinking and work. - Answer all the questions, sequentially 1. Suppose you have some elements to construct a Binary Search Tree. The elements are: [CLO- 4, Level-3] [Marks-10] 51, 53, 60, 45, 70, 54, 32, 46, 21, 11, 18, 22, 74, 63, 91 a. Sketch the BST b. Delete 50 from the tree, as you have drawn from question no 'a', Sketch the BST c. Insert 70 from the tree, as you have drawn from question no 'a', Sketch the BST d. Deploy traversing in the BST: Perform in-order and post-order traversals of the BST obtained in part e. Map the types of trees: For each of the given examples, identify the type of tree (e.g., full tree, complete tree, balanced tree) and explain your reasoning: [Figure: Fig-I showing a binary tree with root 1, left child 2, right child 3, left child of 2 is 4, right child of 2 is 5] [Figure: Fig-II showing a binary tree with root 1, left child 2, right child 3, left child of 2 is 4, right child of 2 is 5, right child of 3 is 6] [Figure: Fig-III showing a binary tree with root 1, left child 2, right child 6, left child of 2 is 4, right child of 2 is 5] 2. Suppose you have a graph as follows: [CLO-4, Level-3] [Marks-10] [Figure: A directed graph with nodes 1, 2, 3, 4, 5, 6, 7, 8 and directed edges between them] Now: a. From Array of Linked list, which one is suitable to represent graph in a computer program. Express why this data structure is the best choice for representing the graph. b. Show the adjacency matrix representation of the given Graph c. Show the adjacency List representation of the given Graph d. Illustrate the Weighted graph and Complete Graph. 3. a. Draw the operation for circular/advance Queue, where maximum capacity of a queue is 5 memory locations. Now show one after another operation as given below: - Initially 10, 20 and 30 inserted - Delete three elements - Insert 40, 50, 60 - Delete 2 ITEMs - Insert 11, 22, 33, 44, 55 - Insert 66 - vii. Delete 5 elements - viii. Delete 1 Item b. Illustrate the Priority Queue with an example. [CLO-3, Level-3] [Total Marks-5] 4. Suppose you have to store "T", "N", "A","Y","A" inside a linked list. Assume the following 7 memory cells are available for the linked list: [Table: Cells 1000 | 1001 | 1002 | 1003 | 1004 | 1005 | 1006] [CLO-3, Level-3] [Total Marks-15] 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. b. After constructing the double-way linked list, as done in part 'a', insert "I" as the 6th element and "B" as the last element of the list, and sketch the resulting linked list. c. Following the creation of the double-way linked list in part 'b', delete all the "A"s from the linked list if exist, and sketch the resulting list. d. Construct a circular linked list with flag using the available memory cells for the given data in the question and sketch the resulting list. e. After constructing the circular linked list in question number 'd', insert "N" as the 1st element into the list, "P" as the last element and sketch the resulting linked list. f. Following the insertion in question number 'e', delete "B" from the list if it exists, and if it exists multiple times, then delete the first occurrence, and sketch the resulting list. g. Construct a circular linked list with a sentinel value using the available memory cells and store the given elements, and sketch the available linked lists. h. After constructing the circular linked list with a sentinel value in part 'g', delete the first occurrence of "A" from the linked list if it exists, and sketch the resulting list. i. Following the insertion in part 'h', insert "H", "I", "M", and "G" as the last four elements into the circular linked list with a sentinel value, and sketch the resulting list. j. Prepare the basic part of the code for linked list construction and print. [Marks Distribution 10*1.5]