✅ Q.1 (a) What is DS?
Explain data
structure and its types. (03)
Data Structure (DS)
A data structure is a way of storing and organizing data so that we can use it easily.
Types of Data Structures
1. Primitive – Basic data types
o int, float, char
2. Non-Primitive – Complex structures, used to store a group of values
o Linear – elements arranged one after another
Array, Linked List, Stack, Queue
o Non-Linear – data arranged in branches
Tree, Graph
✅ Q.1 (b) Tower of Hanoi (04)
Tower of Hanoi is a puzzle with 3 rods and N disks.
Rules
1. Move one disk at a time.
2. Big disk cannot be placed on a small disk.
3. Use the 3rd rod as a helper.
Example for 3 disks
Steps:
1. Move disk 1 → Rod C
2. Move disk 2 → Rod B
3. Move disk 1 → Rod B
4. Move disk 3 → Rod C
5. Move disk 1 → Rod A
6. Move disk 2 → Rod C
7. Move disk 1 → Rod C
Total moves = 2³ − 1 = 7 moves
✅ Q.1 (c) Algorithm for Insert & Delete in
Queue (07)
Insert (Enqueue)
1. If rear == MAX-1 → Queue full
2. Else
3. rear = rear + 1
4. queue[rear] = value
5. End
Delete (Dequeue)
1. If front > rear → Queue empty
2. Else
3. value = queue[front]
4. front = front + 1
5. End
✅ Q.2 (a) Construct Binary Tree using
Preorder & Postorder (03)
Preorder: 1,2,4,5,3,6,8,9,7
Postorder: 4,5,2,8,9,6,7,3,1
Simple Explanation:
First element of preorder = root = 1
Last element of postorder = root = 1 (matches)
Preorder left subtree starts from 2, and postorder left subtree ends at 2.
Left subtree =
2
/ \
4 5
Right subtree =
Root of right subtree = 3 (from preorder after left subtree)
Right subtree structure becomes:
3
/ \
6 7
/ \
8 9
Final Tree:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
✅ Q.2 (b) Construct AVL Tree by inserting 1
to 8 (04)
Insert numbers 1 to 8 one by one.
After inserting all:
4
/ \
2 6
/ \ / \
1 3 5 7
\
8
Tree stays balanced automatically.
✅ Q.2 (c) What is Stack? Explain operations
(07)
Stack
A stack is a LIFO (Last In, First Out) data structure.
Last item inserted comes out first.
Operations:
1. Push – Add an item
2. Pop – Remove top item
3. Peek/Top – Show top item
4. isEmpty – Check if empty
5. isFull – Check if full
Example:
Push 10 → Push 20 → Pop → removes 20.
✅ Q.3 (a) Explain 2-3 Tree (03)
2-3 tree is a balanced search tree where:
Every node has 2 or 3 children
Every internal node has 1 or 2 keys
All leaf nodes are at same level
Used for fast searching.
✅ Q.3 (b) Explain three hashing techniques
(04)
1. Division Method:
key % table_size
Example: 35 % 10 = 5
2. Mid-square Method:
Square the key
Take middle digits
Example:
Key = 12 → 144 → take middle = 4
3. Folding Method:
Split number into parts and add.
Example:
Key = 123456 → 12 + 34 + 56 = 102
✅ Q.3 (c) Problem with Simple Queue +
Solution (07)
Problem:
In simple queue, front moves forward permanently, so even if space becomes empty, it cannot
be reused.
Solution: Circular Queue
Here, after last position, queue goes to first position like a circle.
Algorithms
Insert:
1. If (front == 0 AND rear == MAX-1) OR (rear+1 == front)
Queue full
2. Else
rear = (rear+1) % MAX
queue[rear] = value
Delete:
1. If front == -1 → empty
2. Else
value = queue[front]
front = (front+1) % MAX
✅ Q.4 (a) Asymptotic Notations (03)
1. Big O – Worst case
2. Omega (Ω) – Best case
3. Theta (Θ) – Average case
Example: Searching in array = O(n)
✅ Q.4 (b) Linked List Applications (04)
1. Undo/Redo in editors
2. Music playlist
3. Image sliders
4. Dynamic memory allocation
5. Graph representation
✅ Q.4 (c) Doubly Linked List + Algorithms
(07)
DLL
Each node has 3 parts:
prev pointer
data
next pointer
Can move both ways.
Insert at beginning
1. Create new node
2. new->next = head
3. head->prev = new
4. head = new
Delete from beginning
1. temp = head
2. head = head->next
3. head->prev = NULL
4. free(temp)
✅ Q.5 (a) malloc & free (03)
malloc()
Used to allocate memory at runtime.
Example:
ptr = malloc(10 * sizeof(int));
free()
Releases memory back to system.
free(ptr);
✅ Q.5 (b) Define (04)
1. Sibling: Nodes with same parent
2. Forest: Collection of many trees
3. Complete Binary Tree: All levels filled except last
4. Complete Graph: Every node is connected to every other node
✅ Q.5 (c) Explain (07)
(i) Recursion
Function calling itself again and again.
(ii) Non-primitive data structures
Complex types → array, list, stack, queue, tree.
(iii) Hashing
Convert key into small number (hash).
(iv) Non-linear data structures
Not in sequence. Example: Tree, Graph.
(v) Sparse Matrix
Matrix with many zeros.
(vi) Priority Queue
Queue where highest priority item is removed first.
(vii) Collision
When two keys get same hash address.