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.
- Arrange the following prefix expressions by value in increasing order: 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
- Which of the following are true for a complete binary tree? A. It has always 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 2 n-1 vertices, it has…
- Which of the following is TRUE?
- 2-3-4 trees are B - trees of order 4. They are isometric of trees.
- Match List I with List II. List I: A. Parallel FFT, B. Iterative FFT, C. Evaluation of a polynomial at n points by Horner's method, D. Product of two polynomials represented in point-value form. List II: I. Θ(n²), II. Θ…
- 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…
- A. If some NP-complete problem P is in 𝒫, then 𝒫 = 𝒩𝒫. B. TSP is in 𝒩𝒫. C. SAT is in 𝒩𝒫. D. The Hamiltonian circuit problem is not NP-complete. Which are correct?
- Suppose a circular queue of capacity n-1 elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variable respectively.…
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: The AVL trees are more balanced as compared to Red Black trees, but they may cause more rotations during…
- Consider a hash table of size seven with starting (6x + 3) mod 4 index zero and a hash function . Assuming the hash table is initially empty. Which of the following is the content of the table when 1, 3, 8, 10, 5 the se…
- Match List I with List II
- Given below are two statements: Statement I: If f and g are two functions and f = O(g) g ≠ o(f) but , we say that the growth rate of g is smaller than that of f Statement II: The class of all decision problems decided b…
- 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 doubly linked list using only one pointer with every node. Reason R: By storing…
- Given six weights 4, 15, 25, 5, 8, 16, construct a 2-tree (binary tree). What is the minimum weighted path length?
- Consider: A. The number of labelled binary trees possible with n nodes is (2n)!/(n + 1)!. B. The number of binary search trees possible with n nodes is (2n)!/((n + 1)! n!). C. The number of unlabelled binary trees possi…
- Which of the following are correct about Hamiltonian problems? 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. C. The Hami…
- For matrix multiplication with a 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 II
- Match List I with List II
- What is the maximum value of items you can carry if maximum weight allowed is 25 with a fractional knapsack?
- If new item is added to the list, total items is 8 and capacity is 25 , then the best-case time of fractional knapsack for this case is _____
- Which of the following statements is correct for a knapsack?
- How many different binary trees are possible with ' n ' nodes?
- Let n be a positive integer and f(n) = 0 if n = 1, and f(n) = f(⌊n/2⌋) + 1 if n > 1. What is f(25), and what does the function compute?
- Given the FFT we can have ______ time procedure for multiplying two polynomials A(x) Q 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 of AND, OR and NOT gates, is it satisfiable (is there an input for which the output is 1)? 1. Circuit-SAT belongs to NP. 2. Circuit-SAT is at least a…
- 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 infix and postfix is the same…
- Match List I with List II
- Given the graph below one of the following edges cannot be added in that order to find a minimum spanning tree algorithm. Q I. a-b II. d-f III. b-f IV. d-c V. d-e
- Statement 1: su Given a graph G=(V, E) in which each vertex v € V has an associated positive weight w(v), we can Q use linear programming to find the lower bound on the weight of the minimum-weight vertex cover. Stateme…