Data Structure and Algorithm

Daffodil International University Faculty of Science & Information Technology Department of Information Technology & Management Mid Term Examination, Fall 2026 Course Code: ITM 217; Course Title: Data Structure and Algorithms Section: A; Teacher: FR Time: 1:30 Hrs Marks: 25 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) Describe the different types of operations performed on Array Data structure. [Marks-5] b) Discuss the following terms with appropriate examples. Explain how each metric is used to evaluate the performance and efficiency of algorithms: [Marks-5] I. Time Complexity II. Space Complexity 2. a) A stack of files in an office tray follows the stack (LIFO) principle and can hold a maximum of N = 8 files. [Marks-4] Initially, the stack contains the following file numbers (from bottom to top): Stack: 105, 112, 118, 124, 131, ___, ___, ___ Apply the following operations on the stack: 1. PUSH(140) 2. PUSH(147) 3. PUSH(153) 4. PUSH(160) 5. POP(ITEM) 6. POP(ITEM) 7. PUSH(166) 8. POP(ITEM) Instructions • After each operation, clearly show the updated state of the stack. • For every POP operation additionally mention the removed book number. • Clearly indicate the step where stack overflow or stack underflow occurs. b) You are given a singly linked list that represents the scores of different students in a quiz, arranged in the following order: [Marks-6] [Figure: Singly linked list with nodes containing scores and addresses: HEAD (1000) -> [Addr: 1000 | 62 | 2400] -> [Addr: 2400 | 70 | 1800] -> [Addr: 1800 | 55 | 3200] -> [Addr: 3200 | 88 | 2000] -> [Addr: 2000 | 47 | 2800] -> [Addr: 2800 | 93 | NULL]] Demonstrate how to perform the following deletion operations on the linked list: 1. Deletion at the Beginning: Delete the first node (the node containing the score 62) from the list. 2. Deletion in the Middle: Delete the node containing the score 88 from the list. 3. Deletion at the End: Delete the last node (the node containing the score 93) from the list. Each operation is applied to the list as it stands after the previous operation. Instructions • For each deletion operation, clearly draw the linked list structure before and after the deletion. • Write pseudocode that shows how the node to be deleted is located (for example, using a temporary pointer and a previous pointer), how the pointers are updated to bypass the deleted node, and how the deleted node is released from memory. 3. a) Consider the following arithmetic expression P written in postfix notation: [Marks-5] P: 40, 8, 2, +, /, 6, 3, 2, -, *, + Calculate the value of the arithmetic expression P. (Use a stack to store operands and perform the evaluation step by step.)