Exam prep

Question 1

Primitive vs. Non-Primitive Data Types

Answer 1

Primitive Data Types: Basic types such as int, char, float, and double. They store single values and are directly supported by the system.
Non-Primitive Data Types: Complex data types like arrays, structures, linked lists, stacks, and queues. These are derived from primitive data types.

Question 2

Postfix Expression Conversion

Answer 2

Expression: ((A + B) * C – (D – E)) / (F + G)
Steps:

Convert innermost parentheses: (A + B) becomes AB+
Convert D – E to DE-
Apply multiplication: AB+C*
Apply subtraction: AB+C*DE-
Final postfix: AB+C*DE-/FG+

Question 3

Priority Queue vs. Normal Queue

Answer 3

Normal Queue: FIFO (First In, First Out) order.
Priority Queue: Each element is associated with a priority. Elements with higher priority are dequeued before elements with lower priority, regardless of their insertion order.

Question 3

Stack Operations with C Code

Answer 3

Basic Operations: Push, Pop, Peek
C Code (Push Example):

c

void push(int stack[], int top, int value) {
if (top == MAX - 1)
printf(“Stack Overflow\n”);
else {
(top)++;
stack[top] = value;
}
}

Question 4

Circular Queue: Insertion & Deletion

Answer 4

void enqueue(int queue[], int front, int rear, int value) {
if ((rear + 1) % MAX == front)
printf(“Queue is full\n”);
else {
*rear = (rear + 1) % MAX;
queue[rear] = value;
}
}

Question 5

Recursive Algorithms for Binary

Answer 5

int findMax(struct Node* root) {
if (root == NULL)
return INT_MIN;
int res = root->data;
int lres = findMax(root->left);
int rres = findMax(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}

Question 6

Kruskal’s Algorithm

Answer 6

Purpose: Find the Minimum Spanning Tree (MST) of a graph.
Steps:

Sort all edges in non-decreasing order of their weight.
Pick the smallest edge. If it doesn't form a cycle, include it in the MST.
Repeat until you have V-1 edges in the MST, where V is the number of vertices.

Question 7

Dijkstra’s Algorithm

Answer 7

Purpose: Find the shortest path from a source node to all other nodes.
Steps:

Set the distance of the source node to 0 and all other nodes to infinity.
Mark the source node as visited.
Update the distances of adjacent nodes.
Repeat for the next unvisited node with the smallest known distance.

Question 8

Hashing: Separate Chaining vs. Open Addressing

Answer 8

Separate Chaining: Uses linked lists to handle collisions. Each bucket of the hash table is a linked list where elements are stored if they hash to the same index.
Open Addressing: Resolves collisions by probing through alternative locations in the hash table (linear probing, quadratic probing, etc.).

Question 9

Binary Heap Deletion Example

Answer 9

Min-Heap Deletion:
Replace the root with the last element.
Heapify down from the root.
Example: Given Min-Heap:

markdown

   10
  /       \
 20      30
/ \       /    40 50 60

after deletion
20
/ \
40 30
/ \ /
50 60

Question 10

Kruskal’s Algorithm Steps

Answer 10

Purpose: Find the Minimum Spanning Tree (MST) of a graph.

Steps:

Sort all edges in non-decreasing order of their weight.
Pick the smallest edge. If it forms a cycle, discard it.
Repeat until there are V-1 edges in the MST.

Example: Graph with edges and weights:

Edges: {(A, B, 1), (A, C, 3), (B, C, 2)}
MST edges after sorting: {(A, B, 1), (B, C, 2)}

Question 11

Dijkstra’s Algorithm Steps

Answer 11

Purpose: Find the shortest path from a source node to all other nodes.

Steps:

Initialize distances: Set source distance to 0, all others to infinity.
Mark the source node as visited.
Update distances of adjacent nodes.
Repeat until all nodes are visited.

Example: From Node A to others in a weighted graph.

Question 12

DFS vs. BFS for Tree Traversal

Answer 12

Depth-First Search (DFS):

Traversal Order: Pre-order, In-order, Post-order.
Use Cases: Finding paths, topological sorting.

Breadth-First Search (BFS):

Traversal Order: Level-order.
Use Cases: Shortest path in unweighted graphs, finding connected components.

Question 13

Bellman-Ford Algorithm for Shortest Paths

Answer 13

Purpose: Find shortest paths from a single source, even with negative weights.
Steps:

Initialize distances from source to all other vertices as infinite.
Set the distance to the source itself as 0.
Relax all edges V-1 times.
Check for negative weight cycles.

Question 14

Infix to Postfix Conversion Example

Answer 14

Infix Expression: ((A + B) * C - (D - E)) / (F + G)
Step Symbol Stack Postfix Expression
1 ( (
2 ( ((
3 A (( A
4 + ((+ A
5 B ((+ AB
6 ) ( AB+
7 * (* AB+
8 C (* AB+C
9 - (- AB+C*
10 ( (-( AB+C*
11 D (-( AB+CD
12 - (-(- AB+CD
13 E (-(- AB+CDE
14 ) (- AB+CDE-
15 ) AB+CDE-
16 / / AB+CDE-
17 ( /( AB+CDE-
18 F /( AB+CDE-F
19 + /(+ AB+CDE-F
20 G /(+ AB+CDE-FG
21 ) / AB+CDE-FG+
22 End AB+CDE-FG+/

Postfix Expression: AB+C*DE-FG+/

Question 15

Postfix Evaluation Example

Answer 15

Postfix Expression: 52+83-*4/
Step Symbol Stack Explanation
1 5 5 Push 5 onto the stack.
2 2 5, 2 Push 2 onto the stack.
3 + 7 5 + 2 = 7, push 7.
4 8 7, 8 Push 8 onto the stack.
5 3 7, 8, 3 Push 3 onto the stack.
6 - 7, 5 8 - 3 = 5, push 5.
7 * 35 7 * 5 = 35, push 35.
8 4 35, 4 Push 4 onto the stack.
9 / 8.75 35 / 4 = 8.75, push 8.75

Result: 8.75

Question 16

Depth-First Search (DFS) Example

Answer 16

A
/ \
B C
| |
D E
Starting from A:
Step Vertex Visited Stack Traversal
1 A A A
2 B A, B A B
3 D A, B, D A B D
4 Backtrack to B A, B A B D
5 Backtrack to A A A B D
6 C A, C A B D C
7 E A, C, E A B D C E

DFS Traversal: A B D C E

Question 17

Breadth-First Search (BFS) Example

Answer 17

A
/ \
B C
| |
D E
Step Vertex Visited Queue Traversal
1 A A A
2 B B, C A B
3 C C, D A B C
4 D D, E A B C D
5 E E A B C D E

BFS Traversal: A B C D E

Question 18

Kruskal’s Algorithm Example

Answer 18

Edges:
(A, B) = 1
(A, C) = 3
(B, C) = 2
(C, D) = 4
Step Edge Added Selected Edges Total Weight
1 (A, B) = 1 A-B 1
2 (B, C) = 2 A-B, B-C 3
3 (A, C) = 3 Discard (cycle) 3
4 (C, D) = 4 A-B, B-C, C-D 7
Minimum Spanning Tree: A-B, B-C, C-D
Total Weight: 7

Question 19

Dijkstra’s Algorithm Example

Answer 19

Graph with Weights:
A
/ \
B C
| |
D E
Weights:
A-B: 1, A-C: 4, B-D: 2, C-E: 5
Step Vertex Processed Shortest Path Estimate Explanation
1 A A: 0, B: 1, C: 4 Start from A.
2 B A: 0, B: 1, D: 3 Process B, update D.
3 C A: 0, B: 1, D: 3, E: 9 Process C, update E.
4 D A: 0, B: 1, D: 3 Process D, no update.
5 E A: 0, B: 1, D: 3, E: 9 Process E. Done.
Shortest Path Estimates from A:

A -> B = 1
A -> D = 3
A -> C = 4
A -> E = 9

Question 20

Prim’s Algorithm: Calculating Minimum Spanning Tree (MST) Weight

Answer 20

Prim’s Algorithm also finds the Minimum Spanning Tree, but it starts from a single vertex and grows the tree by adding the smallest edge that connects a vertex already in the tree to a vertex not yet in the tree.
A
/ \
1 3
B—–C
\ /
2
D
Start from vertex A:

Add the smallest edge connected to A (i.e., A-B = 1).
Now the tree contains vertices A and B. Next, add the smallest edge connected to these vertices that does not form a cycle (i.e., B-D = 2).
Add A-C = 3 to connect C.

Step Edge Added Tree Formed Total Weight
1 A-B = 1 A-B 1
2 B-D = 2 A-B-D 1 + 2 = 3
3 A-C = 3 A-B-D-C 3 + 3 = 6

MST Total Weight: 6