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.
- The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is :
- The following multithreaded algorithm computes transpose of a matrix in parallel : p Trans (X, Y, N) if N = 1 ← then Y[1,1] X[1,1] else partition X into four (N/2) x (N/2) X X X X submatrices 11, 12, 21, 22 partition Y…
- Consider the following statements : (a) The running time of dynamic programming θ(ρ) ρ algorithm is alway where is number of subproblems. (b) When a recurrence relation has cyclic dependency, it is impossible to use tha…
- With preconditions p ≥ 1 and n ≥ 0 (no overflow): int x = p; int k = n; int m = 1; while (k != 0) { if (k is odd) m = m * x; x = x * x; k = floor(k / 2); } The loop invariant is m·xᵏ = pⁿ and k ≥ 0. Which must be true a…
- Match List I with List II. List I: (a) Prim's algorithm, (b) Dijkstra's algorithm, (c) Faster all-pairs shortest path, (d) Edmonds-Karp algorithm. List II: (i) O(V³ lg V), (ii) O(VE²), (iii) O(E lg V), (iv) O(V²).
- There are many sorting algorithms based on comparison. The running time of heapsort O(n lg n) P Q algorithm is . Like , but unlike , (P, Q) heapsort sorts in place where is equal to
- Which of the following is best running time to n n2 − 1 sort integers in the range 0 to ?
- Which of the following is application of depth- first search?
- Consider double hashing of the form h(k, i) = (h (k) + ih (k)) mod m 1 2 h (k) = k mod m where 1 h (k) = 1 + (k mod n) 2 n = m − 1 m = 701 where and k = 123456 For , what is the difference between first and second probe…
- Consider the complexity class as the ¯¯¯ L ∈ NP set of languages L such that , and the following two statements : S : P ⊆ CO − NP 1 S NP ≠ CO − NP P ≠ NP 2 : If , then Which of the following is/are correct? S
- Consider the following steps : S 1 : Characterize the structure of an optimal solution S 2 : Compute the value of an optimal solution in bottom-up fashion Which of the step(s) is/are common to both dynamic programming a…
- Consider the following properties with respect to G = (V , E) a flow network in which a flow is a f : V × V → R real-valued function : P : For all u, v ∈ V , f(u, v) = −f(v, u) 1 P : ∑ f(u, v) = 0 for all u ∈ V 2 v∈V Wh…
- Consider the graph shown below : Use Kruskal's algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is
- The solution of recurrence relation : T(n) = 2T(sqrt(n)) + lg(n) is
- The elements 42,25,30,40,22,35,26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as
- Consider two sequences X = ⟨0, 1, 2, 1, 3, 0, 1⟩ and Y = ⟨1, 3, 2, 0, 1, 0⟩. The length of the longest common subsequence of X and Y is
- Consider the postfix expression with single-digit operands: 6 2 3 * / 4 2 * + 6 8 * −. The top two elements of the stack after the second * is evaluated are
- A binary search tree is constructed by inserting the following numbers in order : 60,25,72,15,30,68,101,13,18,47,70,34 The number of nodes in the left subtree is
- In a ternary tree, the number of internal nodes of degree 1,2 , and 3 is 4,3 , and 3 respectively. The number of leaf nodes in the ternary tree is
- Match List I with List II and choose the correct answer from the code given below. Where V and E are the number of vertices and edges in the graph respectively.
- A K-colouring of an undirected graph G = (V, E) is a function c : V → {0, 1, …, K − 1} such that c(u) ≠ c(v) for every edge (u, v) ∈ E. For a 2-colourable graph G, which of the following is not correct?
- Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list?
- The second smallest of n elements can be found with ____________ comparisons in the worst case.
- Consider the pseudo-code fragment, where m is a non-negative integer that has been initialized: p = 0; k = 0; while (k < m) p = p + 2^k; k = k + 1; end while Which of the following is a loop invariant for the while stat…
- The solution of the recurrence relation T(m) = T(3 m/4) + 1 is :
- Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are _________ and _________ respectively. (Root is at level 0).
- Which of the following algorithms solves the single-source shortest paths ?
- A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of :
- A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves :
- Match the following with respect to algorithm paradigms :