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.
- A lower-triangular sparse matrix is one:
- Arrange the following prefix expressions in increasing order of their values: A. + − * 2 / 8 4 3 2 B. ↑ − * 3 3 * 4 2 5 C. + − ↑ 3 2 ↑ 2 3 / 6 − 4 2 D. * + 3 + 3 ↑ 3 + 1 1 3 Choose the correct answer from the options gi…
- Which of the following are true for a complete (full) binary tree? A. It always has an odd number of vertices. B. With i internal vertices, it has i + 1 leaves. C. With l leaves, it has 2l − 1 vertices. D. With 2n − 1 v…
- In a ______ the left and right subtrees of some node differ in height by more than one.
- FFTs are ______ techniques used to encode digital video and audio information and help analyse the signal in the ____ domain.
- 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?
- 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 ______
- 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…
- 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…
- 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…
- Match List I with List IIList 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
- Match List I with List IIList 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
- 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:
- Find the optimal solution of the fractional knapsack problem when the maximum capacity is 15.
- What is the maximum value of the items you can carry if the maximum weight allowed is 25 (fractional knapsack)?
- 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 ______
- The most efficient solution to the fractional knapsack problem with maximum capacity 15 is obtained using ___
- Which of the following statements about the knapsack problem is correct?
- How many different binary trees are possible with n nodes?
- Let n denote a positive integer. A function f is defined as f(n) = 0, if n = 1 f(n) = f(⌊n/2⌋) + 1, if n > 1 What is f(25), and what does this function find?
- Given the FFT, we can have a ______ time procedure for multiplying two polynomials A(x) and B(x) of degree bound n, where input and output representations are in coefficient form, assuming n is a power of 2.
- Circuit satisfiability problem: given a Boolean combinational circuit composed of AND, OR and NOT gates, is it satisfiable? A one-output Boolean combinational circuit is satisfiable if for some input the output is 1. 1.…
- Given the expression (A + B * D) / (E − F) + G: 1. The prefix notation is + / + A * D B − E F G 2. The prefix expression is the reverse of the postfix expression. 3. The order of operands in the infix expression and pos…
- Match List I with List II. Choose the correct answer from the options given below:List I List II a. Dijkstra's algorithm I. Calculates path matrix b. Prim's algorithm II. Stores minimum cost edge c. Warshall's algorithm…
- For the weighted graph below, which of the following orders of adding edges can NOT be produced by a minimum spanning tree algorithm? Edges (weight): a–b (1), d–f (1), b–f (2), c–d (2), b–c (3), d–e (3), b–d (4), c–e (4…
- Statement I: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to find a lower bound on the weight of the minimum-weight vertex cover. Statement II…
- Assume that f(n), g(n) and h(n) are asymptotically positive. Which of the following is correct?
- The solution of the recurrence relation T(n) = 3T(n/4) + n log n is
- The number of nodes of height h in any n-element heap is at most
- Consider a B-tree of height h and minimum degree t ≥ 2 that contains n keys, n ≥ 1. Which of the following is correct?