Data Structures and Algorithms Exam - C++

Solutions
Your Name
May 25, 2025

QUESTION ONE
(a) Definition of a Data Structure
A data structure is a specialized format for organizing, storing, and managing
data to enable efficient access, modification, and retrieval. Data structures
are foundational in computer science as they provide the building blocks for
designing efficient algorithms and systems. They can be broadly classified into:

• Linear Data Structures: Elements are arranged sequentially, e.g., ar-

rays, linked lists, stacks, and queues. These are suitable for sequential
processing or when data access follows a predictable order.
• Non-Linear Data Structures: Elements are organized hierarchically or
in a networked manner, e.g., trees, graphs, and heaps. These are ideal for
representing complex relationships, such as hierarchies or networks.
• Static vs. Dynamic: Static structures (e.g., arrays) have a fixed size at
compile time, while dynamic structures (e.g., linked lists, dynamic arrays)
can resize during runtime.

Data structures are selected based on application requirements, such as ac-

cess speed, memory efficiency, or ease of implementation. For instance, arrays
provide O(1) indexed access but are inflexible for insertions, while linked lists
excel in dynamic insertions and deletions but have O(n) access time.
Significance: Data structures bridge raw data and efficient algorithms,
enabling optimized solutions for tasks like searching, sorting, and data man-
agement. They are critical in applications ranging from databases to real-time
systems.

(b) Reasons for Using Data Structures

Data structures are indispensable in software development for the following
reasons:

1
 1. Efficient Data Organization and Retrieval: Structures like hash ta-
bles provide O(1) average-case retrieval, while balanced binary search trees
(e.g., AVL trees) offer O(log n) search time for hierarchical data.
2. Optimized Memory Usage: Sparse matrices or linked lists minimize
memory waste for irregular or dynamic data, unlike arrays, which may
allocate unused space.
3. Enhanced Algorithm Performance: Many algorithms rely on specific
data structures for efficiency, e.g., heaps in Dijkstra’s algorithm for short-
est paths or priority queues in scheduling.
4. Scalability in Application Development: Data structures like graphs
support scalable applications, such as social networks, GPS navigation, or
recommendation systems.
5. Improved Code Maintainability: Encapsulating data and operations
within structures like classes or structs promotes modularity, reusability,
and maintainability.

Example: In a database, B-trees index records to ensure O(log n) query

performance, enabling scalability for millions of records.
Note: Choosing the right data structure requires balancing trade-offs be-
tween time complexity, space complexity, and implementation complexity based
on the application’s needs.

(e) C++ Code for Stack Operations

A stack is a linear data structure following the Last-In-First-Out (LIFO) prin-
ciple, where elements are added (pushed) and removed (popped) from the top.
Key operations include push, pop, peek, isEmpty, and isFull (for array-based
stacks). Stacks are used in function call stacks, expression evaluation, and back-
tracking algorithms.
Implementation Details: The implementation uses a fixed-size array with
a capacity of 5 elements. It includes error handling for overflow/underflow, a
peek operation, and a test program to demonstrate functionality.
1 # include <iostream >
2 using namespace std;
3

4 class Stack {
5 private :
6 static const int MAX = 5; // Maximum size of the
stack
7 int arr[MAX ];
8 int top;
9

10 public :

2
11 Stack () { top = -1; } // Constructor initializes top
to -1 ( empty stack )
12

13 bool isEmpty () const {

14 return top == -1;
15 }
16

17 bool isFull () const {

18 return top == MAX - 1;
19 }
20

21 void push(int val) {

22 if ( isFull ()) {
23 cout << " Stack ␣ Overflow :␣ Cannot ␣push␣" << val
<< endl;
24 return ;
25 }
26 arr [++ top] = val;
27 cout << " Pushed ␣" << val << endl;
28 }
29

30 void pop () {
31 if ( isEmpty ()) {
32 cout << " Stack ␣ Underflow :␣ Cannot ␣pop␣from␣
empty ␣ stack " << endl;
33 return ;
34 }
35 cout << " Popped ␣" << arr[top --] << endl;
36 }
37

38 int peek () const {

39 if ( isEmpty ()) {
40 cout << " Stack ␣is␣empty " << endl;
41 return -1; // Return sentinel value
42 }
43 return arr[top ];
44 }
45

46 void display () const {

47 if ( isEmpty ()) {
48 cout << " Stack ␣is␣empty " << endl;
49 return ;
50 }
51 cout << " Stack ␣ elements ␣(top␣to␣ bottom ):␣";
52 for (int i = top; i >= 0; i--) {
53 cout << arr[i] << "␣";

3
54 }
55 cout << endl;
56 }
57 };
58

59 int main () {
60 Stack s;
61 s.push (10);
62 s.push (20);
63 s.push (30);
64 s. display ();
65 cout << "Top␣ element :␣" << s.peek () << endl;
66 s.pop ();
67 s. display ();
68 s.push (40);
69 s.push (50);
70 s.push (60); // Should trigger overflow
71 s. display ();
72 s.pop ();
73 s.pop ();
74 s.pop ();
75 s.pop (); // Should trigger underflow
76 s. display ();
77 return 0;
78 }

Time and Space Complexity:

• Push: O(1)

• Pop: O(1)
• Peek: O(1)
• Display: O(n), where n is the number of elements
• Space: O(MAX) for the fixed-size array

Output:
Pushed 10
Pushed 20
Pushed 30
Stack elements (top to bottom): 30 20 10
Top element: 30
Popped 30
Stack elements (top to bottom): 20 10
Pushed 40

4
Pushed 50
Stack Overflow: Cannot push 60
Stack elements (top to bottom): 50 40 20 10
Popped 50
Popped 40
Popped 20
Popped 10
Stack is empty
Note: The implementation includes bounds checking, uses const for non-
modifying methods, and provides a complete test program. For dynamic stacks,
a linked list or dynamic array (e.g., std::vector) could be used to avoid fixed-
size limitations.

QUESTION TWO
(a) Definition of a Queue
A queue is a linear data structure that adheres to the First-In-First-Out (FIFO)
principle. Elements are added (enqueued) at the rear and removed (dequeued)
from the front. Key operations include enqueue, dequeue, front, isEmpty, and
isFull.
Types of Queues:

• Circular Queue: Connects the last element to the first, improving space
efficiency.
• Priority Queue: Dequeues elements based on priority rather than inser-
tion order.
• Deque: Allows insertion and deletion at both ends.

Applications: Queues are used in task scheduling (e.g., CPU process schedul-
ing), breadth-first search (BFS), and buffer management (e.g., printer queues).
Note: Queues are essential for managing ordered tasks or data streams,
with variations like priority queues used in real-time systems.

(e) C++ Code for Doubly Linked List Operations

A doubly linked list is a linear data structure where each node contains data,
a pointer to the next node, and a pointer to the previous node, enabling bidi-
rectional traversal. This structure supports efficient insertions, deletions, and
reverse traversals compared to singly linked lists.
Key Operations:
• Append: Adds a node at the end.
• Insert at Position: Inserts a node at a specified position.

5
 • Delete: Removes a node with a given value.
• Display: Prints elements forward.
• Reverse Display: Prints elements backward using prev pointers.

1 # include <iostream >

2 using namespace std;
3

4 struct Node {
5 int data;
6 Node* prev;
7 Node* next;
8 Node(int val) : data(val), prev( nullptr ), next(
nullptr ) {}
9 };
10

11 class DoublyLinkedList {
12 private :
13 Node* head;
14

15 public :
16 DoublyLinkedList () : head( nullptr ) {}
17

18 void appendNode (int val) {

19 Node* newNode = new Node(val);
20 if (! head) {
21 head = newNode ;
22 return ;
23 }
24 Node* temp = head;
25 while (temp ->next) {
26 temp = temp ->next;
27 }
28 temp ->next = newNode ;
29 newNode ->prev = temp;
30 }
31

32 void insertAtPosition (int val , int pos) {

33 if (pos < 1) {
34 cout << " Invalid ␣ position " << endl;
35 return ;
36 }
37 Node* newNode = new Node(val);
38 if (pos == 1) {
39 newNode ->next = head;

6
40 if (head) head ->prev = newNode ;
41 head = newNode ;
42 return ;
43 }
44 Node* temp = head;
45 for (int i = 1; i < pos - 1 && temp; i++) {
46 temp = temp ->next;
47 }
48 if (! temp) {
49 cout << " Position ␣out␣of␣ range " << endl;
50 delete newNode ;
51 return ;
52 }
53 newNode ->next = temp ->next;
54 newNode ->prev = temp;
55 if (temp ->next) temp ->next ->prev = newNode ;
56 temp ->next = newNode ;
57 }
58

59 void deleteNode (int val) {

60 if (! head) {
61 cout << "List␣is␣ empty " << endl;
62 return ;
63 }
64 Node* temp = head;
65 if (head ->data == val) {
66 head = head ->next;
67 if (head) head ->prev = nullptr ;
68 delete temp;
69 return ;
70 }
71 while (temp && temp ->data != val) {
72 temp = temp ->next;
73 }
74 if (! temp) {
75 cout << " Value ␣not␣ found " << endl;
76 return ;
77 }
78 temp ->prev ->next = temp ->next;
79 if (temp ->next) temp ->next ->prev = temp ->prev;
80 delete temp;
81 }
82

83 void displayList () const {

84 if (! head) {
85 cout << "List␣is␣ empty " << endl;

7
86 return ;
87 }
88 cout << "List␣( forward ):␣";
89 Node* temp = head;
90 while (temp) {
91 cout << temp ->data << "␣";
92 temp = temp ->next;
93 }
94 cout << endl;
95 }
96

97 void displayReverse () const {

98 if (! head) {
99 cout << "List␣is␣ empty " << endl;
100 return ;
101 }
102 Node* temp = head;
103 while (temp ->next) temp = temp ->next;
104 cout << "List␣( reverse ):␣";
105 while (temp) {
106 cout << temp ->data << "␣";
107 temp = temp ->prev;
108 }
109 cout << endl;
110 }
111

112 ~ DoublyLinkedList () {
113 Node* current = head;
114 while ( current ) {
115 Node* next = current ->next;
116 delete current ;
117 current = next;
118 }
119 }
120 };
121

122 int main () {

123 DoublyLinkedList dll;
124 dll. appendNode (10);
125 dll. appendNode (20);
126 dll. appendNode (30);
127 dll. displayList ();
128 dll. displayReverse ();
129 dll. insertAtPosition (15 , 2);
130 dll. displayList ();
131 dll. deleteNode (20);

8
132 dll. displayList ();
133 dll. displayReverse ();
134 return 0;
135 }

Time and Space Complexity:

• Append: O(n) to traverse to the end

• Insert at Position: O(n) for traversal
• Delete: O(n) to find the node

• Display (Forward/Reverse): O(n)

• Space: O(n) for n nodes
Output:
List (forward): 10 20 30
List (reverse): 30 20 10
List (forward): 10 15 20 30
List (forward): 10 15 30
List (reverse): 30 15 10
Note: The implementation includes a destructor to prevent memory leaks,
robust error handling, and a test program. Doubly linked lists are efficient for
applications requiring frequent insertions/deletions and bidirectional traversal,
such as undo/redo functionality in editors.

QUESTION THREE
(a) Difference between Sequential and Interval Search Al-
gorithms
Search algorithms locate a target element in a dataset. The differences between
sequential (linear) and interval (e.g., binary) search are:

• Sequential Search (Linear Search):

– Mechanism: Checks each element sequentially until the target is
found or the list ends.
– Time Complexity: O(n) for average and worst cases.
– Space Complexity: O(1).
– Suitability: Works on unsorted or sorted data, ideal for small datasets
or when simplicity is needed.
– Advantages: No preprocessing; works on any list.

9
 – Disadvantages: Inefficient for large datasets.
• Interval Search (Binary Search):
– Mechanism: Operates on sorted arrays, dividing the search space in
half each iteration by comparing the target with the middle element.
– Time Complexity: O(log n) for average and worst cases.
– Space Complexity: O(1) iterative; O(log n) recursive.
– Suitability: Ideal for large, sorted datasets.
– Advantages: Highly efficient for large data.
– Disadvantages: Requires sorted data, which may need O(n log n)
preprocessing.

Note: Sequential search is simpler but less efficient, while binary search
excels in performance but requires sorted data. The choice depends on data
size and whether sorting is feasible.

(b) C++ Code for Linear Search

Linear search sequentially checks each element, returning the index of the target
or -1 if not found. It’s simple but inefficient for large datasets.
1 # include <iostream >
2 using namespace std;
3

4 int linearSearch (int arr [], int n, int key) {

5 for (int i = 0; i < n; i++) {
6 if (arr[i] == key) {
7 return i;
8 }
9 }
10 return -1;
11 }
12

13 int main () {
14 int arr [] = {5, 2, 9, 1, 7, 6};
15 int n = sizeof (arr) / sizeof (arr [0]);
16 int key = 7;
17 int result = linearSearch (arr , n, key);
18 if ( result != -1) {
19 cout << " Element ␣" << key << "␣found ␣at␣ index ␣"
<< result << endl;
20 } else {
21 cout << " Element ␣" << key << "␣not␣ found " << endl
;
22 }

10
23 return 0;
24 }

Time and Space Complexity:

• Time: O(n)

• Space: O(1)
Output:
Element 7 found at index 4

Note: Linear search is robust for unsorted data or small lists but scales
poorly. It’s useful in scenarios where sorting is impractical or data is dynamic.

(c) C++ Code for Binary Search

Binary search efficiently locates a target in a sorted array by halving the search
space each iteration. This implementation is iterative for O(1) space complexity.
1 # include <iostream >
2 using namespace std;
3

4 int binarySearch (int arr [], int n, int key) {

5 int left = 0, right = n - 1;
6 while (left <= right ) {
7 int mid = left + ( right - left) / 2; // Avoids
overflow
8 if (arr[mid] == key) {
9 return mid;
10 } else if (arr[mid] < key) {
11 left = mid + 1;
12 } else {
13 right = mid - 1;
14 }
15 }
16 return -1;
17 }
18

19 int main () {
20 int arr [] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
21 int n = sizeof (arr) / sizeof (arr [0]);
22 int key = 6;
23 int result = binarySearch (arr , n, key);
24 if ( result != -1) {
25 cout << " Element ␣" << key << "␣found ␣at␣ index ␣"
<< result << endl;

11
26 } else {
27 cout << " Element ␣" << key << "␣not␣ found " << endl
;
28 }
29 return 0;
30 }

Time and Space Complexity:

• Time: O(log n)
• Space: O(1)

Output:
Element 6 found at index 5
Note: Binary search requires a sorted array, making it ideal for static, large
datasets. The mid calculation prevents integer overflow. It’s significantly faster
than linear search for large n.

QUESTION FOUR
(a) Definition of a Sorting Algorithm
A sorting algorithm arranges elements in a list or array in a specific order
(typically ascending or descending). Sorting is critical for data organization,
efficient searching, and visualization in applications like databases and user
interfaces.
Types:

• Comparison-Based: Use comparisons to determine order (e.g., bubble

sort, quicksort).
• Non-Comparison-Based: Exploit data properties (e.g., counting sort,
radix sort).
• Stable vs. Unstable: Stable algorithms preserve the relative order of
equal elements (e.g., insertion sort); unstable ones do not (e.g., quicksort).
Note: The choice of sorting algorithm depends on data size, data distribu-
tion, stability requirements, and whether in-place sorting is needed.

(b) C++ Code for Selection Sort

Selection sort divides the array into sorted and unsorted portions. In each pass,
it finds the minimum element in the unsorted portion and swaps it with the first
element of the unsorted portion.
How It Works:

12
 1. Initialize the sorted portion as empty (index 0).
2. For each pass i from 0 to n-2:
• Find the minimum element in the unsorted portion (arr[i..n-1]).
• Swap the minimum with arr[i].
3. After n-1 passes, the array is sorted.
When It’s Efficient:
• Small Datasets: Simple implementation with minimal overhead.
• Minimal Swaps: Performs O(n) swaps, useful when write operations are
costly (e.g., flash memory).
• Limited Memory: In-place sorting with O(1) space.
Limitations: O(n²) time complexity makes it inefficient for large datasets
compared to quicksort or mergesort.
1 # include <iostream >
2 using namespace std;
3

4 void selectionSort (int arr [], int n) {

5 for (int i = 0; i < n - 1; i++) {
6 int minIndex = i;
7 for (int j = i + 1; j < n; j++) {
8 if (arr[j] < arr[ minIndex ]) {
9 minIndex = j;
10 }
11 }
12 if ( minIndex != i) {
13 swap(arr[i], arr[ minIndex ]);
14 }
15 }
16 }
17

18 int main () {
19 int arr [] = {64 , 34, 25, 12, 22};
20 int n = sizeof (arr) / sizeof (arr [0]);
21 cout << " Original ␣array :␣";
22 for (int i = 0; i < n; i++) cout << arr[i] << "␣";
23 cout << endl;
24 selectionSort (arr , n);
25 cout << " Sorted ␣ array :␣";
26 for (int i = 0; i < n; i++) cout << arr[i] << "␣";
27 cout << endl;
28 return 0;
29 }

13
 Time and Space Complexity:
• Time: O(n²) for all cases
• Space: O(1)
Output:
Original array: 64 34 25 12 22
Sorted array: 12 22 25 34 64
Note: Selection sort is simple and minimizes swaps but is impractical for
large datasets. It’s not stable, as it may swap equal elements far apart.

(c) C++ Code for Insertion Sort

Insertion sort builds a sorted portion by inserting each element into its correct
position in the sorted section, shifting elements as needed.
How It Works:
1. Start with the first element as the sorted portion.
2. For each element arr[i] (i from 1 to n-1):
• Store arr[i] as key.
• Shift elements in the sorted portion (arr[0..i-1]) that are greater
than key one position right.
• Place key in its correct position.
3. Repeat until all elements are processed.
When It’s Efficient:
• Small Datasets: Low overhead and simple logic.
• Nearly Sorted Data: O(n) best-case time when the array is almost
sorted (adaptive).
• Online Sorting: Suitable for data arriving incrementally.
• Stability Required: Preserves the order of equal elements.
Limitations: O(n²) worst-case time makes it inefficient for large, unsorted
datasets.
1 # include <iostream >
2 using namespace std;
3

4 void insertionSort (int arr [], int n) {

5 for (int i = 1; i < n; i++) {
6 int key = arr[i];

14
 7 int j = i - 1;
8 while (j >= 0 && arr[j] > key) {
9 arr[j + 1] = arr[j];
10 j--;
11 }
12 arr[j + 1] = key;
13 }
14 }
15

16 int main () {
17 int arr [] = {64 , 34, 25, 12, 22};
18 int n = sizeof (arr) / sizeof (arr [0]);
19 cout << " Original ␣array :␣";
20 for (int i = 0; i < n; i++) cout << arr[i] << "␣";
21 cout << endl;
22 insertionSort (arr , n);
23 cout << " Sorted ␣ array :␣";
24 for (int i = 0; i < n; i++) cout << arr[i] << "␣";
25 cout << endl;
26 return 0;
27 }

Time and Space Complexity:

• Time: O(n²) worst/average; O(n) best

• Space: O(1)
Output:
Original array: 64 34 25 12 22
Sorted array: 12 22 25 34 64
Note: Insertion sort is stable and adaptive, making it ideal for small or
nearly sorted datasets. It’s used in hybrid algorithms like Timsort for small
subarrays.

(d) C++ Code for Bubble Sort

Bubble sort compares adjacent elements and swaps them if out of order, “bub-
bling” larger elements to the end in each pass. An optimization stops early if
no swaps occur.
How It Works:
1. For each pass i from 0 to n-2:
• Compare adjacent elements arr[j] and arr[j+1] for j from 0 to
n-i-2.

15
 • Swap if arr[j] > arr[j+1].
2. If no swaps occur in a pass, the array is sorted (optimization).
3. Repeat until no swaps are needed or n-1 passes are completed.
When It’s Efficient:
• Small Datasets: Simple to implement with low overhead.
• Nearly Sorted Data: O(n) best-case time with the swap optimization.
• Educational Use: Clear illustration of sorting concepts.
Limitations: O(n²) time complexity makes it impractical for large datasets.
It performs many swaps, which can be costly.
1 # include <iostream >
2 using namespace std;
3

4 void bubbleSort (int arr [], int n) {

5 bool swapped ;
6 for (int i = 0; i < n - 1; i++) {
7 swapped = false ;
8 for (int j = 0; j < n - i - 1; j++) {
9 if (arr[j] > arr[j + 1]) {
10 swap(arr[j], arr[j + 1]);
11 swapped = true;
12 }
13 }
14 if (! swapped ) break ; // Optimization : exit if no
swaps
15 }
16 }
17

18 int main () {
19 int arr [] = {64 , 34, 25, 12, 22};
20 int n = sizeof (arr) / sizeof (arr [0]);
21 cout << " Original ␣array :␣";
22 for (int i = 0; i < n; i++) cout << arr[i] << "␣";
23 cout << endl;
24 bubbleSort (arr , n);
25 cout << " Sorted ␣ array :␣";
26 for (int i = 0; i < n; i++) cout << arr[i] << "␣";
27 cout << endl;
28 return 0;
29 }

Time and Space Complexity:

16
 • Time: O(n²) worst/average; O(n) best
• Space: O(1)
Output:
Original array: 64 34 25 12 22
Sorted array: 12 22 25 34 64
Note: Bubble sort is stable but inefficient due to frequent swaps. The
optimization improves performance for nearly sorted data, but it’s rarely used
in practice except for teaching.

17