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.
- Which algorithm design approach is used in the quick sort algorithm?
- 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…
- Consider the traversals of a tree: Preorder → ABCEIFJDGHKL Inorder → EICFJBGDKHLA Which of the following is the correct postorder traversal?
- 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
- 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) ab…
- 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 −…
- 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 algorith…
- Which of the following is used to determine the cost performance index?
- Software project manager is responsible for the following task: (A) Project planning (B) Project status tracking (C) Resources management (D) Risk management (E) Project delivery within time & budget
- Fill in the blanks: "An ________ chart is a project schedule representation that presents the project plan as a directed graph. The critical path is the ________ sequence of ________ tasks and it defines the project ___…
- Which of the following are the primary objectives of risk monitoring in software project tracking? P: To assess whether predicted risks do, in fact, occur. Q: To ensure that risk aversion steps defined for the risk are…
- Which one of the following is a highly associated activity of project planning? (1) Keep track of the project progress. (2) Compare actual and planned progress and costs. (3) Identify the activities, milestones and deli…
- Which of the following trees are height balanced? A. Binary Search Tree B. AVL Tree C. Red-Black Tree D. B Tree
- Which of the following algorithms use Greedy strategy? A. Dijkstra's algorithm B. Kruskal's algorithm C. Huffman coding D. Bellman-Ford algorithm
- Match List I with List II
- Match List I with List II
- Considering the binary tree shown (A has children B and C; C has children D and E; E has right child F; F has children G and H), what will be the inorder traversal?
- Match the LIST-I with LIST-II
- Which of the following algorithms are based on the Breadth First Search (BFS) ? A. Prim's algorithms B. Kruskal algorithms C. Dijkstra algorithms D. Greedy algorithms E. Dynamic Programming
- Which of the following is the solution of the recurrence T(n) = T(2n/3) + 1?
- Match the LIST-I with LIST-II
- 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
- Select the Sorting Algorithms that are stable. (A) Quick Sort (B) Bubble Sort (C) Insertion Sort (D) Merge Sort (E) Shell Sort
- Match List - I with List - II.
- Match List I (recurrence) with List II (complexity). List I: (A) T(n) = 2T(n/2) + n, (B) T(n) = T(n/2) + 1, (C) T(n) = 2T(n/2) + 1, (D) T(n) = T(n−1) + n. List II: (I) T(n) = Θ(n log n) (exact), (II) O(n²), (III) T(n) =…
- Let n be the least integer such that f(x) is O(xⁿ). Arrange the following 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(x) = (x² + 5…
- Match List - I with List - II. f(n) = a f(n / b) + g(n) is a divide-and- conquer recurrence relation for the Listed-I algorithms, match their recurrence in Listed-II.
- The height of a binary search tree for the words banana, peach, apple, pear, coconut, mango and papaya using alphabetical order is :
- How much time does an algorithm using 2⁵⁰ bit operations need if each bit operation takes 2⁻³⁸ seconds?
- A lower-triangular sparse matrix is one :