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 solution of the recurrence T(n) = 3T(n/4) + n log n is
- Consider a B-tree of height h and minimum degree t ≥ 2 containing n keys, n ≥ 1. Which is correct?
- How many rotations are required during the construction of an AVL tree if the elements 35, 50, 40, 25, 30, 60, 78, 20, 28 are added in this sequence?
- For the graph shown, the following depth-first search sequences are given: (A) abcghf (B) abfchg (C) abfhgc (D) afghbc. Which of the following is correct?
- Match each algorithm with its running time. (A) Breadth-first search, (B) Rabin–Karp algorithm, (C) Depth-first search, (D) Heap sort (worst case), (E) Quick sort (worst case). Times: (I) Θ(V + E), (II) O(V + E), (III)…
- Statement I: Vertex cover has a polynomial-time 2-approximation algorithm. Statement II: TSP-tour is a polynomial-time 3-approximation algorithm for the travelling salesman problem with the triangle inequality. Which is…
- The postfix form of the expression (A + B) * (C * D - E ) * F /G is _______
- A double‐ended queue (dequeue) supports adding and removing items from both the ends of the queue. The operations supported by dequeue are AddFront(adding item to front of the queue), AddRear(adding item to the rear of…
- Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ____ time.
- A data structure is required for storing a set of integers such that each of the following O(log n) operations can be done in time, where n is the number of elements in the set. Deletion of the smallest element Insertio…
- Consider the following graph. Among the following sequences I. a b e g h f II. a b f e h g III. a b f h g e IV. a f g h b e Which are depth first traversals of the above graph?
- Which of the given options provides the increasing order of asymptotic complexity of f1, f2, f3 f4 functions and ? f1(n) = 2n A. f2(n) = n3/2 B. f3(n) = n log n C. f4(n) = nlog n D.
- A hash function h(key) = key mod 7 with linear probing is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed 0 to 6. What will be the location of key 18?
- Match each graph algorithm with its time complexity (n vertices, m edges). List I: A. Bellman-Ford, B. Kruskal's algorithm, C. Floyd-Warshall, D. Topological sorting. List II: I. O(m log n), II. O(n³), III. O(n·m), IV.…
- The reverse Polish notation of the infix expression [A * {B + C * (D + E)}] / {F * (G + H)} is
- With preconditions a > 1 and a < b (no overflow): int x = 0; int p = 1; while (p < b) { p = p * a; x = x + 1; } When the loop ends, x in terms of a and b is
- A complete -ary tree is a tree in which each n I node has children or no children. Let be the L number of internal nodes and be the number n L = 41 of leaves in a complete -ary tree. If , I = 10 n and , What is the valu…
- In a binary max heap containing numbers, the smallest element can be found in ____ time.
- If algorithm A and another algorithm B take −− log (n) √n 2 and microseconds, respectively, to n solve a problem, then the largest size of a problem these algorithms can solve, respectively, in one second are ___ and __…
- Let be a directed graph whose vertex set is the set of numbers from 1 to 100 . There is an i j edge from a vertex to a vertex if and only if j = i + 1 j = 3i either or . The minimum G number of edges in a path in from v…
- The running time of an algorithm is O(g(n)) if and only if: (A) its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)). (B) its worst-case running time is Ω(g(n)) and its best-case running time…
- Match List I with List II. List I: A. Topological sort of a DAG, B. Kruskal's MST algorithm, C. Bellman-Ford single-source shortest path, D. Floyd-Warshall all-pairs shortest path. List II: I. O(V + E), II. O(VE), III.…
- Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node a, which one of the following sequences of edges represents a possible order in which the edges would b…
- G T Let be a simple undirected graph, D be a DFS G T tree on , and B be the BFS tree on G. Consider the following statements. G Statement I : No edge of is a cross with T respect to D (u, v) G u Statement II : For every…
- The weight of minimum spanning tree in graph G, calculated using Kruskal's algorithm is :
- What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume that all insertions can be accomodated.
- In a B-Tree, each node represents a disk block. Suppose one block holds 8192 bytes. Each key uses 32 bytes. In a B-tree of order M there are M - 1 keys. Since each branch is on another disk block, we assume a branch is…
- Give tight bounds for T(n) = 4T(√n) + lg²n, with T(n) constant for n ≤ 2.
- Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]= 29, d[u]= 15, w[u,v]=12. What is the updated value of d[v] based on current information?
- When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?