Data Structure
CIS · Midterm · 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
Department of Computing and Information System
Mid-Term Semester Project: Spring-2026
Program: B.Sc. in CIS
Course Code: CIS 122 and CIS 122L
Course Title: Data Structure with Lab
Total Marks: 60
[Instructions: Give clear and concise answers for every task. Use examples if necessary]
Scenario
Students will learn how to efficiently organize, manage, and process data in the computer science course titled Data Structure. This course is a core subject in the field of computer science. It covers several fundamental data structures, including arrays, stacks, queues, linked lists, graphs and trees. Each of these structures plays a crucial role in solving complex computational problems. By understanding these structures, students can select the most appropriate tool for a specific task, thereby optimizing both algorithm performance and memory usage.
Mr. Mehedi, the instructor of the Data Structure (DS) course for the Spring 2026 semester, delivered lectures on various topics prior to the midterm examination. These topics included basic data structures, their types and fundamental operations, arrays (covering insertion, deletion, updating, splitting and merging) and stacks. He also discussed different searching techniques, such as linear search and binary search.
After the midterm examination, Mr. Mehedi will continue his lectures on queues, linked lists, graphs, and trees, along with the corresponding sorting algorithms. It is also worth mentioning that the following assignments have been successfully completed by a group of students.
Task-1
In Spring 2026, the Department of Computing and Information Systems (CIS) under the Faculty of Science and Information Technology (FSIT) at Daffodil International University will organize a day-long educational tour to several historically significant sites in the Dhaka region. The primary objective of this tour is to provide students with an opportunity to explore the rich cultural and historical heritage of the area while fostering stronger bonds among students and faculty members outside the formal academic environment.
The tour will commence from the main campus of Daffodil International University (DIU). To facilitate proper planning and budgeting, the convener of the event, Mr. Md. Nasimul Kader, has prepared a detailed diagram (see Figure 01) illustrating the selected historical locations along with the estimated traveling costs between each site (measured in BDT). The diagram provides a clear visual representation of the routes and associated expenses, enabling efficient logistical planning and cost management.
After carefully determining and finalizing the travel costs between the designated locations, Mr. Md. Nasimul Kader formally submitted the proposed plan to the Head of the Department for review and approval. Upon receiving official authorization, he will subsequently communicate with the students to finalize the suitable date and time for the tour, ensuring maximum participation and convenience for all concerned.
[Figure: Different historical places with their corresponding traveling costs.]
Task-2
In the fiscal year 2025-2026, the Department of Computing and Information Systems (CIS) at Daffodil International University plans to submit several projects to the ICT Division of the Government of Bangladesh.
Mr. Rahimeen proposes a project on an online ticket purchasing system for both bus and train services. Mr. Sajid intends to develop a library management system focused on book organization. Meanwhile, Mr. Sakib is completing his project on web page access management. All projects will be completed and presented to the ICT Division after six months.
Task-3
A different statement on the tree data structure was made by the instructor of the course after the midterm examination. One of the statements was as follows:
"Suppose you randomly select 11 distinct positive integers (that are represented by the symbol L, I, Y, F, Q, A, B, C, R, E and T, respectively) between 30 and 189 (inclusive). The first, third, fifth, seventh, ninth and eleventh numbers are 80, 97, 63, XX, 170, and 49, respectively, where XX = [(the last two digits of your Student ID % 15) + (the smallest number in your dataset)]. Note that there are only six numbers less than 100, and only two numbers greater than 150." Then the instructor presented the following challenge:
Draw the Huffman Tree and find out the Huffman Code of the message "ARTIFICIAL".
In the classroom, all the students began to solve the given challenge. After some time, the course instructor noticed that one of the students, Mr. Israfil, successfully solved the challenge, while Mr. Ridoy successfully built a Huffman Tree but encountered difficulties in finding the Huffman Code. Eventually, Mr. Israfil helped him overcome these difficulties.
Task-4
One day, the Data Structure (DS) course lecturer covered an interesting topic regarding one-way single linked lists. Following that, every student is able to add, remove, update, merge and divide data to/from the specified linked list. The following diagram was then created by the course facilitator based on the lecture and some questions the students had asked.
[Figure: One way single linked list]
QA. Write the pseudocode to divide the linked list (see List 01 in Figure 02) into two linked lists based on the following condition:
- All elements greater than 25 or divisible by 4 should be placed in one linked list (say X).
- All other elements should be placed in a second linked list (say Y).
QB. Write the pseudocode to merge two linked lists (see X from QA and List 02 in Figure 02) into a single linked list. Ensure that the merged list should contain all unique elements from the two lists.
Every student is making a valiant effort to answer the course instructor's assigned question. The majority of students were unable to give the right response. However, a student-let's say Mr. Habib finally found a solution.
Theory Part (marks - 35)
Task-1 Marks - 10
Q1. Which type of data structure is used by three students in Task-2? Describe with proper explanation. [3] [CLO 3]
Q2. Is it possible to connect all the historical places starting from DIU? If yes, how can this be achieved? Briefly explain your answer. [3] [CLO 3]
Q3. How can you determine the chromatic number of the graph sketched by Mr. Md. Nasimul Kader? A detailed explanation is required with a proper diagram. [4] [CLO 3]
Task-2 Marks - 25
Q4. Determine the minimum travel cost required to connect all the historical places starting from X. Provide a detailed calculation. [4] [CLO 3]
Note: X = (The last two digits of your Student ID % 7)+1.
Q5. Identify the two places that have the minimum travel cost in Figure 01. A proper calculation is needed. [4] [CLO 3]
Q6. How does Mr. Israfil solve the challenge provided by the course instructor in Task-3? A detailed description is needed. [3+4] [CLO 3]
Q7. How did Mr. Habib solves the QA and QB? Elaborately described with necessary explanation. [5+5] [CLO 3]
Lab Part (marks - 25)
Task-1 Marks - 20
QL1. Implement the QA and QB using the c/c++ programming language that is made by Mr. Habib. [10+10] [CLO 4]
Task-2 Marks - 5
QL2. Explain details about your lab work (Task-1) and make a presentation with a short video (at least 4 minutes). [5] [CLO 4]
General Instructions
- Deadline: 05th April, 2026
- You have to submit the assignment in .docx or .pdf format (name it with your ID, such as 253-16-XXX.pdf), Zip the file if any supplementary files are needed.
- Submit the Project/Assignment in the BLC Semester Project section, the option of submission will be available there very soon.
- The deadline is fixed, no excuse will be considered if you missed the deadline.
- Marks will be deducted accordingly if any plagiarism of work is provided.
You must submit the hardcopy of the semester project on the Final Viva day. If anyone is missing at the viva, marks will be deducted.