Solution

• Topological Sort → Can be done using DFS (by finishing times). ✅

• Strongly Connected Components (SCCs) → Kosaraju’s and Tarjan’s algorithms use DFS. ✅

• Solving Maze Problem → DFS is a valid approach to explore paths in a maze. ✅

• Finding minimum distance in an unweighted graph → This requires Breadth First Search (BFS), not DFS, because BFS ensures the shortest path in an unweighted graph. ❌

Solution

Solution

Solution

Solution

Solution

The difference between Quicksort and Randomized Quicksort lies mainly in the way the pivot element is chosen. Let’s analyze each option:

1. Selection of Pivot element ✅

   • Quicksort: Pivot is chosen deterministically (e.g., always first element, last element, or middle element).

   • Randomized Quicksort: Pivot is chosen randomly (uniformly among available elements).
     → This is the key difference.

2. Worst case time complexity ❌

   • For both, the worst case is still O(n²).

   • Randomization only reduces the chance of hitting the worst case often, but it does not eliminate it.

3. Best case time Complexity ❌

   • Both have the same best case: O(n log n) (when pivot splits the array evenly).

   • Randomization doesn’t change the best case.

4. Final Output ❌

   • Both produce the same sorted output.

   • Randomization only affects the process, not the final result.

Solution

Solution

Match the pairs:

• (A) BFS → Queue (IV)

• (B) DFS → Stack (I)

• (C) Heap Sort → Priority Queue (III)

• (D) Storage on secondary storage devices → B-Trees (II)

Solution

Solution

Solution

Solution

Solution

When implementing a database, the most appropriate data structure depends on what part of the database you’re focusing on. Among common options, the standard and most suitable choice is:

B-Tree (or B+ Tree)

• Used by almost all modern databases (MySQL, PostgreSQL, Oracle, etc.) to implement indexes.

• Provides efficient search, insert, delete, and range queries in O(log n) time.

• Optimized for disk storage and block reads, making it ideal for large datasets.

Other data structures used in databases:

1. Hash Tables

   • Used for hash indexes and quick equality lookups (e.g., WHERE id = 100).

   • Very fast for exact matches but not good for range queries.

2. Heaps

   • Used to store unsorted table data.

   • Simple structure but inefficient for searches without indexes.

3. Linked Lists

   • Used internally for things like transaction logs and some in-memory structures.

4. Trie / Radix Trees

   • Sometimes used for full-text search or prefix matching.

Solution

Each node is having a successor node in a Linked List.

• In a linked list, every node contains data and a pointer (or reference) to its successor node (the next node in the sequence).

• The last node points to NULL (in a singly linked list) or back to the head (in a circular linked list).

Solution

Solution

// Structure of node
struct Node {
    int data;
    struct Node* link;
};

// Function to get last node
struct Node* getLastNode(struct Node* head) {
    struct Node* temp = head;

    // Traverse until last node
    while (temp -> link != NULL) {
        temp = temp -> link;
    }

    return temp;  // Now temp points to last node
}
  

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

Solution

In a Binary Search Tree (BST), all keys in the left subtree are smaller than the root and all keys in the right subtree are larger than the root.

Inorder traversal follows the order:
Left Subtree → Root → Right Subtree

Because of the BST property, this traversal prints the elements in sorted order.

The reason correctly explains the inorder traversal process where the root is printed between its left and right subtree.

Correct Answer: (a) Assertion is true, Reason is true, and Reason is the correct explanation of the Assertion.

Solution

Minimum Spanning Tree → Kruskal's algorithm → III
Topological Sort → DFS based algorithm → IV
Recursion → uses stack → II
AVL Tree → height balanced tree → I

Correct Answer: (d) (A)-III, (B)-IV, (C)-II, (D)-I

Solution

Solution

Deletion from Queue → O(1)
Worst case search in Binary Search Tree → O(n)
Insertion in Stack → O(1)
Quick Sort worst case → O(n²)

Same order complexity:
Deletion from Queue and Insertion in Stack → O(1)

Correct Answer: (b) A, C

Solution

Number of elements in an array is calculated using:

Length = Upper Bound − Lower Bound + 1

Example:
If Lower Bound = 0 and Upper Bound = 9

Length = 9 − 0 + 1 = 10

Correct Answer: (c) Upper bound − Lower bound + 1

Solution

Tower of Hanoi → solved using recursion and stack concept
Evaluation of postfix expression → uses stack
Recursion → implemented using call stack

Priority queue is implemented using heap or special queue structure, not stack.

Correct Answer: (c) Priority queue