Data Structures & Algorithms (C2310C5) · CET-II · Wednesday 30 September 2026 · 30 marks · 10:10 am – 12:10 pm ITM (SLS) Baroda University · B.Tech Semester III, 2026. All questions mandatory unless a choice is given; non-programmable calculator allowed. Questions transcribed from the original paper. Solutions are written by CampusLoop; check them against your class notes.
Q1. Multiple choice questions [6]
1. The five items A, B, C, D and E are pushed in a stack, one after the other starting from A. The stack is popped with four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is: a) A · b) B · c) C · d) D
Answer: (d) D.
- After pushes the stack is (bottom → top) A B C D E.
- Pop four: E, D, C, B → enqueue in that order. Queue (front → rear): E D C B. Stack: A.
- Dequeue two: E, then D → push E, push D. Stack: A E D (top D).
- Pop → D.
2. In a linear queue implemented using an array of size N (indices 0 to N−1), the queue is considered FULL when: a) front == 0 · b) rear == N − 1 · c) front == rear · d) rear == N Answer: (b) rear == N − 1.
3. In a circular queue of size N, after an insertion when rear = N − 1, the new value of rear is computed as: a) rear = rear + 1 · b) rear = (rear + 1) % N · c) rear = 0 · d) rear = N Answer: (b) (gives 0, wrapping around).
4. In a circular linked list, the next pointer of the last node points to: a) NULL · b) The first node (head) · c) Itself · d) The second last node
Answer: (b) The head.
5. Which operation is NOT permitted in an input-restricted deque? a) Insertion at rear · b) Deletion at rear · c) Deletion at front · d) Insertion at front Answer: (d) Insertion at front. An input-restricted deque allows insertion at only one end (rear) but deletion at both ends.
6. The time complexity to search for an element in a singly linked list of n nodes is: a) O(1) · b) O(log n) · c) O(n) · d) O(n log n) Answer: (c) O(n) (sequential access only).
Q2. Answer any THREE out of FIVE [9]
Q2.1 What is a queue? Explain the types of queues and their operations.
A queue is a linear data structure that follows FIFO: insertion (enqueue) at the rear, deletion (dequeue) at the front. Operations: enqueue, dequeue, peek/front, isEmpty, isFull, display, each O(1).
- Simple (linear) queue: basic FIFO; space freed at the front is not reused.
- Circular queue: rear wraps to index 0 ((rear + 1) mod N), reusing freed space.
- Priority queue: each element has a priority; the highest-priority element is removed first (ties: FIFO). Used in CPU scheduling, emergency rooms.
- Deque (double-ended queue): insert and delete at both ends. Input-restricted: insert at one end only; output-restricted: delete at one end only.
Q2.2 Pseudocode to find the number NUM of times a given ITEM occurs in a linked LIST.
Procedure COUNT_ITEM(START, ITEM)
1. [Initialise] NUM ← 0, PTR ← START
2. [Traverse] Repeat while PTR ≠ NULL
If INFO(PTR) = ITEM then NUM ← NUM + 1
PTR ← LINK(PTR)
3. [Output] Write NUM
4. Return
Time O(n). Example: LIST 4 → 7 → 4 → 9 → 4, ITEM = 4 → NUM = 3.
Q2.3 What is a linked list? Three advantages of a linked list over an array.
A linked list is a linear collection of nodes, each storing data and a pointer (link) to the next node; the last node's link is NULL and a START/HEAD pointer gives the first node. Nodes need not be contiguous in memory.
Advantages over arrays:
- Dynamic size: grows and shrinks at run time; no need to fix the size in advance.
- Easy insertion/deletion: only pointers change; no shifting of elements (O(1) at a known position).
- No wasted memory from over-allocation, and memory need not be contiguous. (Disadvantages: no random access, extra memory per node for the pointer.)
Q2.4 Linear, circular and priority queue operations
a) Linear queue, size 5, Front = Rear = −1; Enqueue 10, 20, 30, 40:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 10 | 20 | 30 | 40 | — |
Front = 0, Rear = 3.
b) Circular queue, size 5: Enqueue 11, 22, 33, 33, Dequeue, Enqueue 44, 55, 66:
| Operation | Array [0..4] | Front | Rear |
|---|---|---|---|
| Enqueue 11 | 11 – – – – | 0 | 0 |
| Enqueue 22 | 11 22 – – – | 0 | 1 |
| Enqueue 33 | 11 22 33 – – | 0 | 2 |
| Enqueue 33 | 11 22 33 33 – | 0 | 3 |
| Dequeue (removes 11) | – 22 33 33 – | 1 | 3 |
| Enqueue 44 | – 22 33 33 44 | 1 | 4 |
| Enqueue 55 (wraps) | 55 22 33 33 44 | 1 | 0 |
| Enqueue 66 | Overflow: (0 + 1) % 5 = 1 = Front | 1 | 0 |
Final queue: [55, 22, 33, 33, 44], Front = 1, Rear = 0 (order from front: 22, 33, 33, 44, 55). 66 is not inserted.
c) Priority queue (A,4), (B,2), (C,5), (D,1), (E,3), taking a smaller number = higher priority (as in Q3.2, where 1 = most critical):
- Deleted first: D (priority 1).
- Lowest priority: C (priority 5).
- After deleting the highest priority: (B,2), (E,3), (A,4), (C,5) (in priority order). (If your class convention is larger number = higher priority, the answers swap: C is deleted first and D has the lowest priority.)
Q2.5 Circular queue of size 5: Insert 10, 20, 30, Delete, Insert 40, 50
Initially Front = Rear = −1.
| Step | Operation | Array [0..4] | Front | Rear |
|---|---|---|---|---|
| 1 | Insert 10 | 10 – – – – | 0 | 0 |
| 2 | Insert 20 | 10 20 – – – | 0 | 1 |
| 3 | Insert 30 | 10 20 30 – – | 0 | 2 |
| 4 | Delete (10) | – 20 30 – – | 1 | 2 |
| 5 | Insert 40 | – 20 30 40 – | 1 | 3 |
| 6 | Insert 50 | – 20 30 40 50 | 1 | 4 |
Can one more element be inserted? Yes. The queue is full only when (Rear + 1) % 5 = Front; here (4 + 1) % 5 = 0 ≠ 1. Index 0 (freed by the delete) is empty, so the next insert goes there and Rear becomes 0. (A linear queue would report overflow here because Rear = N − 1.)
Q3. Answer any THREE out of FIVE [15]
Q3.1 ENQUEUE and DEQUEUE for a circular queue of size N; why it is more memory-efficient.
Procedure CQ_ENQUEUE(Q, N, FRONT, REAR, X)
1. If (REAR + 1) mod N = FRONT then Write "OVERFLOW"; Return
2. If FRONT = −1 then FRONT ← 0 [queue was empty]
3. REAR ← (REAR + 1) mod N
4. Q[REAR] ← X
5. Return
Function CQ_DEQUEUE(Q, N, FRONT, REAR)
1. If FRONT = −1 then Write "UNDERFLOW"; Return
2. Y ← Q[FRONT]
3. If FRONT = REAR then FRONT ← −1, REAR ← −1 [queue becomes empty]
Else FRONT ← (FRONT + 1) mod N
4. Return Y
Why more memory-efficient: in a linear queue, once REAR reaches N − 1 no more insertions are possible even if elements were deleted from the front, so those slots are wasted. A circular queue wraps REAR (and FRONT) around with mod N, reusing every freed slot, so all N positions are usable (see Q2.5).
Q3.2 Hospital priority queue: P1(2), P2(5), P3(1), P4(3), P5(1), priority 1 = most critical.
a) Order of treatment: sort by priority; equal priorities in arrival order (FIFO): P3 (1) → P5 (1) → P1 (2) → P4 (3) → P2 (5).
b) Pseudocode: insert into an array-based priority queue kept sorted (most critical at the front):
Procedure PQ_INSERT(PQ, N, COUNT, NAME, PRI)
1. If COUNT = N then Write "OVERFLOW"; Return
2. I ← COUNT − 1
3. [Shift less-critical patients right]
Repeat while I ≥ 0 and PQ[I].PRI > PRI
PQ[I + 1] ← PQ[I]
I ← I − 1
4. PQ[I + 1] ← (NAME, PRI) [after equal priorities: keeps FIFO order]
5. COUNT ← COUNT + 1
6. Return
Deletion then simply removes PQ[0] (the most critical). Insert O(n), delete O(1) with front index (or O(n) if shifting).
Q3.3 Diagram of a singly linked list 10, 20, 30, 40; insert 25 between positions 2 and 3.
Before: HEAD → [10|•] → [20|•] → [30|•] → [40|NULL]
After: HEAD → [10|•] → [20|•] → [25|•] → [30|•] → [40|NULL]
Procedure INSERT_AFTER_POS(HEAD, POS, X) [POS = 2: insert after the 2nd node]
1. NEW ← new node; DATA(NEW) ← X
2. PTR ← HEAD
3. Repeat for I = 1 to POS − 1 [move to the POS-th node]
If PTR = NULL then Write "Invalid position"; Return
PTR ← LINK(PTR)
4. LINK(NEW) ← LINK(PTR) [25 → 30]
5. LINK(PTR) ← NEW [20 → 25]
6. Return
Order matters: set NEW's link first, otherwise the rest of the list (30 → 40) is lost.
Q3.4 Insert a new node at the END of a singly circular linked list; how traversal terminates.
Procedure CLL_INSERT_END(LAST, X) [LAST points to the last node; LINK(LAST) is the head]
1. NEW ← new node; DATA(NEW) ← X
2. If LAST = NULL then [empty list]
LINK(NEW) ← NEW; LAST ← NEW; Return
3. LINK(NEW) ← LINK(LAST) [new node points to head]
4. LINK(LAST) ← NEW [old last node points to new node]
5. LAST ← NEW [new node becomes last]
6. Return
Traversal termination: there is no NULL, so start at the head and stop when you come back to the head:
PTR ← HEAD
Repeat
Write DATA(PTR); PTR ← LINK(PTR)
Until PTR = HEAD
(A do-while loop is used so the head itself is processed once.)
Q3.5 Delete the last node from HEAD → 5 → 10 → 15 → 20 → NULL; trace.
Procedure DELETE_LAST(HEAD)
1. If HEAD = NULL then Write "UNDERFLOW"; Return
2. If LINK(HEAD) = NULL then Free(HEAD); HEAD ← NULL; Return [single node]
3. PREV ← HEAD; PTR ← LINK(HEAD)
4. Repeat while LINK(PTR) ≠ NULL
PREV ← PTR; PTR ← LINK(PTR)
5. LINK(PREV) ← NULL
6. Free(PTR)
7. Return
Trace:
| Step | PREV | PTR | LINK(PTR) = NULL? |
|---|---|---|---|
| Initial | 5 | 10 | No |
| 1 | 10 | 15 | No |
| 2 | 15 | 20 | Yes, stop |
Set LINK(15) ← NULL and free node 20. Result: HEAD → 5 → 10 → 15 → NULL. Time O(n).