UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 7: Data Structures and Algorithms PYQ (June 2024 Re-Exam)
Q30. Arrange the following recurrence relations in increasing order of their time complexity:
(A) T(n) = T(n/2) + 1
(B) T(n) = 2T(n/2) + n
(C) T(n) = 3T(n/3) + n
(D) T(n) = 2T(n/2) + √n
(E) T(n) = T(n−1) + 1
Choose the correct answer from the options given below:
(A) T(n) = T(n/2) + 1
(B) T(n) = 2T(n/2) + n
(C) T(n) = 3T(n/3) + n
(D) T(n) = 2T(n/2) + √n
(E) T(n) = T(n−1) + 1
Choose the correct answer from the options given below:
- (E), (A), (B), (D), (C)
- (A), (E), (D), (B), (C)
- (E), (A), (D), (B), (C)
- (A), (B), (D), (E), (C)
Q59. Select the sorting algorithms that are stable.
(A) Quick Sort
(B) Bubble Sort
(C) Insertion Sort
(D) Merge Sort
(E) Shell Sort
Choose the correct answer from the options given below:
(A) Quick Sort
(B) Bubble Sort
(C) Insertion Sort
(D) Merge Sort
(E) Shell Sort
Choose the correct answer from the options given below:
- (A), (B), (C) and (E) Only
- (A), (D) and (E) Only
- (B) and (C) Only
- (B), (C) and (D) Only
Q60. ______ is a self-balancing binary search tree where the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.
- Expression tree
- Game tree
- Red-Black tree
- Threaded tree
Q74. Match List I with List II
| List I | List II |
|---|---|
| (A) Dijkstra's Algorithm | (I) Finds the shortest path between all pairs of vertices in a graph with positive or negative edge weights. |
| (B) Floyd-Warshall Algorithm | (II) Finds the shortest path in a weighted graph with non-negative edge weights. |
| (C) Bellman-Ford Algorithm | (III) Finds single-source shortest paths with possible negative weights. |
| (D) Prim's Algorithm | (IV) Finds the Minimum Spanning Tree (MST). |
- (A)-(I), (B)-(II), (C)-(III), (D)-(IV)
- (A)-(II), (B)-(I), (C)-(III), (D)-(IV)
- (A)-(I), (B)-(II), (C)-(IV), (D)-(III)
- (A)-(III), (B)-(II), (C)-(IV), (D)-(I)
Q83. Arrange the following steps in the correct order to solve the Knapsack problem using Dynamic Programming.
(A) Define the base case when the capacity is zero or no items are left to consider
(B) Compute the maximum value that can be obtained using items up to the i-th item and a knapsack capacity of W
(C) Identify subproblems and their dependencies based on item weights and values
(D) Initialize a table to store results of subproblems
(E) Iterate through each item and each possible capacity to fill the table
Choose the correct answer from the options given below:
(A) Define the base case when the capacity is zero or no items are left to consider
(B) Compute the maximum value that can be obtained using items up to the i-th item and a knapsack capacity of W
(C) Identify subproblems and their dependencies based on item weights and values
(D) Initialize a table to store results of subproblems
(E) Iterate through each item and each possible capacity to fill the table
Choose the correct answer from the options given below:
- (C), (D), (A), (E), (B)
- (D), (C), (A), (E), (B)
- (A), (C), (D), (E), (B)
- (D), (A), (C), (E), (B)
Q86. Match List I (Recurrence Relation) with List II (Complexity)
| List I | List II |
|---|---|
| (A) T(n) = 2T(n/2) + n | (I) T(n) = Θ(n log n) {exact solution} |
| (B) T(n) = T(n/2) + 1 | (II) O(n²) |
| (C) T(n) = 2T(n/2) + 1 | (III) T(n) = Θ(n) {exact solution} |
| (D) T(n) = T(n−1) + n | (IV) O(n) |
- (A)-(I), (B)-(IV), (C)-(III), (D)-(II)
- (A)-(IV), (B)-(II), (C)-(I), (D)-(III)
- (A)-(I), (B)-(III), (C)-(IV), (D)-(II)
- (A)-(III), (B)-(I), (C)-(IV), (D)-(II)