UGC NET Paper 2 Computer Science – Unit 7: Data Structures and Algorithms PYQ (June 2023)

Q2. Consider the following statements about the heap sort algorithm:
A. The MAX-HEAPIFY procedure, which runs in O(lg n) time, is the key to maintaining the max-heap property.
B. The BUILD-MAX-HEAP procedure, which runs in O(lg n) time, produces a max-heap from an unordered input array.
C. The MAX-HEAP-INSERT procedure, which runs in O(lg n) time, implements the insertion operation.
D. The HEAP-INCREASE-KEY procedure runs in O(n lg n) time to set the key of a new node to its correct value.
Choose the correct answer from the options given below:

Q10. Match List I with List II

List I	List II
A. Parallel FFT	I. Θ(n²)
B. Iterative FFT	II. Θ(n)
C. Evaluation of polynomial at n points by Horner method	III. Θ(lg n)
D. Product of two polynomials represented in point-value form	IV. Θ(n lg n)

Q12. Let f(n) and g(n) be asymptotically positive functions.
Statement I: f(n) ≥ 1 and f(n) = O(g(n)) ⇒ g(n) = Ω(f(n)).
Statement II: f(n) = O(g(n)) ⇒ lg(f(n)) = O(lg(g(n))), where lg(g(n)) ≥ 1 and f(n) ≥ 1 for all sufficiently large n.

Q16. Consider the following statements:
A. If some NP-complete problem is in P, then P = NP.
B. TSP is in NP.
C. SAT is in NP.
D. The Hamiltonian circuit problem is not NP-complete.
Choose the correct answer from the options given below:

Q17. A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted into this index, the maximum number of nodes that could be newly created in the process is

Q18. Suppose a circular queue of capacity n − 1 elements is implemented with an array of n elements. Insertion and deletion use REAR and FRONT as array index variables respectively. Initially REAR = FRONT = 0. The conditions to detect queue empty and queue full are

Q21. Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.
Assertion A: AVL trees are more balanced than red-black trees, but they may cause more rotations during insertion and deletion.
Reason R: A red-black tree with n nodes has height greater than 2 log₂(n + 1), and an AVL tree with n nodes has height less than log_φ(√5 (n + 2)) − 2 (where φ is the golden ratio).

Q44. Consider a hash table of size 7 with starting index 0 and hash function (6x + 3) mod 4. Assuming the table is initially empty, which of the following is the content of the table when the sequence 1, 3, 8, 10, 5 is inserted using closed hashing (linear probing)? Here '_' denotes an empty location.

Q85. Match List I with List II

List I	List II
A. Running time of a straightforward recursive method to compute the nth Fibonacci number Fₙ	I. O(n²)
B. Running time to compute Fₙ using memoization	II. O(log n)
C. Running time to compute Fₙ using only integer addition and multiplication	III. O(n)
D. Running time to determine an optimal bitonic tour	IV. Θ(φⁿ)

Q86. Statement I: If f and g are two functions and f = O(g) but g ≠ o(f), we say that the growth rate of g is smaller than that of f.
Statement II: The class of all decision problems decided by a TM in exponential time is O(2ᵏ), k being a constant.

Q89. Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.
Assertion A: It is possible to create a doubly linked list using only one pointer field in every node.
Reason R: By storing the XOR of the addresses of the previous and next nodes.