BOON UNIVERSITY JAAMACADDA BOON
FACULTY OF COMPUTER SCIENCE
SEMESTER 2, ACADEMIC YEAR 2025/2026
DATA STRUCTURE AND ALGORITHM
Name: _________________________________________________ ID NO: _______________
Time Allowed: ____________ Date: JUN, ___,2026
Instructor: Mr. Muhiyadiin Hussein
Part I: Multiple Choice Questions (10 Marks)
Choose the correct answer.
1. What is a graph?
A) A linear collection of elements
B) A non-linear structure consisting of vertices and edges
C) A sorting algorithm
D) A linked list
2. In a graph, a connection between two vertices is called:
A) Node B) Path C) Edge D) Root
3. Which of the following is true about a directed graph?
A) Edges have no direction B) Connections are always mutual
C) Edges have a specific direction D) It contains no vertices
4. What is the topmost node in a tree called?
A) Leaf B) Child C) Root D) Edge
5. Which tree traversal visits nodes in the order Root → Left → Right?
A) Inorder B) Preorder C) Postorder D) Level Order
6. Shell Sort is an improvement of:
A) Bubble Sort B) Merge Sort C) Insertion Sort D) Quick Sort
7. In Quick Sort, the element used to partition the array is called:
A) Key B) Root C) Index D) Pivot
8. Which sorting algorithm repeatedly compares adjacent elements and swaps
them if necessary?
A) Quick Sort B) Shell Sort C) Bubble Sort D) Selection Sort
9. A linked list consists of:
A) Vertices and edges B) Nodes connected using pointers
C) Fixed-size memory blocks D) Arrays only
[Link] Sort performs best when:
A) The data is reverse sorted B) The data is already sorted
C) The dataset is very large D) Pivot selection is random
Part II: Direct Questions (30 Marks)
1. Define a graph.
2. Differentiate between a directed graph and an undirected graph.
3. Define the following terminologies:
a. a) Vertex b) Edge c) Cycle d) Loop
4. Mention any three real-world applications of graphs.
5. What is a tree? Why are trees used in computer science?
6. List of three types of trees.
7. Explain the difference between Quick Sort and Shell Sort.
8. What is the linked list? Mention any two applications of linked lists.
Part III: Problem Solving / Practical Questions (12 Marks)
1. Bubble Sort (2 Marks)
Write a C++ function to sort the following array in ascending order using Bubble
Sort. int arr[] = {45, 12, 34, 8, 23};
2. Insertion Sort (2 Marks)
Write a C++ function to sort the following array in ascending order using Insertion
Sort. int arr[] = {12, 11, 13, 5, 9};
3. Shell Sort (2 Marks)
Write a C++ program that uses Shell Sort to sort the following array.
int arr[] = {12, 34, 54, 2, 3};
4. Quick Sort (2 Marks)
Write the partition () and quicksort () functions to sort the following array.
int arr[] = {10, 7, 8, 9, 1, 5};
5. Linked List (2 Marks)
Create a singly linked list containing the values: 10 → 20 → 30
Then write a function to traverse and display all nodes.
6. Graph and Tree (2 Marks)
Write a function to create the following undirected graph using an adjacency list.
0 --- 1
\ /