UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 7: Data Structures and Algorithms PYQ (December 2022 Shift 1)
Q25. In a ______ the left and right subtrees of some node differ in height by more than one.
- Balanced binary tree
- Weight-balanced binary tree
- Height-balanced tree
- Unbalanced binary tree
Q26. FFTs are ______ techniques used to encode digital video and audio information and help analyse the signal in the ____ domain.
- Encryption, time
- Encryption, frequency
- Compression, time
- Compression, frequency
Q27. Given six weights 4, 15, 25, 5, 8, 16, construct a 2-tree (extended binary tree) with minimum weighted path length. What is the minimum weighted path length?
- 231
- 172
- 73
- 77
Q28. Suppose we store n keys in a hash table of size m = n² using a hash function h chosen randomly from a universal class of hash functions. Then the probability that there are any collisions is ______
- greater than 1/5
- greater than 1/2
- less than 1/2
- less than 1/5
Q56. Which of the following rotations are correctly explained in the context of an AVL tree?
A. LL rotation: the new node is inserted in the left subtree of the left subtree of the critical node.
B. RR rotation: the new node is inserted in the right subtree of the right subtree of the critical node.
C. LR rotation: the new node is inserted in the right subtree of the left subtree of the critical node.
D. RL rotation: the new node is inserted in the left subtree of the right subtree of the critical node.
Choose the correct answer from the options given below:
A. LL rotation: the new node is inserted in the left subtree of the left subtree of the critical node.
B. RR rotation: the new node is inserted in the right subtree of the right subtree of the critical node.
C. LR rotation: the new node is inserted in the right subtree of the left subtree of the critical node.
D. RL rotation: the new node is inserted in the left subtree of the right subtree of the critical node.
Choose the correct answer from the options given below:
- A, D only
- A, C Only
- A, B, C and D
- B, C Only
Q57. In the context of Hamiltonian problems, which of the following are correct?
A. The Hamiltonian cycle problem is NP-complete.
B. If G is an undirected bipartite graph with an odd number of vertices, then G is Hamiltonian.
C. The Hamiltonian path problem cannot be solved in polynomial time on a directed acyclic graph.
D. If G is a connected undirected graph with at least three vertices, then G³ (the graph obtained by connecting all pairs of vertices joined by a path of length at most 3 in G) is Hamiltonian.
E. If any NP-complete problem is polynomial-time solvable, then P = NP.
Choose the most appropriate answer from the options given below:
A. The Hamiltonian cycle problem is NP-complete.
B. If G is an undirected bipartite graph with an odd number of vertices, then G is Hamiltonian.
C. The Hamiltonian path problem cannot be solved in polynomial time on a directed acyclic graph.
D. If G is a connected undirected graph with at least three vertices, then G³ (the graph obtained by connecting all pairs of vertices joined by a path of length at most 3 in G) is Hamiltonian.
E. If any NP-complete problem is polynomial-time solvable, then P = NP.
Choose the most appropriate answer from the options given below:
- A, B, C only
- B, D, E only
- A, D, E only
- A, C, E only
Q58. For matrix multiplication using the simple divide-and-conquer algorithm:
A. The running time is T(n) = Θ(n³)
B. The running time is T(n) = Θ(n² log n)
C. The recurrence is T(n) = 8T(n/2) + Θ(n²)
D. The recurrence is T(n) = 8T(2n) + Θ(n² log n)
E. One of the Master theorem cases is applicable
Choose the most appropriate answer from the options given below:
A. The running time is T(n) = Θ(n³)
B. The running time is T(n) = Θ(n² log n)
C. The recurrence is T(n) = 8T(n/2) + Θ(n²)
D. The recurrence is T(n) = 8T(2n) + Θ(n² log n)
E. One of the Master theorem cases is applicable
Choose the most appropriate answer from the options given below:
- A, C, E only
- A, D, E only
- B, D, E only
- B, C, D only
Q66. Match List I with List II
| List I | List II |
|---|---|
| A. Linear Program | I. Prim's Algorithm |
| B. Predicate Logic | II. In order |
| C. Tree Traversal | III. Simplex Algorithm |
| D. Minimum Spanning Tree Problem | IV. First order logic |
- A-IV; B-III; C-I; D-II
- A-III; B-IV; C-II; D-I
- A-II; B-IV; C-I; D-III
- A-III; B-IV; C-I; D-II
Q72. Match List I with List II
| List I | List II |
|---|---|
| A. 8-Queens problem | I. Divide and conquer |
| B. Closest pair of points | II. Dynamic Programming |
| C. String edit problem | III. Greedy Method |
| D. Knapsack problem | IV. Backtracking |
- A-I, B-II, C-III, D-IV
- A-I, B-IV, C-II, D-III
- A-IV, B-I, C-II, D-III
- A-II, B-III, C-IV, D-I
Q78. Arrange the following search and sort algorithms in ascending order of their worst-case complexities:
A. Merge sort
B. Linear search
C. Bubble sort
D. Binary search
Choose the correct answer from the options given below:
A. Merge sort
B. Linear search
C. Bubble sort
D. Binary search
Choose the correct answer from the options given below:
- D, B, A, C
- B, D, A, C
- B, D, C, A
- B, A, D, C
Directions (Q91–95): For a knapsack problem, P and W are the profits and weights of a set of 7 items:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}
Q91. Find the optimal solution of the fractional knapsack problem when the maximum capacity is 15.
- 43
- 40
- 45
- 44
Q92. What is the maximum value of the items you can carry if the maximum weight allowed is 25 (fractional knapsack)?
- 48.1
- 49
- 47.9
- 40
Q93. If a new item (P = 5, W = 2) is added, giving 8 items, and the capacity is 25, then the time of fractional knapsack in this case is ______
- O(8)
- O(64)
- O(24)
- O(56)
Q94. The most efficient solution to the fractional knapsack problem with maximum capacity 15 is obtained using ___
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithm
- Backtracking
Q95. Which of the following statements about the knapsack problem is correct?
- 0/1 knapsack can be applied to all kinds of problems, but fractional knapsack only if the problem meets certain conditions.
- There is no difference between the two; they give the same solution for any problem.
- We use the greedy algorithm for 0/1 knapsack and dynamic programming for fractional knapsack.
- In the 0/1 knapsack problem items cannot be divided into smaller portions, while in the fractional knapsack items can be divided in any proportion.