Data Structure
CIS · Final · Spring 26
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Faculty of Science & Information Technology
Department of Computing and Information System
Final Examination, Spring-2026
Course Code: CIS122, Course Title: Data Structure
Level: 1 Term: 2
Exam Duration: 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. (a) Construct a flowchart to demonstrate the process of merging two sorted arrays into a single sorted array. | [4] | CO2
(b) Explain the conditions of stack overflow and stack underflow, and demonstrate how these conditions can be handled in a program. | [4] |
(c) Design a flowchart to illustrate the DEQUEUE operation in a queue. | [4] |
(d) Apply the binary search algorithm to determine whether the value x = 35 exists in the sorted array A[9] = {122, 112, 102, 84, 79, 57, 30, 21, 18}, and show the step-by-step process. | [4] |
(e) Develop pseudocode to insert the value 150 immediately after the node containing 76 in the given linked list (refer to Figure 01).
Head1 = 1x
08 (2x) -> 15 (3x) -> 23 (4x) -> 76 (5x) -> 44 Null
1x | 2x | 3x | 4x | 5x
Figure 01: One way single linked list | [4] |
(f) Explain the following terms with reference to Figure 02:
I. Branching Factor
II. Sibling
III. Ancestor
IV. Height of a tree
[Figure: A directed tree with 8 numbered nodes from 1 to 8]
Figure 02: Tree | [4] |
2. "Six distinct positive integers, represented by the symbols L, I, A, P, D, and E, are randomly selected from the range 15 to 100 (inclusive). The values of the first, second, fifth, and sixth symbols are 18, 87, 47, and 29, respectively. Note that only four of the numbers are less than 50."
Based on this information, apply the Huffman coding algorithm to construct the Huffman tree for the given symbols and determine the Huffman codes for the message 'APPLIED AI'. | [6] | CO4
3. (a) Calculate the minimum travel cost among the historical places shown in Figure 03 and analyze the process of determining the minimum travel cost.
[Figure: A graph with 5 vertices labeled 1 to 5 representing historical places and weighted edges between them]
Figure 03: Different historical places with their corresponding traveling costs. | [6] | CO3
(b) From Figure 03, prove that the sum of all the vertex degrees is equal to twice the number of edges. | [4] |