Pre-Board Examination – Spring, 2026 — Model Answers
Course: Data Structure & Algorithm · Full Marks: 100 · Time: 3 hrs Structure: Group A (10×2=20) · Group B (any 5 × 10 = 50) · Group C (any 2 × 15 = 30)
Clean, complete answers to every question in all three groups, with algorithms, worked traces and diagrams. All numeric results are verified.
Group 'A' — Short Answer Questions (10 × 2 = 20)
1. Define best-case, average-case and worst-case complexity.
- Best case — the minimum running time for the most favourable input (lower bound of the running time).
- Average case — the expected running time taken over all possible inputs (weighted by probability).
- Worst case — the maximum running time for the least favourable input (upper bound); most commonly used for guarantees.
2. Differentiate between recursion and iteration.
| Recursion | Iteration |
|---|---|
| A function calls itself until a base case is reached. | A loop repeats a block until a condition fails. |
| Uses the call stack → more memory; risk of stack overflow. | Uses a fixed amount of memory. |
| Code is shorter and closer to the definition. | Usually faster (no call overhead). |
3. How is a stack represented using an array?
A stack is stored in a 1-D array of fixed size MAX with an integer top (initialized to −1). PUSH does top = top + 1; A[top] = x (overflow if top == MAX − 1); POP returns A[top]; top = top − 1 (underflow if top == −1). The element at A[top] is always the most recently inserted.
4. State the main limitation of a simple (linear) queue.
Once rear reaches the last index, no new element can be inserted even if the front slots are empty (a "false-full" condition), because the slots freed by dequeue cannot be reused. This wastes memory; a circular queue overcomes it.
5. What is concatenation in a linked list?
Concatenation is joining two linked lists into one by linking the next pointer of the last node of the first list to the head node of the second list (the first list's tail then points to the second list instead of NULL).
6. What is an AVL tree and balance factor?
An AVL tree is a self-balancing binary search tree in which every node's balance factor stays in {−1, 0, +1}. The balance factor of a node is BF = height(left subtree) − height(right subtree). If an insertion/deletion makes any |BF| = 2, rotations restore balance.
7. Which sorting algorithm is best for nearly-sorted data and why?
Insertion sort. It is adaptive: when data is nearly sorted, each element is already close to its final place, so very few shifts occur and it runs in nearly O(n) time (its best case), outperforming most O(n log n) sorts on such input.
8. 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. A good hash function should distribute keys uniformly across the table to minimize collisions (it should also be fast to compute and deterministic).
9. Differentiate between BFS and DFS.
| BFS | DFS |
|---|---|
| Explores level by level (nearest first). | Explores as deep as possible, then backtracks. |
| Uses a queue. | Uses a stack / recursion. |
| Finds shortest path (fewest edges) in an unweighted graph. | Used for cycle detection, topological sort, connectivity. |
10. Differentiate between Big-O and Omega notation.
- Big-O, O(f(n)) — asymptotic upper bound: time grows at most as fast as c·f(n) for large n (worst-case bound).
- Big-Omega, Ω(f(n)) — asymptotic lower bound: time grows at least as fast as c·f(n) for large n (best-case bound).
Group 'B' — Descriptive Answer Questions (attempt any FIVE; 5 × 10 = 50)
B1. Data structure + classification + asymptotic notations (5 + 5)
Data structure. A systematic way of organizing and storing data in memory so it can be accessed and modified efficiently.
Data Structure
┌───────────────┴───────────────┐
Primitive Non-Primitive
(int, float, ┌────────────────┴────────────────┐
char, pointer) Linear Non-Linear
(Array, Stack, (Tree, Graph)
Queue, Linked List)
Asymptotic notations describe how running time grows with input size n:
- Big-O, O(f(n)) — upper bound. Example: linear search is O(n); it never takes more than a constant multiple of n comparisons.
- Big-Omega, Ω(f(n)) — lower bound. Example: comparison-based sorting is Ω(n log n); it needs at least that many comparisons.
- Big-Theta, Θ(f(n)) — tight bound (both upper and lower). Example: merge sort is Θ(n log n) in all cases.
B2. Advantages/disadvantages of recursion + Tower of Hanoi moves (4 + 6)
Advantages (2): (i) shorter, cleaner code that mirrors the problem's definition; (ii) natural for self-similar problems (Tower of Hanoi, tree traversal, divide-and-conquer). Disadvantages (2): (i) extra memory for the call stack → risk of stack overflow; (ii) function-call overhead makes it slower, and naïve recursion may recompute sub-problems.
Deriving the number of moves for n disks. Let M(n) be the minimum moves. To move n disks: move top n−1 to the spare peg, move the largest, then move n−1 onto it:
M(n) = 2·M(n−1) + 1 , M(1) = 1
= 2²·M(n−2) + 2 + 1
= …
= 2^(n−1)·M(1) + (2^(n−2)+…+2+1)
= 2^(n−1) + (2^(n−1) − 1)
M(n) = 2ⁿ − 1 (e.g. 3 disks → 7 moves).
B3. Stack overflow vs underflow + infix→postfix (3 + 7)
| Overflow | Underflow |
|---|---|
PUSH onto a full stack (top = MAX − 1). |
POP from an empty stack (top = −1). |
| Happens during insertion. | Happens during deletion. |
Convert: ( A + B ) * ( C − D ) / E + F * G (precedence *,/ > +,−; left-associative)
| Symbol | Action | Stack | Postfix |
|---|---|---|---|
| ( | push | ( | |
| A | output | ( | A |
| + | push | ( + | A |
| B | output | ( + | A B |
| ) | pop to ( | A B + | |
| * | push | * | A B + |
| ( | push | * ( | A B + |
| C | output | * ( | A B + C |
| − | push | * ( − | A B + C |
| D | output | * ( − | A B + C D |
| ) | pop to ( | * | A B + C D − |
| / | pop *, 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 |
| * | push | + * | A B + C D − * E / F |
| G | output | + * | A B + C D − * E / F G |
| end | pop *, pop + | A B + C D − * E / F G * + |
Postfix: A B + C D − * E / F G * +
B4. Sorting-efficiency table + merge sort (5 + 5)
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Merge sort on 38, 27, 43, 3, 9, 82, 10 (divide, then merge):
Divide:
[38, 27, 43, 3, 9, 82, 10]
→ [38, 27, 43, 3] [9, 82, 10]
→ [38, 27] [43, 3] [9, 82] [10]
→ [38][27] [43][3] [9][82] [10]
Merge (combine in sorted order):
[27, 38] [3, 43] [9, 82] [10]
[3, 27, 38, 43] [9, 10, 82]
→ [3, 9, 10, 27, 38, 43, 82]
Sorted: 3, 9, 10, 27, 38, 43, 82
B5. Front & rear + BST traversals + circular queue (2 + 4 + 4)
Front and rear. In a queue the front points to the position from which elements are removed (dequeued); 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:
50
/ \
30 70
/ \ / \
20 40 60 80
- Preorder (Root, Left, Right):
50, 30, 20, 40, 70, 60, 80 - Postorder (Left, Right, Root):
20, 40, 30, 60, 80, 70, 50
Circular queue — insertion and deletion (capacity N):
Algorithm CQ_Insert(Q, x): Algorithm CQ_Delete(Q):
if (rear + 1) mod N == front: if front == −1:
print "Overflow"; return print "Underflow"; return
if front == −1: x ← Q[front]
front ← 0 if front == rear: // last item
rear ← (rear + 1) mod N front ← rear ← −1
Q[rear] ← x else:
front ← (front + 1) mod N
return x
The mod N wrap-around lets freed front slots be reused, so the whole array stays usable.
B6. Open-addressing collision resolution + quadratic probing (4 + 6)
Open addressing stores all entries inside the table; on collision it probes for another free slot:
- Linear probing — probe
h, h+1, h+2, … (mod m). Simple, but causes primary clustering. - Quadratic probing — probe
(h + i²) mod m, i = 0,1,2,… Reduces primary clustering (secondary clustering may remain). - Double hashing — probe
(h₁(k) + i·h₂(k)) mod musing a second hash; gives the most uniform spread.
Insert 72, 27, 36, 24, 63, 81, 92, 101 into size 10, h(k) = k mod 10, quadratic probing:
| Key | h(k) | Probe sequence (h+i²) mod 10 |
Slot |
|---|---|---|---|
| 72 | 2 | 2 | 2 |
| 27 | 7 | 7 | 7 |
| 36 | 6 | 6 | 6 |
| 24 | 4 | 4 | 4 |
| 63 | 3 | 3 | 3 |
| 81 | 1 | 1 | 1 |
| 92 | 2 | 2→3→6→1→8 (i=0..4) | 8 |
| 101 | 1 | 1→2→5 (i=0,1,2) | 5 |
Resulting hash table:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | 81 | 72 | 63 | 24 | 101 | 36 | 27 | 92 | — |
Group 'C' — Long Answer Questions (attempt any TWO; 2 × 15 = 30)
C1. 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 and place all 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 it back.
- The last remaining node is the root.
- Label every left edge 0 and every right edge 1; each symbol's code is the path from root to its leaf.
(b) What is it used for? Build the tree. (1 + 3)
Used for: lossless data compression — it assigns short codes to frequent symbols and long codes to rare ones, minimizing total bits (used in ZIP/GZIP, JPEG, MP3).
Merges (total = 100): 5+9=14; 12+13=25; 14+16=30; 25+30=55; 45+55=100.
(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 of each character. (3)
| Symbol | Freq | 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, so decoding is unambiguous.
(d) How Huffman reduces total bits. (4)
Huffman bits = 45×1 + 12×3 + 13×3 + 16×3 + 5×4 + 9×4
= 45 + 36 + 39 + 48 + 20 + 36 = 224 bits (avg 2.24 bits/symbol)
Fixed-length = 100 × 3 = 300 bits
By giving frequent symbols shorter codes, Huffman shrinks the data from 300 → 224 bits, a saving of 76 bits (≈ 25%), while the prefix property keeps decoding correct.
C2. AVL rotations + insertion / deletion / traversals
The four AVL rotations (restore balance when |BF| = 2):
LL (single Right) RR (single Left)
30 10 20
/ 20 \ 20 / \
20 ─────► / \ or 20 ───► / \ = 10 30
/ 10 30 \ 10 30
10 30
LR (Left then Right): 30 → (left-rotate 10) → (right-rotate 30) → balanced
RL (Right then Left): 10 → (right-rotate 30) → (left-rotate 10) → balanced
| Case | New node inserted in… | 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 |
Insert 50, 20, 60, 10, 8, 15, 32, 46, 11, 48. Three rotations occur:
- Insert 8 → node 20 becomes
BF = +2(LL) → right rotation at 20. - Insert 15 → node 50 becomes
BF = +2(LR) → left-rotate 10, then right-rotate 50. - Insert 48 → node 32 becomes
BF = −2(RR) → left rotation at 32.
(a) AVL tree after all insertions:
20
/ \
10 50
/ \ / \
8 15 46 60
/ / \
11 32 48
(b) Delete node 20. Node 20 has two children, so it is replaced by its inorder successor = 32 (smallest key in the right subtree); the old leaf 32 is removed. The tree remains balanced (no rotation needed):
32
/ \
10 50
/ \ / \
8 15 46 60
/ \
11 48
(c) Traversals of the final tree (after deletion):
- Inorder (L, Root, R):
8, 10, 11, 15, 32, 46, 48, 50, 60 - Preorder (Root, L, R):
32, 10, 8, 15, 11, 50, 46, 48, 60 - Postorder (L, R, Root):
8, 11, 15, 10, 48, 46, 60, 50, 32
C3. Graph — definitions + Kruskal MST + Dijkstra
Graph. A graph G = (V, E) is a collection of vertices V and edges E connecting pairs of vertices. In a weighted graph each edge carries a numeric weight.
Strongly vs weakly connected (directed graphs):
- Strongly connected — there is a directed path between every pair of vertices in both directions (e.g. A→B, B→C, C→A).
- Weakly connected — the graph is connected only if edge directions are ignored; some pairs cannot reach each other following the arrows (e.g. A→B, A→C — you cannot get from B to C).
The given graph (undirected weighted; edges from the figure):
Edge list (weight):
A–B = 2 A–C = 11 A–D = 13 B–C = 4 B–E = 3 C–D = 5
C–E = 1 C–F = 6 D–F = 7 E–F = 8 F–G = 9
Adjacency list:
A → B(2), C(11), D(13)
B → A(2), C(4), E(3)
C → A(11), B(4), D(5), E(1), F(6)
D → A(13), C(5), F(7)
E → B(3), C(1), F(8)
F → C(6), D(7), E(8), G(9)
G → F(9)
Note: the paper labels this "directed," but the figure is drawn without arrowheads and both a Minimum Spanning Tree and Kruskal's method apply to undirected graphs, so it is solved as undirected. Also, Kruskal's algorithm is edge-based and does not start from a vertex (that description fits Prim's algorithm); the correct edge-by-edge procedure is shown below.
(a) Kruskal's Algorithm → Minimum Spanning Tree.
Sort edges by weight and add each edge that does not create a cycle (7 vertices → 6 MST edges):
| Edge | Weight | Decision |
|---|---|---|
| C–E | 1 | Add |
| A–B | 2 | Add |
| B–E | 3 | Add |
| B–C | 4 | Reject (cycle) |
| C–D | 5 | Add |
| C–F | 6 | Add |
| D–F | 7 | Reject (cycle) |
| E–F | 8 | Reject (cycle) |
| F–G | 9 | Add → 6 edges, stop |
MST edges: C–E(1), A–B(2), B–E(3), C–D(5), C–F(6), F–G(9). Total minimum cost = 1 + 2 + 3 + 5 + 6 + 9 = 26.
(b) Dijkstra's Algorithm → shortest path A to F.
Repeatedly pick the unvisited vertex with the smallest tentative distance and relax its neighbours:
| Step (picked) | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| Initial | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| A (0) | 0 | 2 | 11 | 13 | ∞ | ∞ | ∞ |
| B (2) | 0 | 2 | 6 | 13 | 5 | ∞ | ∞ |
| E (5) | 0 | 2 | 6 | 13 | 5 | 13 | ∞ |
| C (6) | 0 | 2 | 6 | 11 | 5 | 12 | ∞ |
| D (11) | 0 | 2 | 6 | 11 | 5 | 12 | ∞ |
| F (12) | 0 | 2 | 6 | 11 | 5 | 12 | 21 |
| G (21) | — | — | — | — | — | 12 | 21 |
Shortest path A → F = A → B → C → F, cost = 2 + 4 + 6 = 12. (An equal-cost alternative is A → B → E → C → F = 2 + 3 + 1 + 6 = 12.)
End of model answers — Data Structure & Algorithm, Pre-Board Spring 2026.