3-Mark Questions

1. Explain an AVL tree, and what properties distinguish it from a regular binary search
tree (BST)?​
An AVL tree is a self-balancing binary search tree where the difference in heights of the left
and right subtrees (called the balance factor) of any node is at most 1.​
Key properties distinguishing it from BST:

●​ Balance Factor: For every node, |height(left) - height(right)| ≤ 1.​

●​ Rotations: AVL tree uses rotations (LL, RR, LR, RL) to maintain balance after insertions
or deletions.​

●​ Time Complexity: O(log n) for insertion, deletion, and search due to strict balancing.​

2. Explain the balancing of AVL trees after insertion or deletion of nodes, and why is this
balancing necessary?​
After insertion or deletion, the balance factor of a node may become less than -1 or more than
1. To restore the AVL property, rotations are applied:

●​ LL Rotation: Insertion in the left subtree of the left child.​

●​ RR Rotation: Insertion in the right subtree of the right child.​

●​ LR Rotation: Insertion in the right subtree of the left child.​

●​ RL Rotation: Insertion in the left subtree of the right child.​

Balancing is necessary to maintain O(log n) time complexity, which ensures faster
operations compared to an unbalanced BST.​

3. Explain the time complexity of common operations (insertion, deletion, and search) in
an AVL tree, and how does it compare to a regular binary search tree (BST)?

●​ AVL Tree:​
 ○​ Insertion: O(log n)​

○​ Deletion: O(log n)​

○​ Search: O(log n)​

This is due to strict balancing.​

●​ Regular BST:​

○​ Best Case: O(log n)​

○​ Worst Case: O(n) (degenerates into a linked list if unbalanced)​

AVL trees provide more consistent performance in comparison to BSTs.​

4. Explain the concept of a binary search tree (BST) and its key properties.​
A Binary Search Tree is a binary tree in which each node has the following properties:

●​ The left subtree contains nodes with values less than the node’s value.​

●​ The right subtree contains nodes with values greater than the node’s value.​

●​ The left and right subtrees are also BSTs.​

Key properties:​

●​ Inorder traversal yields sorted order.​

●​ Efficient for search, insert, and delete operations if balanced.​

5. Construct a binary search tree from the following list of numbers: [10, 5, 15, 3, 7, 12,
18].

Step-by-step Insertion:

●​ Insert 10 → root​

●​ Insert 5 → left of 10​

●​ Insert 15 → right of 10​

 ●​ Insert 3 → left of 5​

●​ Insert 7 → right of 5​

●​ Insert 12 → left of 15​

●​ Insert 18 → right of 15​

Final BST Structure:

10

/ \

5 15

/\ / \

3 7 12 18

6. Evaluate an in-order traversal on the binary search tree given:

10

/ \

5 15

/\ / \

3 7 12 18

In-order Traversal Rule: Left → Root → Right​

Traversal Steps:

●​ Left subtree of 10 → in-order(5) = in-order(3) → 3, 5, 7​

●​ Root = 10​

●​ Right subtree of 10 → in-order(15) = in-order(12) → 12, 15, 18​

Final Answer: 3, 5, 7, 10, 12, 15, 18

7. Illustrate what a graph is and explain the main components of a graph.​

A graph is a collection of nodes (vertices) and edges (links) connecting pairs of vertices.​
Main Components:

●​ Vertices (V): Represent entities (e.g., cities, computers).​

●​ Edges (E): Connections between vertices.​

●​ Types:​

○​ Directed (edges have direction)​

○​ Undirected (edges are bidirectional)​

●​ Weights (optional): Value or cost associated with edges in weighted graphs.​

8. Describe path in a graph. Distinguish the difference between a simple path and a cycle
in a graph. Provide an example of each.

●​ Path: A sequence of vertices where each adjacent pair is connected by an edge.​

●​ Simple Path: No repeated vertices or edges.​

○​ Example: A → B → C​

●​ Cycle: A path that starts and ends at the same vertex.​

○​ Example: A → B → C → A​

9. Differentiate a connected graph and a disconnected graph. Provide examples of each.

●​ Connected Graph: There is a path between every pair of vertices.​

Example:​
​
A—B

○​
●​ Disconnected Graph: Not all pairs of vertices have paths between them.​

Example:​
​
A—B D—E

○​

10. Justify the primary purpose of a B-tree in database systems.​

The primary purpose of a B-tree is to maintain sorted data for fast retrieval, insertion, and
deletion in large-scale storage systems like databases and file systems.​
Justification:

●​ Minimizes disk I/O by reducing tree height.​

●​ Keeps data balanced to ensure O(log n) operations.​

●​ Efficient for range queries due to its ordered structure.​

●​ Used in indexes in DBMS like MySQL and Oracle.​

11. Distinguish between a B+ tree and a B-tree, and write advantages of both in terms of
searching and range queries.

Feature B-Tree B+ Tree

Leaf Nodes Contains both data and keys Only leaf nodes store data

Internal Nodes Store keys and data Store only keys

 Searching Slower than B+ tree for ranges Faster for range-based
queries

Range Inefficient due to scattered Efficient due to linked leaves

Queries data

Advantages:

●​ B-Tree: Good for point queries (exact key lookups).​

●​ B+ Tree: Excellent for range-based searches and sequential access due to linked leaf
nodes.​

12. Explain the process of inserting a new value into a B-tree.​

Steps:

1.​ Search the appropriate leaf node for the new value.​

2.​ Insert the value in sorted order in the leaf.​

3.​ If the node exceeds the allowed number of keys:​

○​ Split the node into two nodes.​

○​ Promote the middle key to the parent node.​

4.​ Repeat the process up the tree if necessary.​

5.​ If the root splits, a new root is created — increasing the tree height.​

13. Write the difference between a directed graph (digraph) and an undirected graph.
Provide an example of each.

Feature Directed Graph (Digraph) Undirected Graph

Edge Direction Has a direction (A → B) No direction (A — B)

Representatio Arrows or ordered pairs Lines or unordered

n pairs
Example:

●​ Directed: A → B​

●​ Undirected: A — B​

14. Compute the time complexity?

for (int i = 0; i <= n; i++) {

for (int j = 0; j <= n; j++) {
Statement 1;
Statement 2;
...
Statement n;
}
}

Analysis:

●​ Outer loop: Runs (n + 1) times → O(n)​

●​ Inner loop: Runs (n + 1) times → O(n)​

●​ Inside: Constant number of statements (say k) → O(1)​

Total Time Complexity: O(n²)​

15. Compute the output of the pseudo code when n == 5?

int Factorial (int n)

{
if (n==0)
return 1;
else
return n * factorial(n-1);
}

Calculation:
 ●​ factorial(5)​
= 5 × factorial(4)​
= 5 × 4 × factorial(3)​
= 5 × 4 × 3 × factorial(2)​
= 5 × 4 × 3 × 2 × factorial(1)​
= 5 × 4 × 3 × 2 × 1 × factorial(0)​
= 5 × 4 × 3 × 2 × 1 × 1 = 120​

Answer: 120

16. Solve the following.​

Given:​
F[0] = 0, F[1] = 1​
Find: F[9]​
F[i] = F[i-1] + F[i-2] (Fibonacci series)

Calculation:

●​ F[2] = 1​

●​ F[3] = 2​

●​ F[4] = 3​

●​ F[5] = 5​

●​ F[6] = 8​

●​ F[7] = 13​

●​ F[8] = 21​

●​ F[9] = 34​

Answer: 34

17. Predict the address of an element in 1D array using the formula​

Given:
 ●​ Base address (B) = 2000​

●​ Size of each element (W) = 4 bytes​

●​ Index (K) = 5​

●​ Formula: Address of A[K] = B + W * K​

Calculation:​
Address = 2000 + 4 × 5 = 2020

Answer: 2020

18. Construct Postfix expression of A * B + C / D

Infix: A * B + C / D​
Postfix conversion steps:

1.​ A * B → AB*​

2.​ C / D → CD/​

3.​ AB* + CD/ → AB*CD/+​

Answer: AB*CD/+

19. int Stack[10] = [5, 4, 3, 23, 11, 4, 6, 7], Top = 7​

Top = 7 means Stack[7] = 7 is the current topmost element.​
Stack structure (bottom to top):

Index: 0 1 2 3 4 5 6 7
Value: 5 4 3 23 11 4 6 7

Answer: Top element = 7, Top index = 7

20. Perform 3 Pop operations first, then 4 Push operations: 22, 12, 5, 16
Initial Stack: Top = 7​
After 3 Pops: Remove 7, 6, 4 → Top moves to index 4​
Stack becomes:​
[5, 4, 3, 23, 11] (Top = 4)

Push 22 → Top = 5​
Push 12 → Top = 6​
Push 5 → Top = 7​
Push 16 → Top = 8

Final Top index: 8​

Top element: 16

Answer: Top = 8, Top Element = 16

21. Deduce the number of elements inside a Queue when Front = 2 and Rear = 6.

Given:​
Queue[8] = [20, 30, 25, 12, 15, 24, 32, 16]​
Front = 2, Rear = 6

Formula:​
Number of elements = Rear - Front + 1 = 6 - 2 + 1 = 5

Answer: 5 elements

22. Evaluate Popped out sequence for the following:​

Operations:​
Push(10), Push(20), POP, Push(10), Push(20), POP, POP, POP, Push(20), POP

Simulation using Stack:

1.​ Push 10 → Stack = [10]​

2.​ Push 20 → Stack = [10, 20]​

3.​ POP → 20 (Popped)​

4.​ Push 10 → Stack = [10, 10]​

5.​ Push 20 → Stack = [10, 10, 20]​

 6.​ POP → 20​

7.​ POP → 10​

8.​ POP → 10​

9.​ Push 20 → Stack = [20]​

10.​POP → 20​

Popped sequence: 20, 20, 10, 10, 20

Answer: 20, 20, 10, 10, 20

23. Define time complexity and space complexity.

●​ Time Complexity: The total amount of time taken by an algorithm to run, measured as a
function of the input size (n).​

○​ Example: O(n), O(n²), etc.​

●​ Space Complexity: The total memory space required by an algorithm to run to

completion, also expressed as a function of input size.​

Answer:

●​ Time complexity measures execution time.​

●​ Space complexity measures memory usage.​

24. Interpret the pseudo code to find the running time complexity:

for (int i = 0; i <= n; i++) {

if (i % 2 == 0) {
i = i + 2;
} else {
i = i - 2;
}
}
Analysis:​
This loop has a non-standard increment.

●​ When i is even: i = i + 2​

●​ When i is odd: i = i - 2​

This can create an infinite loop for certain values of n, especially when i keeps oscillating.

Worst-case Time Complexity: Infinite / Undefined (non-terminating)

25. Classify nonlinear data structures into self-balancing and non-self-balancing

categories.

Type Example

Self-Balancing AVL Tree, Red-Black Tree

Non-Self-Balancin Binary Search Tree (unbalanced), Heap,

g B-tree

●​ ​
Self-Balancing trees adjust themselves after insertion/deletion.​

●​ Non-Self-Balancing does not guarantee optimal balance unless explicitly managed.​

26. Explain the importance of self-balancing properties in search trees.

Importance:

●​ Self-balancing ensures that the height of the tree remains logarithmic (O(log n)).​

●​ This guarantees efficient performance for search, insertion, and deletion operations.​

●​ Prevents degeneration of the tree into a linked list, which would degrade performance
to O(n).​
 ●​ Helps maintain uniform distribution of nodes, improving traversal speed.​

27. Classify nonlinear data structures into balanced and unbalanced categories.

Balanced Unbalanced

AVL Tree, Red-Black Tree, B-Tree Binary Tree, Binary Search

Tree

●​ ​
Balanced structures keep their height minimized automatically.​

●​ Unbalanced structures may become skewed, increasing time complexity.​

28. Explain the significance of balance in search trees and how it affects their efficiency.

●​ Balanced trees maintain low height: O(log n).​

●​ Ensures consistent and fast performance for all operations.​

●​ Unbalanced trees (e.g., skewed BSTs) may degrade to O(n) time complexity.​

●​ Efficiency is directly proportional to the balance: the better balanced, the faster
operations.​

29. Discuss suitability of B-Tree for scenarios like file systems and databases.

●​ B-Trees are multi-level balanced trees, ideal for disk-based storage.​

●​ Each node can store multiple keys, reducing the tree height.​

●​ Minimizes disk I/O operations during search and update.​

 ●​ Widely used in databases, file systems, and indexing systems (e.g., MySQL, NTFS).​

30. Explain threaded binary tree using an example.

●​ In a threaded binary tree, null pointers are replaced with pointers to inorder
predecessor or successor.​

●​ This allows faster traversal without recursion or stack.​

Example:​
If a node’s right child is NULL, it may point to the inorder successor.

10

/ \

5 15

12

In the threaded version:

●​ The right of 12 may point to 15 (its inorder successor).​

●​ Left of 15 may point back to 12 (inorder predecessor).​

Benefit: Enables inorder traversal using only the threads.

31. Illustrate the advantages of non-linear data structures in computation.

Advantages:

●​ Efficient Relationships: Represent hierarchical or network-like relationships (e.g.,

family trees, web links).​
 ●​ Dynamic Memory Usage: Allow dynamic memory allocation, unlike fixed-size arrays.​

●​ Better Performance: Provide faster access, insertion, and deletion in specific scenarios.​

●​ Examples:​

○​ Trees: used in parsing expressions, file systems.​

○​ Graphs: used in networks, social media connections.​

32. Predict and construct AVL tree for the following data:​
Data: 21, 26, 30, 9, 4, 14, 28, 18, 15, 10, 2, 3, 7

Step-by-step construction with rebalancing is complex for this format, but here’s the idea:

After each insertion, check balance factors and apply:

●​ LL, RR, LR, or RL rotation as needed.​

Final AVL Tree (Simplified Structure):

14
/ \
9 26
/ \ / \
4 10 21 28
/\ \ \ \
2 3 12 30 -
\
7

Note: Actual AVL tree may vary slightly depending on the rotation strategy but will always
maintain balance at each step.

33. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted into an initially empty BST.
Predict the inorder traversal sequence.

Step-by-step Insertion:​
BST structure will look like:
 7
/ \
5 8
/\ \
1 6 9
/\
0 3
/\
2 4

Inorder Traversal (Left → Root → Right):​

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Answer: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

34. Express the application of preorder, postorder, level-order, or inorder tree traversals
to check whether the given binary tree is full or not.

●​ A full binary tree is a tree where every node has 0 or 2 children.​

●​ Application of traversal:​

○​ Use any traversal (preorder/inorder/postorder) to visit all nodes.​

○​ For each node, check:​

■​ If it has only one child, it is not a full tree.​

■​ If all nodes have either 0 or 2 children → it's a full tree.​

Answer: Use traversal to inspect node structure and determine full-ness.

35. Consider the following data and identify which one is Preorder, Inorder, and
Postorder sequences.

●​ S1: N, M, P, O, Q​

●​ S2: N, P, Q, O, M​
 ●​ S3: M, N, O, P, Q​

Let’s examine:

●​ Preorder: Root → Left → Right → Likely S1​

●​ Postorder: Left → Right → Root → Likely S2​

●​ Inorder: Left → Root → Right → Likely S3​

Answer:

●​ S1: Preorder​

●​ S2: Postorder​

●​ S3: Inorder​

36. Explain with example whether a graph is strongly connected or not.

●​ A strongly connected graph is a directed graph where there is a path from every
vertex to every other vertex.​

Example of strongly connected graph:​

​
A→B→C
↑ ↓
←←←

●​
○​ From A, we can reach B and C.​

○​ From C, we can reach A and B, and so on.​

●​ A graph is not strongly connected if any vertex cannot reach another.​

37. Identify the different applications of stack and queue.

 Stack Queue

Function call handling CPU scheduling

Expression evaluation (postfix) Print queue management

Undo feature in text editors Task queue in operating

systems

Backtracking (e.g., maze solving) BFS traversal in graphs

38. Explain different types of Queues.

1.​ Simple Queue: FIFO (First In First Out)​

2.​ Circular Queue: Last position connects to the first to utilize space.​

3.​ Priority Queue: Elements are dequeued based on priority, not order.​

4.​ Double-Ended Queue (Deque): Insertion and deletion possible at both ends.​

39. Explain the concept of a push algorithm in a stack.

Push Algorithm Steps:

1.​ Check if the stack is full (Overflow condition).​

2.​ If not full:​

○​ Increment the Top pointer.​

○​ Place the new item at Stack[Top].​

Example in pseudo-code:

if (Top == Max - 1)
print "Stack Overflow"
else
Top = Top + 1
Stack[Top] = item
40. Explain the concept of a pop algorithm in a stack.

Pop Algorithm Steps:

1.​ Check if the stack is empty (Underflow condition).​

2.​ If not empty:​

○​ Retrieve the element at Stack[Top].​

○​ Decrement the Top pointer.​

Example in pseudo-code:

if (Top == -1)
print "Stack Underflow"
else
item = Stack[Top]
Top = Top - 1

41. Evaluate the postfix expression 5 3 * 10 2 / + using a stack.

Steps:

●​ Stack = []​

●​ Read 5: Push → [5]​

●​ Read 3: Push → [5, 3]​

●​ Read *: Pop 3 and 5 → 5 * 3 = 15 → Push → [15]​

●​ Read 10: Push → [15, 10]​

●​ Read 2: Push → [15, 10, 2]​

●​ Read /: Pop 2 and 10 → 10 / 2 = 5 → Push → [15, 5]​

 ●​ Read +: Pop 5 and 15 → 15 + 5 = 20​

Answer: 20

42. Convert the infix expression A + B * (C - D) to postfix notation using a stack.

Infix: A + B * (C - D)

Steps:

●​ C - D → CD-​

●​ B * (C - D) → B CD- *​

●​ A + ... → A B CD- * +​

Answer: A B C D - * +

43. Explain the concept of an EnQueue algorithm in a Queue.

EnQueue Algorithm Steps:

1.​ Check if the queue is full (Rear == Max - 1 for linear queue).​

2.​ If not full:​

○​ If Front == -1: set Front = 0​

○​ Increment Rear​

○​ Insert item at Queue[Rear]​

Pseudo-code:

if (Rear == Max - 1)

print "Overflow"
else {

if (Front == -1)

Front = 0;

Rear = Rear + 1;

Queue[Rear] = item;

44. Explain the concept of a DeQueue algorithm in a Queue.

DeQueue Algorithm Steps:

1.​ Check if queue is empty (Front == -1 or Front > Rear).​

2.​ If not empty:​

○​ Retrieve item = Queue[Front]​

○​ Increment Front​

○​ If Front > Rear, reset Front = Rear = -1​

Pseudo-code:

if (Front == -1 || Front > Rear)

print "Underflow"

else {

item = Queue[Front];

Front = Front + 1;

if (Front > Rear)

Front = Rear = -1;

}

45. Explain the conditions to check whether a circular queue is empty or full.

●​ Empty Condition:​
Front == -1​

●​ Full Condition (with array size N):​

(Front == 0 && Rear == N - 1) || (Rear + 1) % N == Front​

Answer:

●​ Queue is empty when no elements are in it.​

●​ Queue is full when the next position of Rear is Front (after wrapping around).​

46. Explain what a circular queue is and how it differs from a regular queue.

●​ A circular queue is a linear data structure in which the last position is connected
back to the first, forming a circle.​

●​ It uses modulo arithmetic to wrap around the index when inserting or removing elements.​

Regular Queue Circular Queue

May waste space after Efficient space usage

deletion

Linear layout Circular layout

 Rear cannot go back to start Rear wraps around using (Rear + 1) %
size

47. Explain the key advantages of using a linked list to implement a queue over an array.

Linked List Implementation Array Implementation

Dynamic size (no overflow unless memory full) Fixed size (can overflow)

Insertion/Deletion O(1) May involve shifting elements

Memory-efficient (no pre-allocation) Wastes space if queue is

underused

Key Advantages:

●​ No need to define maximum size in advance.​

●​ Avoids overflow unless memory is exhausted.​

●​ Efficient insertion and deletion.​

48. Describe the Sparse Matrix with proper example.

A sparse matrix is a matrix with more zero elements than non-zero elements.

Example:

0005

0800
0000

3000

Only a few elements (5, 8, 3) are non-zero.

Storage: Instead of storing all elements, store only non-zero elements with their positions to
save memory.

Triplet representation:

Row Col Value

0 3 5

1 1 8

3 0 3

49. Compare 1D and 2D array in data structure.

Feature 1D Array 2D Array

Structure Linear list Matrix (table-like)

Access Single index A[i] Double index A[i][j]

Usage List of values Grids, matrices, tables

Memory Allocation Continuous in single line Continuous, row-major or column-major

50. Discuss short notes on sparse matrix.

●​ Sparse matrices save memory and computation time.​

●​ Used when a large matrix has mostly zero values.​

●​ Stored efficiently using formats like:​

○​ Triplet form (row, col, value)​

○​ Compressed Sparse Row (CSR)​

●​ Applications:​

○​ Graph algorithms​

○​ Image compression​

○​ Scientific computing​

51. Evaluate the following expression from Infix to Postfix and Prefix: A + B * (C - D)

Given Infix: A + B * (C - D)

Postfix Conversion:

1.​ C - D → CD-​

2.​ B * (C - D) → B CD- *​

3.​ A + ... → A B CD- * +​

✅ Postfix: A B C D - * +
Prefix Conversion:

1.​ C - D → - C D​

2.​ B * ... → * B - C D​
 3.​ A + ... → + A * B - C D​

✅ Prefix: + A * B - C D
52. Explain insertion, deletion, traversal operations in data structure.

●​ Insertion: Adding a new element to a data structure.​

○​ Examples: Inserting into an array, linked list, tree, etc.​

●​ Deletion: Removing an existing element.​

○​ Must handle rearranging or re-linking (e.g., shifting in arrays, updating pointers in

lists).​

●​ Traversal: Visiting all elements in a data structure.​

○​ Arrays: Linear iteration​

○​ Trees: Inorder, Preorder, Postorder​

○​ Graphs: BFS, DFS​

53. Explain the need for a double-ended queue (deque) and its usage scenarios.

●​ A deque allows insertion and deletion at both front and rear.​

●​ Useful when both stack and queue operations are required.​

Use Cases:

●​ Sliding window problems (e.g., in data streaming)​

●​ Task scheduling​

●​ Undo/redo functionality in applications​

54. Explain the term "queue capacity" and its significance in queue data structures.

●​ Queue capacity: Maximum number of elements a queue can hold.​

●​ Important to manage overflow and memory usage.​

●​ In dynamic queues (linked lists), capacity is limited by memory.​

●​ In static queues (arrays), it's predefined.​

55. Explain insertion, deletion, traversal operation in data structure (same as Q52 –
possibly repeated)

✅ Answer Summary (as above):

●​ Insertion: Add data​

●​ Deletion: Remove data​

●​ Traversal: Visit all data​

Different data structures may implement these in specific ways (linked list, arrays, trees, etc.)