UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 7: Data Structures and Algorithms PYQ (September 2022)
Q52. Assume that f(n), g(n) and h(n) are asymptotically positive. Which of the following is correct?
- f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = ω(h(n))
- f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = O(h(n))
- f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
- f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = Ω(h(n))
Q53. The solution of the recurrence relation T(n) = 3T(n/4) + n log n is
- Θ(n2 log n)
- Θ(n log n)
- Θ(n log2 n)
- Θ(log log n)
Q54. The number of nodes of height h in any n-element heap is at most
- ⌈n / 2h+1⌉
- ⌈n / 2h−1⌉
- ⌈n / 2h⌉
- ⌈(n − 1) / 2h−1⌉
Q55. Consider a B-tree of height h and minimum degree t ≥ 2 that contains n keys, n ≥ 1. Which of the following is correct?
- h ≥ logt((n + 1)/2)
- h ≤ logt((n + 1)/2)
- h ≥ logt((n − 1)/2)
- h ≤ logt((n − 1)/2)
Q56. Which algorithm design approach is used in the quick sort algorithm?
- Dynamic programming
- Backtracking
- Divide and conquer
- Greedy approach
Q57. Consider a hash table of size 11 that uses open addressing with linear probing, with h(k) = k mod 11. Records with keys 43, 36, 92, 87, 11, 47, 11, 13, 14 are inserted into an initially empty table with bins 0–10. What is the index of the bin into which the last record is inserted?
- 8
- 7
- 10
- 4
Q58. Consider the traversals of a tree:
Preorder → ABCEIFJDGHKL
Inorder → EICFJBGDKHLA
Which of the following is the correct postorder traversal?
Preorder → ABCEIFJDGHKL
Inorder → EICFJBGDKHLA
Which of the following is the correct postorder traversal?
- EIFJCKGLHDBA
- FCGKLHDBUAE
- FCGKLHDBAEIJ
- IEJFCGKLHDBA
Q59. How many rotations are required during the construction of an AVL tree if the following elements are inserted in the given sequence?
35, 50, 40, 25, 30, 60, 78, 20, 28
35, 50, 40, 25, 30, 60, 78, 20, 28
- 2 left rotations, 2 right rotations
- 2 left rotations, 3 right rotations
- 3 left rotations, 2 right rotations
- 3 left rotations, 1 right rotation
Q73. Consider the following undirected graph with vertices a, b, c, f, g, h and edges:
a–b, a–c, a–f, b–c, b–f, b–h, c–g, f–g, f–h, g–h
The following depth-first search (DFS) sequences are given:
(A) abcghf
(B) abfchg
(C) abfhgc
(D) afghbc
Which of the following is correct?
a–b, a–c, a–f, b–c, b–f, b–h, c–g, f–g, f–h, g–h
The following depth-first search (DFS) sequences are given:
(A) abcghf
(B) abfchg
(C) abfhgc
(D) afghbc
Which of the following is correct?
- (A), (B) and (D) only
- (A), (B), (C) and (D)
- (B), (C) and (D) only
- (A), (C) and (D) only
Q85. Consider the following algorithms and their running times. Which one of the following is correct?
| List I | List II |
|---|---|
| A. Breadth-first search | I. Θ(V + E) |
| B. Rabin–Karp algorithm | II. O(V + E) |
| C. Depth-first search | III. Θ((n − m + 1)m) |
| D. Heap sort (worst case) | IV. O(n²) |
| E. Quick sort (worst case) | V. O(n log n) |
- A-III, B-II, C-I, D-IV, E-V
- A-II, B-III, C-I, D-IV, E-V
- A-II, B-III, C-I, D-V, E-IV
- A-III, B-I, C-II, D-IV, E-V
Q87. Consider the following statements on approximation algorithms:
Statement I: APPROX-VERTEX-COVER is a polynomial-time 2-approximation algorithm.
Statement II: APPROX-TSP-TOUR is a polynomial-time 3-approximation algorithm for the travelling salesman problem with the triangle inequality.
Which of the following is correct?
Statement I: APPROX-VERTEX-COVER is a polynomial-time 2-approximation algorithm.
Statement II: APPROX-TSP-TOUR is a polynomial-time 3-approximation algorithm for the travelling salesman problem with the triangle inequality.
Which of the following is correct?
- Statement I true and Statement II false
- Statement I and Statement II true
- Statement I false and Statement II true
- Statement I and Statement II false