DSA · Question paper

CET-2 · 10 Oct 2025

Data Structures & Algorithms (C2310C5) · CET-II · 10 October 2025 · 30 marks · 12:30 – 2:00 pm ITM (SLS) Baroda University · B.Tech CSE/CSN/IT/AI&DS · Semester III, Odd Semester 2025. Questions transcribed from the original paper. Solutions are written by CampusLoop; check them against your class notes.

Q1. Multiple choice questions [6]

1. In Tower of Hanoi, if there are 4 disks, the minimum number of moves required is: a) 7 · b) 8 · c) 15 · d) 16

Answer: (c) 15 = 2⁴ − 1.

2. Which of the following is true about linked lists compared to arrays? a) Linked lists use less memory · b) Random access is possible in linked lists · c) Insertions and deletions are easier in linked lists · d) Arrays are always better

Answer: (c). (Linked lists use more memory per element because of the pointer, and allow only sequential access.)

3. Time complexity to insert a node at the beginning of a singly linked list is: a) O(1) · b) O(n) · c) O(log n) · d) O(n²)

Answer: (a) O(1). Only new->next = head; head = new;.

4. Tower of Hanoi is an example of: a) Iteration · b) Dynamic programming · c) Recursion · d) Greedy method

Answer: (c) Recursion.

5. In a circular queue of size n, if front = rear + 1, then the queue is: a) Empty · b) Full · c) Overflow · d) Underflow

Answer: (b) Full. In the array implementation where front and rear both point to elements, the queue is full when (rear + 1) % n == front, i.e. front = rear + 1 (or front = 0 and rear = n − 1).

6. What does the next field in a linked list node store? a) Data · b) Address of next node · c) Size of list · d) Index number

Answer: (b) Address of the next node.

Q2. Answer any THREE out of FIVE [9]

Q2.1 Explain the Tower of Hanoi problem.

Three pegs (Source, Auxiliary, Destination) and n disks of different sizes on Source, largest at the bottom. Move all disks to Destination following three rules: move one disk at a time, only the top disk can be moved, and never place a larger disk on a smaller one.

Recursive idea: move n−1 disks Source → Auxiliary; move the largest disk Source → Destination; move n−1 disks Auxiliary → Destination.

Procedure TOH(N, SRC, AUX, DST)
1. If N = 1 then Write "Move disk 1 from", SRC, "to", DST; Return
2. Call TOH(N − 1, SRC, DST, AUX)
3. Write "Move disk", N, "from", SRC, "to", DST
4. Call TOH(N − 1, AUX, SRC, DST)
5. Return

Moves: T(n) = 2T(n−1) + 1 → 2ⁿ − 1 (3 disks: 7 moves). Time O(2ⁿ).

3-disk move list (A→C using B): A→C, A→B, C→B, A→C, B→A, B→C, A→C.

Q2.2 Difference between singly linked list and doubly linked list.

Singly linked listDoubly linked list
Node: data, nextNode: prev, data, next
Traversal in one direction onlyTraversal in both directions
Less memory per nodeOne extra pointer per node
Deleting a given node needs its predecessor (O(n) search)Delete a given node in O(1) using prev
Simpler to implementMore pointer updates on insert/delete
Used in stacks, simple listsUsed in browser history, undo/redo, deques

Q2.3 Explain circular queue with pseudocode.

A circular queue treats the array as a ring: after the last index, rear wraps to index 0, so freed slots at the front are reused (a linear queue wastes them).

Procedure CQINSERT(Q, N, FRONT, REAR, X)
1. If (REAR + 1) mod N = FRONT then Write "OVERFLOW"; Return
2. If FRONT = −1 then FRONT ← 0          [first element]
3. REAR ← (REAR + 1) mod N
4. Q[REAR] ← X
5. Return

Function CQDELETE(Q, N, FRONT, REAR)
1. If FRONT = −1 then Write "UNDERFLOW"; Return
2. Y ← Q[FRONT]
3. If FRONT = REAR then FRONT ← REAR ← −1    [queue becomes empty]
   Else FRONT ← (FRONT + 1) mod N
4. Return Y

Q2.4 Convert infix to postfix using a stack: ((A+B) * (C+D) / (E−F)) + G

Scan left to right; operands go to output; ( is pushed; on ) pop until (; an operator pops operators of higher or equal precedence first.

SymbolStackPostfix output
((
(((
A((A
+((+A
B((+AB
)(AB+
*(*AB+
((*(AB+
C(*(AB+C
+(*(+AB+C
D(*(+AB+CD
)(*AB+CD+
/(/AB+CD+*
((/(AB+CD+*
E(/(AB+CD+*E
−(/(−AB+CD+*E
F(/(−AB+CD+*EF
)(/AB+CD+*EF−
)(empty)AB+CD+*EF−/
++AB+CD+*EF−/
G+AB+CD+*EF−/G
end*AB+CD+EF−/G+

Postfix: AB+CD+*EF-/G+

Q2.5 Algorithm for PUSH and POP on a stack.

Procedure PUSH(S, TOP, N, X)
1. [Overflow?]  If TOP ≥ N − 1 then Write "STACK OVERFLOW"; Return
2. [Increment]  TOP ← TOP + 1
3. [Insert]     S[TOP] ← X
4. Return

Function POP(S, TOP)
1. [Underflow?] If TOP = −1 then Write "STACK UNDERFLOW"; Return
2. [Remove]     Y ← S[TOP]
3. [Decrement]  TOP ← TOP − 1
4. Return Y

Both run in O(1).

Q3. Answer any THREE out of FIVE [15]

Q3.1 Program to evaluate a postfix expression using a stack.

#include <stdio.h>
#include <ctype.h>

int stack[100], top = -1;
void push(int x) { stack[++top] = x; }
int pop(void)    { return stack[top--]; }

int evaluatePostfix(const char *exp) {
    for (int i = 0; exp[i] != '\0'; i++) {
        char c = exp[i];
        if (isdigit(c)) push(c - '0');          /* single-digit operands */
        else {
            int b = pop(), a = pop();           /* order matters: a op b */
            switch (c) {
                case '+': push(a + b); break;
                case '-': push(a - b); break;
                case '*': push(a * b); break;
                case '/': push(a / b); break;
            }
        }
    }
    return pop();
}

int main(void) {
    printf("%d\n", evaluatePostfix("231*+9-"));  /* 2 + 3*1 - 9 = -4 */
    return 0;
}

Idea: push operands; on an operator pop two (second popped is the left operand), apply, push the result. The final stack value is the answer.

Q3.2 Program to implement a singly linked list (insert, delete, display).

#include <stdio.h>
#include <stdlib.h>

struct node { int data; struct node *next; };
struct node *head = NULL;

void insertEnd(int x) {
    struct node *n = malloc(sizeof *n);
    n->data = x; n->next = NULL;
    if (head == NULL) { head = n; return; }
    struct node *t = head;
    while (t->next != NULL) t = t->next;
    t->next = n;
}

void deleteValue(int x) {
    struct node *t = head, *prev = NULL;
    while (t != NULL && t->data != x) { prev = t; t = t->next; }
    if (t == NULL) { printf("%d not found\n", x); return; }
    if (prev == NULL) head = t->next; else prev->next = t->next;
    free(t);
}

void display(void) {
    for (struct node *t = head; t != NULL; t = t->next) printf("%d -> ", t->data);
    printf("NULL\n");
}

int main(void) {
    insertEnd(10); insertEnd(20); insertEnd(30);
    display();            /* 10 -> 20 -> 30 -> NULL */
    deleteValue(20);
    display();            /* 10 -> 30 -> NULL */
    return 0;
}

Q3.3 Convert infix to postfix and prefix using a stack: A+(B*C−(D/E^F)*G)*H

Postfix: ABC*DEF^/G*-H*+

Key steps: B*C → BC*; E^F → EF^; D/E^F → DEF^/; (D/E^F)*G → DEF^/G*; B*C − (…) → BC*DEF^/G*-; (…)*H → BC*DEF^/G*-H*; A + (…) → ABC*DEF^/G*-H*+. (^ has the highest precedence and is right-associative.)

Prefix: +A*-*BC*/D^EFGH

Method: reverse the expression (swapping brackets), convert to postfix, then reverse the result. Check: B*C → *BC; D/E^F → /D^EF; (D/E^F)*G → */D^EFG; minus → -*BC*/D^EFG; *H → *-*BC*/D^EFGH; A+ → +A*-*BC*/D^EFGH.

Q3.4 Traversals of the given binary tree

Tree (a binary search tree): root 25; left subtree 20 → (10 → 5, 12), 22; right subtree 36 → (30 → 28), (40 → 38, 48).

  • Preorder (Root, Left, Right): 25, 20, 10, 5, 12, 22, 36, 30, 28, 40, 38, 48
  • Inorder (Left, Root, Right): 5, 10, 12, 20, 22, 25, 28, 30, 36, 38, 40, 48 (sorted, confirming it is a BST)
  • Postorder (Left, Right, Root): 5, 12, 10, 22, 20, 28, 30, 38, 48, 40, 36, 25

(One leaf under 40 is faint in the scan; it reads as 38, which fits the BST order.)

Q3.5 Algorithm to insert an element at the start and at the end of a singly linked list.

Procedure INSERT_FIRST(HEAD, X)
1. [Create node]  NEW ← AVAIL; DATA(NEW) ← X
2. [Link]         LINK(NEW) ← HEAD
3. [Update head]  HEAD ← NEW
4. Return                                   [O(1)]

Procedure INSERT_LAST(HEAD, X)
1. [Create node]  NEW ← AVAIL; DATA(NEW) ← X; LINK(NEW) ← NULL
2. [Empty list?]  If HEAD = NULL then HEAD ← NEW; Return
3. [Find last]    PTR ← HEAD
                  Repeat while LINK(PTR) ≠ NULL: PTR ← LINK(PTR)
4. [Link]         LINK(PTR) ← NEW
5. Return                                   [O(n); O(1) with a tail pointer]