CUET PG MCA Data Structures Previous Year Questions (PYQs) – Page 1 of 4
Study Stuff for MCA Examinations
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
• Deletion: To delete, we also search for the node (\(O(h)\)) and adjust pointers (constant). Worst case: \(h=n\). So, time = \(O(n)\).
✅ Therefore: \[ \text{Insertion: } O(n), \quad \text{Deletion: } O(n) \]
Solution
• Binary Search: Time complexity \(O(\log n)\). Depends on \(n\). ❌
• Hashing: Average case \(O(1)\). Independent of \(n\) (worst case \(O(n)\)). ✅
• Linear Search: Time complexity \(O(n)\). Depends on \(n\). ❌
• Jump Search: Time complexity \(O(\sqrt{n})\). Depends on \(n\). ❌
Therefore: \[ \text{Correct Answer: Hashing (Option 2).} \]
Solution
(A) \(\; \text{while }(x \neq NIL \;\wedge\; x.key \neq k)\)
(B) \(\; x = L.head\)
(C) \(\; x = x.next\)
(D) \(\; \text{return } x\)
Correct order:
1. Initialize pointer: \((B)\) → \(x = L.head\)
2. Loop until end or key found: \((A)\) → \(\text{while}(x \neq NIL \;\wedge\; x.key \neq k)\)
3. Move to next node: \((C)\) → \(x = x.next\)
4. Return result: \((D)\) → \(\text{return }x\)
✅ Therefore, the correct sequence is: \[ (B), (A), (C), (D) \]
Solution
(A) Bubble Sort (worst case): \(O(n^2)\)
(B) Deleting head node in singly linked list: \(O(1)\)
(C) Binary Search: \(O(\log n)\)
(D) Merge Sort (worst case): \(O(n \log n)\)
Step 2: Arrange in increasing order
\[ O(1)\;<\;O(\log n)\;<\;O(n \log n)\;<\;O(n^2) \] So: \[ (B)\;<\;(C)\;<\;(D)\;<\;(A) \]
Solution
The difference between Quicksort and Randomized Quicksort lies mainly in the way the pivot element is chosen. Let’s analyze each option:
-
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.
-
-
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.
-
-
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.
-
-
Final Output ❌
-
Both produce the same sorted output.
-
Randomization only affects the process, not the final result.
-
Solution
BST Procedure Time Complexities (MathJax):
- 1. TREE-SUCCESSOR: \( O(h) \)
- 2. TREE-MAXIMUM: \( O(h) \)
- 4. TREE-MINIMUM: \( O(h) \)
- 3. INORDER-WALK: \( \Theta(n) \)
Since \(O(h)\) differs from \( \Theta(n) \) and INORDER-WALK always visits all \(n\) nodes,
\[ \boxed{\text{Distinct running time: INORDER-WALK (Option 3)}} \]
| List-I | List-II |
| (Algorithm/ Application) | (Data Structure Used) |
| (A). BFS | (1). Stack |
| (B). DFS | (II). B Trees |
| (C). Heap sort | (III). Priority Queue |
| (D). Storage on secondary storages devices | (IV). Queue |
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
In a binary heap (array representation):
Parent(i) = \(\left\lfloor \tfrac{i}{2} \right\rfloor\), Left(i) = \(2i\), Right(i) = \(2i+1\)
All three can be computed directly from the index i.
But the heap size depends on the total number of elements \((n)\), which cannot be determined from i alone.
\(\therefore\) Correct Answer: (2) Heap size
Solution
Linear Probing → collisions resolved by moving sequentially to next free slot.
Quadratic Probing → collisions resolved by quadratic jumps.
Universal Hashing → refers to a family of hash functions, not directly a collision handling method.
Chaining → collisions are handled by storing all elements in the same slot using a linked list (or another secondary structure).
CUET PG MCA
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
CUET PG MCA
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
