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 list | Doubly linked list |
|---|---|
Node: data, next | Node: prev, data, next |
| Traversal in one direction only | Traversal in both directions |
| Less memory per node | One 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 implement | More pointer updates on insert/delete |
| Used in stacks, simple lists | Used 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.
| Symbol | Stack | Postfix 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]