IGNOU MCS-021 Long Answer Questions and Theoretical Explanations (Exam Style)

Q1. Explain Depth First Search (DFS) with an example. Write its algorithm and
applications.

Answer: Depth First Search (DFS) is a fundamental graph traversal algorithm that explores as far as
possible along each branch before backtracking. It uses a stack data structure, either explicitly or via system
recursion. DFS helps in exploring all vertices and edges of a graph and is commonly used in pathfinding,
cycle detection, and topological sorting.

Algorithm:

void DFS(int v, int visited[], int graph[5][5]) {

visited[v] = 1;
printf("%c ", v + 'A');
for (int i = 0; i < 5; i++) {
if (graph[v][i] == 1 && !visited[i]) {
DFS(i, visited, graph);
}
}
}

Example Graph:

A
/ \
B C
\ \
D E

Traversal starting from A: A → B → D → C → E

Applications:

• Cycle detection
• Topological sorting
• Maze solving
• Graph component analysis

1
Q2. What is Prim’s Algorithm? How does it work? Explain with example.

Answer: Prim’s Algorithm is a greedy technique used to find the Minimum Cost Spanning Tree (MST) in a
connected, undirected graph. It starts from any node and repeatedly adds the least-weight edge that
connects a new node to the already-formed tree without creating a cycle.

Steps:

1. Choose any starting vertex.

2. Select the edge with the smallest weight that connects a visited and unvisited vertex.
3. Repeat until all vertices are included in MST.

Example Graph:

A --1-- B
| /
4 3
| /
C

MST Path: A-B (1), B-C (3) → Total Cost = 4

Applications:

• Network routing
• Circuit design
• Road networks

Q3. What is an AVL Tree? How is it balanced? Explain with rotations and example.

Answer: AVL Tree is a type of self-balancing binary search tree. In an AVL tree, the height difference
(balance factor) between left and right subtree for every node is at most 1. When imbalance occurs due to
insertion or deletion, rotations are applied to restore balance.

Rotations in AVL Trees:

• Left Rotation (RR Imbalance)

• Right Rotation (LL Imbalance)
• Left-Right (LR Imbalance)
• Right-Left (RL Imbalance)

Example: Insertions 10, 20, 30 → RR Imbalance After Left Rotation:

2
 20
/ \
10 30

Applications:

• Databases
• File systems

Q4. Define Red-Black Tree. What are its properties? Where is it used?

Answer: A Red-Black Tree is a balanced binary search tree where each node contains an extra bit for color
(red or black) to ensure the tree remains balanced during insertions and deletions.

Properties:

• Every node is either red or black.

• The root is always black.
• Red nodes cannot have red children.
• Every path from a node to descendant NULL nodes must have the same number of black nodes.

Use Cases:

• Java TreeMap & TreeSet

• Linux kernel (process management)
• Associative containers in C++ STL

Q5. Differentiate between File Organization Methods with examples.

Answer: Sequential File Organization:

• Records stored one after the other.

• Easy to implement.
• Suitable for batch processing.
• Example: Attendance records stored day-wise.

Indexed Sequential File Organization:

• Index helps to quickly access data blocks.

• Balanced between speed and simplicity.
• Example: Library catalogue.

3
Direct Access File Organization:

• Uses hashing to compute block location.

• Best for quick search and updates.
• Example: Bank account number access.

Q6. Explain Binary Search. How does it work? Write algorithm and complexity.

Answer: Binary search is an efficient algorithm for finding a target value within a sorted array. It divides the
search interval in half each time and reduces the problem size logarithmically.

Steps:

1. Compare target with mid element.

2. If equal → found.
3. If smaller → search left subarray.
4. If greater → search right subarray.

Algorithm:

int binarySearch(int arr[], int l, int r, int x) {

while (l <= r) {
int mid = l + (r - l)/2;
if (arr[mid] == x) return mid;
else if (arr[mid] > x) r = mid - 1;
else l = mid + 1;
}
return -1;
}

Complexity: O(log n)

Q7. What is Hashing? Explain with advantages and applications.

Answer: Hashing is a technique used for fast data retrieval using a key. A hash function converts the key
into an index in a hash table.

Advantages:

• Fast access
• Efficient memory usage

4
Collision Handling:

• Linear Probing
• Separate Chaining

Applications:

• Symbol tables in compilers

• Password storage systems
• Indexing in databases

Q8. Explain Tree Traversals. Give Preorder and Postorder of a Binary Tree with
example.

Answer: Tree traversal is the process of visiting all the nodes in a binary tree. The common types are:

• Preorder Traversal: Visit Root → Left Subtree → Right Subtree

• Postorder Traversal: Visit Left Subtree → Right Subtree → Root

Example Tree:

A
/ \
B C
/ \
D E

Preorder: A, B, D, E, C\ Postorder: D, E, B, C, A

Applications:

• Preorder: Used to create a copy of the tree

• Postorder: Used to delete the tree

Q9. Explain Kruskal’s Algorithm with steps and example.

Answer: Kruskal’s Algorithm is a Minimum Spanning Tree algorithm that adds the next lowest-weight edge
that doesn’t form a cycle, using Disjoint Set Union for cycle detection.

Steps:

1. Sort all edges in ascending order of weight.

2. Pick the smallest edge. Check if it forms a cycle.

5
 3. If not, include it. Repeat until (V-1) edges are added.

Example Edges: AB(1), BC(3), AC(4)

MST: AB and BC → Total Cost = 4

Applications:

• Network design
• Minimum wiring/cabling paths

Q10. Write Stack Operations using Linked List. Explain PUSH, POP, and isEmpty.

Answer: A stack is a linear data structure that follows Last In First Out (LIFO) order.

Operations:

• PUSH: Insert at beginning

• POP: Remove from beginning
• isEmpty: Check if stack is empty

C-like Code:

struct Node {
int data;
struct Node* next;
};

void push(struct Node** top, int x) {

struct Node* temp = malloc(sizeof(struct Node));
temp->data = x;
temp->next = *top;
*top = temp;
}

int pop(struct Node** top) {

if (*top == NULL) return -1;
int val = (*top)->data;
*top = (*top)->next;
return val;
}

int isEmpty(struct Node* top) {

return top == NULL;
}

6
Q11. What is Circular Queue? Write algorithm for insertion and deletion.

Answer: Circular queue is a linear data structure in which the last position is connected back to the first
position to make a circle.

Operations:

• Enqueue (Insert): Add element at rear

• Dequeue (Delete): Remove element from front

Algorithm Highlights:

• Use modulo operator to wrap around

• Handle full and empty conditions using front and rear pointers

Applications:

• CPU Scheduling
• Memory management in OS

Q12. Represent a Polynomial using Linked List and perform addition.

Answer: Polynomials can be represented using a linked list where each node contains a coefficient and an
exponent.

Example:

• P1: 3x^3 + 2x + 1
• P2: 4x^2 + 2x + 5

Result: 3x^3 + 4x^2 + 4x + 6

C-like Structure:

struct PolyNode {
int coeff, expo;
struct PolyNode* next;
};

Use Case: Symbolic computations, computer algebra systems

7
Q13. What is a Sparse Matrix? Write its 3-Tuple representation with example.

Answer: A sparse matrix is a matrix with most of its elements as zero. To save space, it can be represented
using a 3-tuple format where only non-zero elements are stored.

Example Matrix:

0 0 3
0 0 0
4 0 0

3-Tuple Representation:

Row Col Val

0 2 3
2 0 4

Applications:

• Scientific computing
• Image compression
• Graph algorithms

This completes the core repeated questions across IGNOU MCS-021 past years. Let me know if you want
the non-repeated topics or full PDF export now.