DSA · Question paper

CET-2 · 30 Sep 2026

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:

  1. Dynamic size: grows and shrinks at run time; no need to fix the size in advance.
  2. Easy insertion/deletion: only pointers change; no shifting of elements (O(1) at a known position).
  3. 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:

Index01234
Value10203040—

Front = 0, Rear = 3.

b) Circular queue, size 5: Enqueue 11, 22, 33, 33, Dequeue, Enqueue 44, 55, 66:

OperationArray [0..4]FrontRear
Enqueue 1111 – – – –00
Enqueue 2211 22 – – –01
Enqueue 3311 22 33 – –02
Enqueue 3311 22 33 33 –03
Dequeue (removes 11)– 22 33 33 –13
Enqueue 44– 22 33 33 4414
Enqueue 55 (wraps)55 22 33 33 4410
Enqueue 66Overflow: (0 + 1) % 5 = 1 = Front10

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.

StepOperationArray [0..4]FrontRear
1Insert 1010 – – – –00
2Insert 2010 20 – – –01
3Insert 3010 20 30 – –02
4Delete (10)– 20 30 – –12
5Insert 40– 20 30 40 –13
6Insert 50– 20 30 40 5014

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:

StepPREVPTRLINK(PTR) = NULL?
Initial510No
11015No
21520Yes, stop

Set LINK(15) ← NULL and free node 20. Result: HEAD → 5 → 10 → 15 → NULL. Time O(n).