Pre-Board Examination – Spring, 2026 — Model Answers
Course: Data Structure & Algorithm · Program: BCSIT · Semester: II Full Marks: 100 · Pass Marks: 50 · Time: 3 hrs
These model answers cover every question in Groups A, B and C. Diagrams, traces and derivations are shown step by step.
Group 'A' — Short Answer Questions (10 × 2 = 20)
1. Define a data structure and classify it with a suitable diagram.
A data structure is a systematic way of organizing, storing and managing data in memory so that it can be accessed and modified efficiently. Data structures are classified as follows:
Data Structure
┌───────────────┴───────────────┐
Primitive Non-Primitive
(int, float, ┌────────────────┴────────────────┐
char, pointer) Linear Non-Linear
(Array, Stack, (Tree, Graph)
Queue, Linked List)
2. What is tail recursion? Give one example.
A recursive call is a tail recursion when the recursive call is the last statement executed by the function, so nothing remains to be computed after it returns.
void countDown(int n){
if (n == 0) return;
print(n);
countDown(n - 1); // last operation → tail recursive
}
3. Differentiate between overflow and underflow in a stack.
| Overflow | Underflow |
|---|---|
| Trying to PUSH onto a full stack (top = MAX − 1). | Trying to POP from an empty stack (top = −1). |
| Occurs during insertion. | Occurs during deletion. |
4. State two limitations of a simple (linear) queue.
- When
rearreaches the last index, no new element can be inserted even if front slots are empty (a "false-full" condition). - Slots freed by dequeue at the front cannot be reused, causing memory wastage. (Both are solved by the circular queue.)
5. In which situation would you prefer a linked list over an array? Give a real-life example.
Prefer a linked list when the number of elements is unknown or changes frequently and when frequent insertions/deletions in the middle are required — a linked list grows dynamically and needs no shifting of elements. Real-life example: a music playlist, where songs can be added or removed at any position.
6. Define a complete binary tree with an example.
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
A
/ \
B C
/ \ /
D E F ← last level filled from the left
7. Differentiate between internal and external sorting.
| Internal Sorting | External Sorting |
|---|---|
| All data fits in main memory (RAM). | Data is too large for memory; uses disk/tape. |
| e.g., Quick Sort, Insertion Sort. | e.g., External Merge Sort. |
8. State the precondition for applying binary search and its time complexity.
Precondition: the array/list must be sorted. Time complexity: O(log n) in the average and worst case; O(1) in the best case.
9. Define a hash function and state one characteristic of a good hash function.
A hash function h maps a key to an index in a hash table: h(key) → index.
Characteristic of a good hash function: it should distribute keys uniformly across the table to minimize collisions (it should also be fast to compute and deterministic).
10. Differentiate between a spanning tree and a minimum spanning tree.
| Spanning Tree | Minimum Spanning Tree (MST) |
|---|---|
| A cycle-free subgraph connecting all n vertices with n − 1 edges. | The spanning tree with the least total edge weight. |
| A graph may have many spanning trees. | It is the optimal (minimum-cost) one. |
Group 'B' — Descriptive Answer Questions (attempt any FIVE; 5 × 10 = 50)
B1. Best/average/worst-case complexity + largest-element algorithm (3 + 7)
Definitions.
- Best case — the minimum running time for the most favourable input (lower bound).
- Worst case — the maximum running time for the least favourable input (upper bound); used most often.
- Average case — the expected running time over all possible inputs (weighted by probability).
Algorithm — find the largest element of an array.
Algorithm FIND_MAX(A, n)
max ← A[0]
for i ← 1 to n − 1 do
if A[i] > max then
max ← A[i]
return max
Analysis. The loop runs n − 1 times and performs one comparison each iteration, so the number of comparisons is n − 1. Every element must be inspected regardless of input, therefore:
- Best = Average = Worst = O(n) (time)
- Auxiliary space = O(1)
B2. Advantages/disadvantages of recursion + Tower of Hanoi moves (4 + 6)
Advantages (2). (i) Code is shorter, cleaner and mirrors the mathematical/problem definition. (ii) Naturally suited to problems with self-similar structure (Tower of Hanoi, tree traversal, divide-and-conquer).
Disadvantages (2). (i) Extra memory for the function-call stack, risking stack overflow. (ii) Overhead of repeated calls makes it slower, and naïve recursion may recompute sub-problems.
Deriving the number of moves for n disks.
Let M(n) = minimum moves for n disks. To move n disks we move the top n−1 to the spare peg, move the largest disk, then move the n−1 disks onto it:
M(n) = 2·M(n − 1) + 1 , M(1) = 1
Expanding (back-substitution):
M(n) = 2·M(n−1) + 1
= 2²·M(n−2) + 2 + 1
= 2³·M(n−3) + 2² + 2 + 1
= …
= 2^(n−1)·M(1) + (2^(n−2) + … + 2 + 1)
= 2^(n−1) + (2^(n−1) − 1)
M(n) = 2ⁿ − 1. (For example, 3 disks → 2³ − 1 = 7 moves.)
B3. Define stack + infix→postfix conversion (3 + 7)
Stack. A stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle: the element inserted last is removed first. All operations happen at one end called TOP — PUSH (insert) and POP (remove).
Convert: A + B * C − ( D / E + F ) − G * H
Precedence: * , / (higher) > + , − (lower); left-to-right associative.
| Symbol | Action | Operator Stack | Postfix Output |
|---|---|---|---|
| A | operand → output | A | |
| + | push | + | A |
| B | output | + | A B |
| * | prec(*) > prec(+) → push | + * | A B |
| C | output | + * | A B C |
| − | pop *, pop + then push − | − | A B C * + |
| ( | push | − ( | A B C * + |
| D | output | − ( | A B C * + D |
| / | push | − ( / | A B C * + D |
| E | output | − ( / | A B C * + D E |
| + | pop /, push + | − ( + | A B C * + D E / |
| F | output | − ( + | A B C * + D E / F |
| ) | pop + up to ( , discard ( | − | A B C * + D E / F + |
| − | pop − (equal prec), push − | − | A B C * + D E / F + − |
| G | output | − | A B C * + D E / F + − G |
| * | prec(*) > prec(−) → push | − * | A B C * + D E / F + − G |
| H | output | − * | A B C * + D E / F + − G H |
| end | pop *, pop − | A B C * + D E / F + − G H * − |
Postfix: A B C * + D E / F + − G H * −
B4. Front & rear + BST traversals + AVL rotations (2 + 2 + 4 + 2)
Front and rear. In a queue the front points to the position from which elements are removed (dequeued), and the rear points to the position at which elements are inserted (enqueued). A queue is FIFO.
BST from 50, 30, 70, 20, 40, 60, 80 (insert left if smaller, right if larger):
50
/ \
30 70
/ \ / \
20 40 60 80
Traversals.
- Preorder (Root, Left, Right):
50, 30, 20, 40, 70, 60, 80 - Inorder (Left, Root, Right):
20, 30, 40, 50, 60, 70, 80(always sorted for a BST) - Postorder (Left, Right, Root):
20, 40, 30, 60, 80, 70, 50
AVL tree and its four rotations.
An AVL tree (Adelson-Velsky and Landis) is a self-balancing binary search tree in which, for every node, the balance factor
BF = height(left subtree) − height(right subtree)
is always −1, 0, or +1. When an insertion breaks this rule, the tree is rebalanced with one of four rotations, chosen by where the new node was inserted relative to the unbalanced node:
| Case | Where inserted | Fix |
|---|---|---|
| LL | left subtree of left child | single Right rotation |
| RR | right subtree of right child | single Left rotation |
| LR | right subtree of left child | Left then Right rotation |
| RL | left subtree of right child | Right then Left rotation |
LL — single right rotation (insert 30, 20, 10):
30 (bf=+2) 20
/ right / \
20 ───────► 10 30
/ rotation
10
RR — single left rotation (insert 10, 20, 30):
10 (bf=−2) 20
\ left / \
20 ───────► 10 30
\ rotation
30
LR — left rotation then right rotation (insert 30, 10, 20):
30 30 20
/ left / right / \
10 ─────► 20 ─────► 10 30
\ on 10 / on 30
20 10
RL — right rotation then left rotation (insert 10, 30, 20):
10 10 20
\ right \ left / \
30 ─────► 20 ─────► 10 30
/ on 30 \ on 10
20 30
In every case the result is a balanced tree with all balance factors in {−1, 0, +1}.
B5. BFS & DFS + Quick Sort trace (5 + 5)
BFS (Breadth-First Search) — explores level by level using a queue.
BFS(G, s):
mark all vertices unvisited
enqueue(s); mark s visited
while queue not empty:
v ← dequeue()
visit v
for each unvisited neighbour w of v:
mark w visited; enqueue(w)
DFS (Depth-First Search) — explores as deep as possible first, using a stack (or recursion).
DFS(G, v):
mark v visited; visit v
for each unvisited neighbour w of v:
DFS(G, w)
Example — for the graph A–B, A–C, B–D, C–D starting at A: BFS → A, B, C, D; DFS → A, B, D, C.
Quick Sort on 44, 33, 11, 55, 77, 90, 40, 60, 99, 22 (pivot = last element; bold = pivot placed in final position):
Start : 44 33 11 55 77 90 40 60 99 22
pivot 22 → [11] **22** 44 55 77 90 40 60 99 33
pivot 33 → 11 22 **33** 55 77 90 40 60 99 44
pivot 44 → 11 22 33 [40] **44** 90 55 60 99 77
pivot 77 → 11 22 33 40 44 [55 60] **77** [99 90]
pivot 60 → 11 22 33 40 44 55 **60** 77 99 90
pivot 90 → 11 22 33 40 44 55 60 77 **90** 99
Sorted: 11 22 33 40 44 55 60 77 90 99
B6. Probing techniques + linear-probing insertion (3 + 7)
Collision-resolution by open addressing.
- Linear probing: on collision, try the next slots in order
h(k), h(k)+1, h(k)+2, … (mod m). Simple but causes primary clustering. - Quadratic probing: try
h(k)+1², h(k)+2², h(k)+3², … (mod m). Reduces primary clustering (may cause secondary clustering). - Double hashing: use a second hash function
h₂; probe(h₁(k) + i·h₂(k)) mod m, i = 0,1,2,… Gives the most uniform spread.
Insert 72, 27, 36, 24, 63, 81, 92, 101 into a table of size 10, h(k) = k mod 10, linear probing.
| Key | h(k) | Probes | Final index |
|---|---|---|---|
| 72 | 2 | slot 2 free | 2 |
| 27 | 7 | slot 7 free | 7 |
| 36 | 6 | slot 6 free | 6 |
| 24 | 4 | slot 4 free | 4 |
| 63 | 3 | slot 3 free | 3 |
| 81 | 1 | slot 1 free | 1 |
| 92 | 2 | 2→3→4→5 (3 collisions) | 5 |
| 101 | 1 | 1→2→3→4→5→6→7→8 (7 collisions) | 8 |
Resulting hash table:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | 81 | 72 | 63 | 24 | 92 | 36 | 27 | 101 | — |
The long probe sequence for 101 shows the primary-clustering weakness of linear probing.
Group 'C' — Long Answer Questions (attempt any TWO; 2 × 15 = 30)
C1. Ride-hailing weighted graph
The road network has the following weighted edges: A–B (4), A–C (3), B–C (1), B–D (2), C–D (4), C–E (5), D–E (7), D–F (5), E–F (6).
(a) Adjacency matrix and adjacency list. (4)
Adjacency matrix (0 on diagonal, ∞ = no direct road):
A B C D E F
A [ 0 4 3 ∞ ∞ ∞ ]
B [ 4 0 1 2 ∞ ∞ ]
C [ 3 1 0 4 5 ∞ ]
D [ ∞ 2 4 0 7 5 ]
E [ ∞ ∞ 5 7 0 6 ]
F [ ∞ ∞ ∞ 5 6 0 ]
Adjacency list:
A → B(4) → C(3)
B → A(4) → C(1) → D(2)
C → A(3) → B(1) → D(4) → E(5)
D → B(2) → C(4) → E(7) → F(5)
E → C(5) → D(7) → F(6)
F → D(5) → E(6)
(b) Dijkstra's algorithm — shortest path A → F. (4)
Starting from A, repeatedly pick the unvisited vertex with the smallest tentative distance and relax its neighbours:
| Step (vertex picked) | A | B | C | D | E | F | Visited |
|---|---|---|---|---|---|---|---|
| Initial | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | — |
| A (0) | 0 | 4 | 3 | ∞ | ∞ | ∞ | A |
| C (3) | 0 | 4 | 3 | 7 | 8 | ∞ | A, C |
| B (4) | 0 | 4 | 3 | 6 | 8 | ∞ | A, C, B |
| D (6) | 0 | 4 | 3 | 6 | 8 | 11 | A, C, B, D |
| E (8) | 0 | 4 | 3 | 6 | 8 | 11 | A, C, B, D, E |
| F (11) | — | — | — | — | — | 11 | all |
Shortest path: A → B → D → F, cost = 4 + 2 + 5 = 11 minutes.
(c) Minimum Spanning Tree by Kruskal's algorithm. (4)
Sort edges by weight and add each edge unless it forms a cycle:
| Edge | Weight | Decision |
|---|---|---|
| B–C | 1 | Add |
| B–D | 2 | Add |
| A–C | 3 | Add |
| A–B | 4 | Reject (cycle) |
| C–D | 4 | Reject (cycle) |
| C–E | 5 | Add |
| D–F | 5 | Add → all 6 vertices connected, stop |
MST edges: B–C, B–D, A–C, C–E, D–F. Total cost = 1 + 2 + 3 + 5 + 5 = 16.
(d) Why MST, not the shortest-path tree, for least-cost maintenance. (3)
The MST minimizes the total weight of all edges needed to keep every location connected — exactly the goal of a least-cost maintenance network. A shortest-path tree only minimizes the distance from one source to each vertex; it is source-dependent and can include heavier edges, giving a larger total cost. Because maintenance cost depends on the whole network's total edge weight (not distance from a single origin), the MST is the correct choice.
C2. Huffman coding — A=5, B=9, C=12, D=13, E=16, F=45
(a) Steps of the Huffman algorithm. (4)
- Create a leaf node for every symbol with its frequency; place all nodes in a min-priority queue.
- While more than one node remains: remove the two smallest-frequency nodes, make them children of a new internal node whose frequency is their sum, and insert that node back.
- The last remaining node is the root.
- Label every left edge 0 and every right edge 1; a symbol's code is the sequence of labels on the path from the root to its leaf.
(b) What is Huffman coding used for? Build the Huffman tree. (1 + 3)
What it is used for: Huffman coding is a lossless data-compression technique. It assigns variable-length prefix codes to symbols according to frequency — frequent symbols get shorter codes — so the total number of bits needed to store/transmit the data is minimized. It is used in file compressors (ZIP, GZIP), image formats (JPEG) and multimedia codecs (MP3, MPEG).
Building the tree — successive merges of the two smallest frequencies:
{5, 9, 12, 13, 16, 45} → merge 5+9 = 14
{12, 13, 14, 16, 45} → merge 12+13 = 25
{14, 16, 25, 45} → merge 14+16 = 30
{25, 30, 45} → merge 25+30 = 55
{45, 55} → merge 45+55 = 100 (root)
(100)
0 / \ 1
F:45 (55)
0/ \1
(25) (30)
0/ \1 0/ \1
C:12 D:13 (14) E:16
0/ \1
A:5 B:9
(c) Huffman code for each character. (3)
| Symbol | Frequency | Code | Length |
|---|---|---|---|
| F | 45 | 0 |
1 |
| C | 12 | 100 |
3 |
| D | 13 | 101 |
3 |
| E | 16 | 111 |
3 |
| A | 5 | 1100 |
4 |
| B | 9 | 1101 |
4 |
All codes are prefix-free (no code is a prefix of another), so decoding is unambiguous.
(d) How Huffman coding reduces total bits. (4)
- Fixed-length coding: 6 symbols need 3 bits each → 100 characters × 3 = 300 bits.
- Huffman coding (frequency × code length):
A: 5×4=20 B: 9×4=36 C: 12×3=36
D: 13×3=39 E: 16×3=48 F: 45×1=45
Total = 224 bits (average 2.24 bits/symbol)
Huffman gives frequent symbols shorter codes (F → 1 bit) and rare symbols longer codes (A, B → 4 bits), so the weighted total shrinks from 300 to 224 bits — a saving of 76 bits (≈ 25%) — while the prefix property keeps decoding correct.
C3. Printer job queue
(a) Queue type for an ordinary shared printer. (3)
A simple (linear) FIFO queue. Print jobs should be serviced in the order received — the first job submitted is the first printed — which is exactly First-In-First-Out behaviour and guarantees fairness among users.
(b) If urgent documents must print first. (3)
A priority queue is needed. Each job is given a priority; higher-priority (urgent) jobs are dequeued before lower-priority ones, while jobs of equal priority still keep their arrival (FIFO) order.
(c) How a circular queue uses buffer memory efficiently. (3)
In a linear queue the slots freed at the front after printing cannot be reused, so the fixed print buffer fills up "falsely." A circular queue wraps rear (and front) around to index 0 using modulo arithmetic (rear = (rear + 1) mod size). Freed front slots are therefore reused, the whole buffer stays available, and no element shifting is required — maximizing use of the limited buffer memory.
(d) Two other operating-system uses of queues. (3)
- CPU / process scheduling — the ready queue of processes waiting for the CPU.
- I/O buffering and spooling — e.g., disk-request queues and keyboard input buffers. (Also acceptable: interrupt handling.)
(e) Double-ended queue + queue using two stacks. (1 + 2)
Double-ended queue (deque): a linear data structure in which insertion and deletion can be done at both ends — the front and the rear. Its restricted forms are the input-restricted deque (insertion only at one end) and the output-restricted deque (deletion only at one end).
Implementing a queue with two stacks — use S1 for enqueue and S2 for dequeue. Reversing elements from S1 into S2 turns LIFO order into FIFO order:
Algorithm ENQUEUE(x):
push(S1, x)
Algorithm DEQUEUE():
if S2 is empty then
if S1 is empty then
return "Queue Underflow"
while S1 is not empty do
push(S2, pop(S1)) // reverse order → FIFO
return pop(S2)
Enqueue is O(1); each element is moved between stacks at most once, so dequeue is amortized O(1).
End of model answers — Data Structure & Algorithm, Pre-Board Spring 2026.