Data Structures and Algorithms – Previous Year Questions
215 questions from past UGC NET Paper 2 – Computer Science papers, each with the correct answer. Open any question for its explanation.
Topic-wise mock tests
- Which of the following description(s) is/are true? A. Red-Black Tree – guarantees worst case O(log n) time for search, insert & delete. B. Trie – used for efficient prefix-based searches. C. AVL Tree – self-balancing bi…
- Match List I with List IIList I List II A. Insertion Sort I. O(log n) B. Binary Search II. O(n²) C. Quick Sort III. O(n) D. Selection Sort IV. O(n log n)
- 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 corre…
- 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:
- ______ 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.
- Match List I with List IIList 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 s…
- 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…
- 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 s…
- Which of the following is NOT a palindromic subsequence of the string "ababcdabba"?
- Which of the following is TRUE?
- What is the result of evaluating the postfix expression "4 3 * 2 5 * + 8 -"?
- Which data structure is typically used to implement a hash table?
- Which collision resolution technique involves maintaining a linked list of collided keys?
- Consider the following functions: f(n) = 3n√n, g(n) = 2√n log₂ n, h(n) = n!. Which of the following is true?
- 2-3-4 trees are B-trees of order 4. They are isometric to ______ trees.
- 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…
- Match List I with List IIList 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 f…
- 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 sufficien…
- 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…
- 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
- 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…
- 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…
- 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 inser…
- Match List I with List IIList 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…
- 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(…
- 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 s…
- For each function below, let n be the least integer such that f(x) is O(xⁿ). Arrange the functions in increasing order of n: A. f(x) = 3x³ + (log x)⁴ B. f(x) = (x⁵ + x² + 1)/(x³ + 1) C. f(x) = (x³ + x² + 1)/(x² + 1) D.…
- f(n) = a·f(n/b) + g(n) is a divide-and-conquer recurrence. Match the algorithms in List I with their recurrences in List II.List I List II A. Binary Search I. f(n) = 7f(n/2) + 15n²/4 B. Find maximum and minimum of a seq…
- The height of a binary search tree built by inserting the words banana, peach, apple, pear, coconut, mango and papaya (in this order, alphabetical comparison) is:
- How much time does an algorithm using 2⁵⁰ bit operations need if each bit operation takes 2⁻³⁸ seconds?