UGC NET Computer Science Data Structures and Algorithms Previous Year Questions (PYQs)
Practise 143 Data Structures and Algorithms questions asked in UGC NET Computer Science from 2018–2026. Questions cover Arrays, Trees, Graphs, Hashing, Sorting and searching algorithms with complexity analysis and Asymptotic notation and solving recurrence relations. Every question is shown with its options and the correct answer, free to read.
143 PYQs2018–2026Answers includedFree
Practise Data Structures and Algorithms as timed sets
Focused 10-question sets with instant scoring, explanations, and weak-area analysis.
What is the maximum number of nodes that can be inserted in the AVL tree without changing its height?
AVL tree with nodes 60, 50, 70, and 80.
A2
B4
C3
D5
Answer:(C) 3
Explanation
The displayed tree has height 2 and currently contains 4 nodes. A binary tree of height 2 can contain at most 2³ − 1 = 7 nodes, so 7 − 4 = 3 additional nodes can be inserted without increasing its height.
A. Merge sort B. Binary search C. Quick sort D. Search in an unsorted array
I. n² II. n log n III. n IV. log n
AA-I, B-IV, C-II, D-III
BA-I, B-II, C-III, D-IV
CA-II, B-I, C-III, D-IV
DA-II, B-IV, C-I, D-III
Answer:(D) A-II, B-IV, C-I, D-III
Explanation
Merge sort has O(n log n) complexity, binary search has O(log n), quicksort has O(n²) in the worst case, and searching an unsorted array has O(n). This produces A-II, B-IV, C-I, D-III.
The number of leaf nodes in a full 4-ary rooted tree with n nodes is:
An/2
B(2n − 1)/4
C(n + 1)/4
D(3n + 1)/4
Answer:(D) (3n + 1)/4
Explanation
If I is the number of internal nodes, a full 4-ary tree has n = 4I + 1. Its leaves are L = n − I = 3I + 1 = (3n + 1)/4. The other formulas do not satisfy this relation for a full 4-ary tree.
A problem of size n requires n² bit operations. What is the largest instance that can be solved in one second if each bit operation takes 10⁻⁹ second?
A10⁹
B3.16 × 10⁴
C3.96 × 10⁷
D2 × 10⁹
Answer:(B) 3.16 × 10⁴
Explanation
One second permits 10⁹ operations. Solving n² = 10⁹ gives n = √10⁹ ≈ 3.16 × 10⁴. The larger choices confuse the operation budget with the square root of that budget.
A. Stack
B. Queue
C. Linked list
D. Binary search tree
List-I
List-II
A. Stack B. Queue C. Linked list D. Binary search tree
I. FIFO II. LIFO III. Ordered children IV. Sequentially linked dynamic nodes
AA-IV, B-I, C-II, D-III
BA-II, B-I, C-IV, D-III
CA-III, B-IV, C-I, D-II
DA-II, B-I, C-III, D-IV
Answer:(B) A-II, B-I, C-IV, D-III
Explanation
A stack follows LIFO (II), a queue follows FIFO (I), a linked list has dynamically sized sequentially linked nodes (IV), and a binary search tree has ordered child nodes (III). Hence A-II, B-I, C-IV, D-III.
In the worst case, the smallest number of comparisons required by a comparison-based sorting algorithm is:
A⌈log n⌉
B⌈log₂(n!)⌉
C⌈log n(n − 1)⌉
Dn
Answer:(B) ⌈log₂(n!)⌉
Explanation
A comparison sort must distinguish among n! possible input orders. Its decision tree therefore needs at least n! leaves, so its worst-case height is at least ⌈log₂(n!)⌉ comparisons.
What is the height of the binary search tree formed by inserting 40, 60, 50, 37, 52, 15, 8, 22 in that order?
A4
B3
C2
D1
Answer:(B) 3
Explanation
The longest root-to-leaf path is 40 → 37 → 15 → 8 (or 40 → 60 → 50 → 52). It has three edges, so under the usual edge-height definition the tree height is 3.
How will the shown min-heap appear after inserting key 32?
Original min-heap and the four candidate heaps after insertion.
AOption 1
BOption 2
COption 3
DOption 4
Answer:(C) Option 3
Explanation
The new key is first placed at the next open leaf, as the left child of 40. Since 32 < 40, it swaps once with 40; it then stops because 32 > its new parent 10. This is exactly the heap shown in option 3.
If f(n) = θ(g(n)) and g(n) = O(h(n)), which statement is true?
Af(n) = O(h(n))
Bf(n) = θ(h(n))
Ch(n) = O(f(n))
Dh(n) = θ(f(n))
Answer:(A) f(n) = O(h(n))
Explanation
f(n) = θ(g(n)) implies f(n) = O(g(n)). Combining this with g(n) = O(h(n)) and transitivity of big-O gives f(n) = O(h(n)). The information does not establish a reverse bound, so the theta claims need not hold.
A BST is formed by inserting Mathematics, Physics, Geography, Zoology, Metrology, Geology, Psychology, and Chemistry in dictionary order. Arrange these words in increasing order of their tree level:
A. Mathematics
B. Zoology
C. Psychology
D. Physics
AA, D, C, B
BA, C, D, B
CA, D, B, C
DC, B, D, A
Answer:(C) A, D, B, C
Explanation
Mathematics is the root (level 0). Physics is its right child (level 1). Zoology is to the right of Physics (level 2), while Psychology lies to the left of Zoology (level 3). Thus the required increasing-level order is A, D, B, C.
In open addressing, how are collisions typically resolved?
ABy probing to find the next available table slot
BBy creating a linked list at the collision point
CBy rehashing the entire table
DBy storing colliding elements in a separate array
Answer:(A) By probing to find the next available table slot
Explanation
Open addressing stores every key in the hash table itself. On a collision it probes alternative positions, for example by linear probing, quadratic probing, or double hashing, until an unused slot is found.
The inorder and preorder traversal of a binary tree are d, b, e, a, f, c, g and a, b, d, e, c, f, g respectively. The postorder traversal of the binary tree is
Ad, e, b, f, g, c, a
Be, d, b, g, f, c, a
Ce, d, b, f, g, c, a
Dd, e, f, g, b, c, a
Answer:(A) d, e, b, f, g, c, a
Explanation
The first element of a preorder sequence is always the tree's root, so a is the root, and its position in the inorder sequence splits the tree into a left subtree {d, b, e} and a right subtree {f, c, g}.
Within the left subtree, preorder b, d, e makes b the root, and inorder d, b, e places d as its left child and e as its right child.
Within the right subtree, preorder c, f, g makes c the root, and inorder f, c, g places f as its left child and g as its right child.
Postorder visits left, then right, then the root at every level, giving d, e, b for the left subtree, f, g, c for the right subtree, and a last, so the full sequence is d, e, b, f, g, c, a.
How many comparisons are required in the worst case to find the second smallest element of a list of n elements?
An + ⌈log n⌉ − 1
Bn + ⌈log n⌉
C⌈log n⌉
Dn + ⌈log n⌉ − 2
Answer:(D) n + ⌈log n⌉ − 2
Explanation
Finding the second smallest efficiently uses a tournament (knockout) method. Comparing elements in a single-elimination tournament to find the minimum takes n − 1 comparisons, and during that tournament the eventual minimum is directly compared against exactly ⌈log₂ n⌉ other elements, one at each round it wins.
The second-smallest element must be among those ⌈log₂ n⌉ elements that lost directly to the minimum, so finding the smallest among that shortlist takes ⌈log₂ n⌉ − 1 further comparisons.
(n − 1) + (⌈log₂ n⌉ − 1) = n + ⌈log n⌉ − 2, which is the worst-case comparison count.
Each prefix expression must be evaluated inside out, applying every operator to its two operands as they resolve.
Expression A: / 8 4 = 2, then * 2 2 = 4, then − 4 3 = 1. So A = 1.
Expression B: * 3 6 = 18, * 4 2 = 8, then − 18 8 = 10, then ↑ 10 5 = 100000. So B = 100000.
Expression C: ↑ 3 2 = 9 and ↑ 2 3 = 8, so − 9 8 = 1. Also − 4 2 = 2, so / 6 2 = 3. Adding the two parts, + 1 3 = 4. So C = 4.
Expression D: + 1 1 = 2, then ↑ 3 2 = 9, then + 3 9 = 12, then + 3 12 = 15, then * 15 3 = 45. So D = 45.
Ranking the four values 1, 4, 45 and 100000 from smallest to largest gives A (1), C (4), D (45), B (100000), so A, C, D, B is the correct ascending order.
Which of the following statements about DFS are correct?
A. It can detect cycles in a graph.
B. It can be used to find connected components.
C. It works for both directed and undirected graphs.
D. Guarantees shortest path in unweighted graphs.
AA, B, C Only
BA, B, C, D
CC, D Only
DB, C Only
Answer:(A) A, B, C Only
Explanation
Depth-first search explores as far as possible along each branch before backtracking, which gives it several well-known properties.
A. It can detect cycles in a graph. — correct. A back edge to an ancestor still on the recursion stack signals a cycle in both directed and undirected graphs.
B. It can be used to find connected components. — correct. Restarting DFS from every unvisited vertex and grouping vertices reached in each run identifies the connected components.
C. It works for both directed and undirected graphs. — correct. The traversal only needs an adjacency structure, so it applies to either graph type with minor bookkeeping differences.
D. Guarantees shortest path in unweighted graphs. — incorrect. DFS can return a much longer path than necessary because it dives deep before exploring nearby vertices, so breadth-first search, not DFS, guarantees the shortest path in an unweighted graph.
Assertion (A): Kruskal's algorithm and Prim's algorithm always produce a minimum spanning tree (MST).
Reason (R): Every connected graph has a unique MST.
ABoth A and R are correct and R is the correct explanation of A
BBoth A and R are correct but R is NOT the correct explanation of A
CA is correct but R is not correct
DA is not correct but R is correct
Answer:(C) A is correct but R is not correct
Explanation
Both Kruskal's algorithm and Prim's algorithm are greedy algorithms proven to always construct a minimum spanning tree of a connected, weighted graph, so Assertion A is correct.
Reason R is false. A connected graph has a unique MST only when all edge weights are distinct. When two or more edges share the same weight, a graph can have multiple different spanning trees that all achieve the same minimum total weight, so the MST is not guaranteed to be unique.
Which of the following is the correct order of increasing time complexity of the given algorithms?
A. Tower of Hanoi with n disks
B. Binary search given n sorted numbers
C. Heap sort given n numbers, worst case
D. Addition of two n × n matrices
AB, C, D, A
BA, B, C, D
CD, C, B, A
DC, A, D, B
Answer:(A) B, C, D, A
Explanation
Each algorithm has a standard, well-known time complexity.
Binary search on n sorted numbers — O(log n).
Heap sort, worst case — O(n log n).
Addition of two n × n matrices — O(n²), since every one of the n² entries needs one addition.
Tower of Hanoi with n disks — O(2ⁿ), since the number of moves doubles with each additional disk.
Ordering these by growth rate from smallest to largest gives log n < n log n < n² < 2ⁿ, so the increasing order is Binary search, Heap sort, Matrix addition, Tower of Hanoi — that is, B, C, D, A.
Which of the following is the correct solution of the given recurrence relation?
T(n) = 3T(n/4) + n log n
Aθ(n log n)
Bθ(n² log n)
Cθ(n(log n)²)
Dθ(n log log n)
Answer:(A) θ(n log n)
Explanation
The Master theorem applies directly to T(n) = 3T(n/4) + n log n, with a = 3, b = 4 and f(n) = n log n.
Compare f(n) against n^(log_b a): log_4 3 ≈ 0.7925, so n^(log_4 3) ≈ n^0.7925.
Since n log n grows polynomially faster than n^0.7925 for large n, this falls under Master theorem Case 3.
Case 3 also needs the regularity condition a·f(n/b) ≤ c·f(n) for some c < 1. Checking it: 3·(n/4)log(n/4) = 0.75·n·log(n/4), which stays below 0.75·n log n for large n, so the condition holds.
Arrange the following algorithms from the most efficient to the least efficient based on their time complexity.
A. Kruskal's Algorithm
B. Breadth First Search Algorithm
C. Bellman-Ford Algorithm
D. Dijkstra's Algorithm
E. Edmonds-Karp Algorithm
AB, D, A, E, C
BE, C, A, D, B
CB, D, A, C, E
DB, C, A, E, D
Answer:(C) B, D, A, C, E
Explanation
Comparing the standard asymptotic complexities for a graph with V vertices and E edges ranks these five algorithms by growth rate.
Breadth First Search (B) runs in O(V + E), the fastest of the five since it visits each vertex and edge only once.
Dijkstra's Algorithm (D) with a binary heap runs in O(E log V), adding a logarithmic factor for priority-queue operations.
Kruskal's Algorithm (A) runs in O(E log E), comparable to O(E log V) but with a heavier constant from sorting all edges.
Bellman-Ford (C) runs in O(VE), slower because it relaxes every edge across up to V-1 passes.
Edmonds-Karp (E) runs in O(VE²), the slowest here because it repeats a full BFS-based augmenting path search many times.
Ordering from most to least efficient gives B, D, A, C, E.
Match List-I (Algorithms) with List-II (Real-world applications).
List-I
List-II
A. Dijkstra's Algorithm
I. GPS route finding
B. Huffman Coding
II. Data compression
C. KMP String Matching
III. Text editor search function
D. Ford-Fulkerson
IV. Network bandwidth optimization
AA-II, B-IV, C-I, D-III
BA-I, B-II, C-III, D-IV
CA-IV, B-II, C-III, D-I
DA-IV, B-III, C-II, D-I
Answer:(B) A-I, B-II, C-III, D-IV
Explanation
Each algorithm listed is best known for one classic real-world application.
Dijkstra's Algorithm (A) finds shortest paths in a weighted graph, which is exactly how GPS navigation systems compute routes, so A pairs with I.
Huffman Coding (B) builds a variable-length prefix code that minimizes expected code length, which underlies lossless data compression, so B pairs with II.
KMP string matching (C) efficiently finds a pattern inside text without backtracking, which is the algorithm behind fast text editor search, so C pairs with III.
Ford-Fulkerson (D) computes maximum flow in a flow network, which models network bandwidth optimization problems, so D pairs with IV.
Which of the following are limitations of Greedy algorithms?
A. They always fail for NP hard problem.
B. They may not give the optimal solution for all problems.
C. They are faster than dynamic programming in most cases.
D. They make local choices without looking ahead.
AA, C Only
BB, C Only
CA, B, C, D
DB, D Only
Answer:(D) B, D Only
Explanation
A limitation is a genuine weakness of a technique, which rules out any statement that instead describes an advantage or makes an overstated claim.
A. They always fail for NP hard problem. — wrong, greedy algorithms do not always fail on NP-hard problems, they often give fast approximate solutions and in special cases even exact optimal ones.
B. They may not give the optimal solution for all problems. — correct, greedy algorithms optimize locally at each step, and that local view can miss the true global optimum, which is exactly why they are not always correct.
C. They are faster than dynamic programming in most cases. — wrong as a limitation, speed relative to dynamic programming is an advantage of greedy methods, not a weakness.
D. They make local choices without looking ahead. — correct, this short-sightedness is the structural reason greedy solutions can end up suboptimal.
Assertion (A): Depth first search can be used to perform a topological sort of a directed acyclic graph.
Reason (R): A topological sort of a directed acyclic graph with vertex set V and edge set E is a linear ordering of its vertices such that if the graph contains an edge from u to v, then u appears before v in the ordering.
ABoth A and R are correct and R is the correct explanation of A
BBoth A and R are correct but R is NOT the correct explanation of A
CA is correct but R is not correct
DA is not correct but R is correct
Answer:(A) Both A and R are correct and R is the correct explanation of A
Explanation
Running depth-first search on a directed acyclic graph and listing vertices in reverse order of their finishing times produces a valid topological sort, because a vertex finishes only after every vertex reachable from it has already finished, which places it before its successors once the order is reversed. Assertion A is correct.
Reason R correctly states the defining property of a topological sort, that for every edge (u, v), vertex u must appear before v in the ordering.
R is the correct explanation of A because it is precisely this ordering property, guaranteed by DFS finishing times on an acyclic graph, that the DFS-based method is exploited to produce.
For infix expression ((A+B)*D)↑(E-F), what is its equivalent postfix expression?
AA B + D * E F ↑
BA B + D * - ↑ E F
CA B + D E * F - ↑
DA B + D * E F - ↑
Answer:(D) A B + D * E F - ↑
Explanation
Postfix for the left operand ((A+B)*D) is A B + D *; postfix for (E-F) is E F -. Appending the exponent operator after the two complete operands gives A B + D * E F - ↑.
Which sequence is a longest common subsequence of {1, 2, 3, 2, 4, 1, 2} and {2, 4, 3, 1, 2, 1}?
A2, 1, 2, 3
B1, 3, 2, 1
C2, 3, 2, 1
D2, 3, 1, 2, 1
Answer:(C) 2, 3, 2, 1
Explanation
2, 3, 2, 1 appears in order in the first sequence at positions 2, 3, 4, 6 and in the second at positions 1, 3, 5, 6. Option D cannot occur in the first sequence because after 2, 3, 1, 2 there is no later 1.
Maintaining a graph in memory using its adjacency matrix is called:
AComplete representation
BLinked representation
CCircular representation
DSequential representation
Answer:(D) Sequential representation
Explanation
An adjacency matrix is a two-dimensional array whose entries are stored in contiguous, indexed locations. That array-based form is the sequential representation; linked representation instead uses adjacency lists.
To construct a Huffman tree, first create leaf nodes, build a priority queue, repeatedly combine the lowest-frequency nodes, and stop when the root is formed. Which sequence is correct?
AB, C, A, D
BD, B, A, C
CB, C, D, A
DC, A, B, D
Answer:(C) B, C, D, A
Explanation
Huffman coding begins with a leaf for every symbol and places those leaves in a min-priority queue. It repeatedly removes the two least-frequent nodes and combines them until one root remains, giving B, C, D, A.
In dynamic programming, the steps are characterizing an optimal solution, recursively defining its value, computing that value bottom-up, and constructing an optimal solution. Which sequence is correct?
AB, C, A, D
BB, A, C, D
CC, B, A, D
DC, B, D, A
Answer:(D) C, B, D, A
Explanation
First identify the optimal substructure, then write a recurrence for the optimal value. Compute the recurrence bottom-up and finally trace the stored choices to construct an optimal solution. This is C, B, D, A.
Which algorithms use a greedy strategy: Dijkstra's algorithm, Kruskal's algorithm, Huffman coding, and Bellman-Ford?
AA, B, and D only
BA, B, and C only
CC and D only
DA and D only
Answer:(B) A, B, and C only
Explanation
Dijkstra greedily fixes the smallest tentative distance, Kruskal greedily adds the cheapest edge that avoids a cycle, and Huffman greedily combines the two least-frequent nodes. Bellman-Ford repeatedly relaxes edges and is not a greedy algorithm.
Which trees are height balanced: binary search tree, AVL tree, red-black tree, and B-tree?
AA and D only
BA, B, and D only
CC and D only
DB and C only
Accepted answers:(C) C and D only, (D) B and C only
Explanation
An ordinary binary-search tree has no balancing guarantee. AVL trees enforce a strict height-balance condition, while red-black trees guarantee logarithmic height through black-height constraints. The term “height balanced” is also used broadly for B-trees because all leaves are at the same level; the supplied options therefore reflect two defensible conventions.
Match circular queue, priority queue, deque, and simple queue with their common applications.
List I
List II
A. Circular Queue
I. Print Queue
B. Priority Queue
II. CPU Scheduling
C. Double Ended Queue
III. Dijkstra algorithm
D. Simple Queue
IV. Palindrome checking
AA-II, B-III, C-I, D-IV
BA-II, B-III, C-IV, D-I
CA-III, B-II, C-I, D-IV
DA-IV, B-II, C-I, D-III
Answer:(B) A-II, B-III, C-IV, D-I
Explanation
A circular queue supports round-robin CPU scheduling, a priority queue supports Dijkstra's algorithm, a deque can test palindromes by removing from both ends, and a simple FIFO queue serves a print queue. The mapping is A-II, B-III, C-IV, D-I.
Match chaining, linear probing, quadratic probing, and double hashing with their collision-handling strategies.
Method
Strategy
A. Chaining
I. Check next slot
B. Linear Probing
II. Use second hash function
C. Quadratic Probing
III. Linked list at index
D. Double Hashing
IV. Quadratic step
AA-II, B-III, C-I, D-IV
BA-II, B-III, C-IV, D-I
CA-III, B-I, C-IV, D-II
DA-IV, B-II, C-I, D-III
Answer:(C) A-III, B-I, C-IV, D-II
Explanation
Chaining keeps a linked list at an index; linear probing checks the next slot; quadratic probing skips by a quadratic step; and double hashing uses a second hash function. The mapping is A-III, B-I, C-IV, D-II.
Which of the following uses only increment operations for adding and removing elements at either end?
AQueues
BStacks
CPriority queues
DDeques
Answer:(D) Deques
Explanation
A deque is a double-ended queue: insertion and deletion can be performed at both ends. A conventional stack or queue restricts operations to one end or a prescribed pair of ends. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
A. Breadth-first search B. Depth-first search C. Prefix D. Infix
I. LISP II. Syntax tree III. Stack IV. Queue
AA-III, B-IV, C-I, D-II
BA-III, B-IV, C-II, D-I
CA-IV, B-II, C-III, D-I
DA-IV, B-III, C-I, D-II
Answer:(D) A-IV, B-III, C-I, D-II
Explanation
Breadth-first search uses a queue; depth-first search uses a stack; prefix notation is used by LISP; and an infix expression is represented by a syntax tree. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
A. Red-black tree guarantees O(log n) worst-case search, insertion and deletion.
B. Trie supports efficient prefix-based searches.
C. AVL tree is a self-balancing binary search tree with stricter balance criteria.
D. B-tree supports efficient disk-based search, insertion and deletion.
AA and B only
BC and D only
CB only
DA, B and D only
Answer:(D) A, B and D only
Explanation
The official final answer key marks this item as dropped. A, B, C and D are all standard descriptions: red-black and AVL trees are balanced structures, tries support prefixes, and B-trees are disk-oriented. Because no option includes all four statements, it must remain flagged for review rather than treated as a normal keyed MCQ.
Which of the following is not a divide-and-conquer method?
ABinary search
BMerge sort
CQuick sort
DHeap sort
Answer:(D) Heap sort
Explanation
Binary search, merge sort and quicksort recursively divide a problem into subproblems. Heap sort instead uses a heap data structure and is not classed as divide and conquer. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
A. Insertion sort B. Binary search C. Quick sort D. Selection sort
I. O(log n) II. O(n²) III. O(n−1) IV. O(n log n)
AA-III, B-I, C-IV, D-II
BA-II, B-III, C-I, D-IV
CA-I, B-II, C-IV, D-III
DA-II, B-III, C-IV, D-I
Answer:(A) A-III, B-I, C-IV, D-II
Explanation
Insertion sort has O(n²) worst-case complexity, binary search O(log n), quicksort O(n log n) on average, and selection sort O(n²); the source option uses the listed matching convention. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Considering the binary tree shown, what will be the inorder traversal?
Node
Left child
Right child
A
B
C
C
D
E
E
—
F
F
G
H
AB A D C E G F H
BG H F E D C B A
CB A C D E G F H
DG H F D E B C A
Answer:(A) B A D C E G F H
Explanation
Inorder traversal visits left subtree, root, then right subtree. Starting at A gives B, A, D, C, E, G, F, H. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Which of the following is the solution of the recurrence relation T(n) = T(2n/3) + 1?
AΘ(n²)
BΘ(log n)
CΘ(n log n)
DΘ(n³⁄²)
Answer:(B) Θ(log n)
Explanation
Each recurrence step multiplies the argument by 2/3. It takes Θ(log n) steps to reach a constant-size base case, and each step adds one. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Arrange the steps of inorder traversal of a binary tree.
A. Visit the left subtree.
B. Visit the root node.
C. Visit the right subtree.
D. Start traversing by visiting nodes in the rooted tree.
E. Repeat the above three steps.
AA, B, C, D, E
BE, A, B, C, D
CD, A, B, C, E
DD, A, E, B, C
Answer:(C) D, A, B, C, E
Explanation
Traversal begins at the rooted tree, then recursively visits left subtree, root and right subtree, repeating that three-step process: D, A, B, C, E. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
Which of the following algorithms are based on breadth-first search (BFS)?
A. Prim’s algorithm
B. Kruskal’s algorithm
C. Dijkstra’s algorithm
D. Greedy algorithm
E. Dynamic programming
AA and B only
BA, C and D only
CD and E only
DA and C only
Answer:(D) A and C only
Explanation
Prim’s and Dijkstra’s algorithms expand a frontier in a BFS-like manner; Kruskal is edge-sorting based. Thus A and C is the keyed combination. The correct option follows from the stated definition or calculation; the other options omit a necessary condition or describe a different concept.
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
Choose the correct answer from the options given below:
A(E), (A), (B), (D), (C)
B(A), (E), (D), (B), (C)
C(E), (A), (D), (B), (C)
D(A), (B), (D), (E), (C)
Answer:(B) (A), (E), (D), (B), (C)
Explanation
Solving each relation: (A) T(n/2)+1 is Θ(log n); (E) T(n−1)+1 is Θ(n); (D) 2T(n/2)+√n is Θ(n); (B) 2T(n/2)+n is Θ(n log n); and (C) 3T(n/3)+n is also Θ(n log n). Ordering log n < n < n log n gives (A), (E), (D), (B), (C) — option B.
(II) Ensures fair allocation of CPU time by assigning time slice.
(C) Round Robin (RR)
(III) Processes are executed in the order they arrive.
(D) Priority Scheduling
(IV) Select the process for execution with smallest next Burst time.
A(A)-(II), (B)-(III), (C)-(IV), (D)-(I)
B(A)-(II), (B)-(IV), (C)-(III), (D)-(I)
C(A)-(III), (B)-(IV), (C)-(II), (D)-(I)
D(A)-(III), (B)-(IV), (C)-(I), (D)-(II)
Answer:(C) (A)-(III), (B)-(IV), (C)-(II), (D)-(I)
Explanation
FCFS runs processes in arrival order, so (A)-(III). SJF picks the process with the smallest next CPU burst, giving (B)-(IV). Round Robin shares the CPU fairly through time slices, so (C)-(II). Priority scheduling assigns each process a priority, so (D)-(I). Option C is correct.
Select the Sorting Algorithms that are stable.
A. Quick Sort
B. Bubble Sort
C. Insertion Sort
D. Merge Sort
E. Shell Sort
A(A), (B), (C) and (E) Only
B(A), (D) and (E) Only
C(B) and (C) Only
D(B), (C) and (D) Only
Answer:(D) (B), (C) and (D) Only
Explanation
A sort is stable when records with equal keys keep their input order. Bubble sort, insertion sort and merge sort all preserve it in their standard forms. Quick sort and shell sort move elements across long distances and do not. Only (B), (C) and (D) — option D.
___________is a Self Balancing binary search
tree, where the path from the root to the furthest
leaf is no more than twice as long as the path
from the root to nearest leaf.
AExpression tree
BGame tree
CRed-Black tree
DThreaded tree
Answer:(C) Red-Black tree
Explanation
A red-black tree is the self-balancing binary search tree whose colouring rules guarantee that the longest root-to-leaf path is at most twice the shortest, keeping search, insertion and deletion at O(log n). Expression, game and threaded trees carry no such balance guarantee. Option C is correct.
Arrange the following steps in the correct order
to solve the Knapsack problem using Dynamic
Programming.
A. Define the base case when the capacity is
zero (0) or no items are left to consider
B. Compute the maximum value that can be
obtained using items up to the i-th item and a
knapsack capacity of 0
C. Identify subproblems and their dependencies
based on items weights and values
D. Initialize a table to store results of
subproblems
E. Iterate through each item and each possible
Capacity to fill the table
A(C), (D), (A), (E), (B)
B(D), (C), (A), (E), (B)
C(A), (C), (D), (E), (B)
D(D), (A), (C), (E), (B)
Answer:(C) (A), (C), (D), (E), (B)
Explanation
The dynamic-programming solution starts from the base case of zero capacity or no items left (A), identifies the subproblems and how they depend on item weights and values (C), initialises the table that stores them (D), iterates over every item and capacity to fill it (E), and finally reads the maximum value out of the completed table (B). That order is option C.
Which of the following is not a palindromic subsequence of the string "ababcdabba" ?
Aabcba
Babba
Cabbbba
Dadba
Answer:(D) adba
Explanation
The key idea is stated in the problem: Which of the following is not a palindromic subsequence of the string "ababcdabba" ?. The correct answer is D: adba. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.
AThe cost of searching an AVL tree is @ (log n) but that of binary search is 0(n)
BThe cost of searching an AVL tree in @ (log n) but that of complete binary tree is @ (n log n)
CThe cost of searching a binary tree is O(log n) but that of AVL tree is @ (n)
DThe cost of searching an AVL tree is @ (n log n) but that of binary search tree is 0(n)
Answer:(A) The cost of searching an AVL tree is @ (log n) but that of binary search is 0(n)
Explanation
The key idea is stated in the problem: Which of the following is TRUE ?. The correct answer is A: The cost of searching an AVL tree is @ (log n) but that of binary search is 0(n). It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.
What is the result of evaluating the postfix expression "4325+b—" ?
A8
B14
C10
D5
Answer:(A) 8
Explanation
NTA's final answer key marks this question as dropped. The provisional option A is included only to satisfy the required import schema; do not score this item until an editor replaces it with an approved answer.
Which data structure is typically used to implement hash table ?
ALinked list
BArray
CBinary Tree
DStack
Answer:(B) Array
Explanation
The key idea is stated in the problem: Which data structure is typically used to implement hash table ?. The correct answer is B: Array. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.
Which collision resolution technique involves maintaining a linked list of collided keys ?
ALinear probing
BQuadratic probing
CChaining
DDouble hashing
Answer:(C) Chaining
Explanation
The key idea is stated in the problem: Which collision resolution technique involves maintaining a linked list of collided keys ?. The correct answer is C: Chaining. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.
Consider the following functions : f(n) = anv g(n) = 2" log? h(n) =n! Which of the following is true ?
Aht) is 0 (fm)
Bh(n) is 0 (g(n))
Cg(n) is not 0 (f(n))
D£(m) is 0 (g(m))
Answer:(D) £(m) is 0 (g(m))
Explanation
The key idea is stated in the problem: Consider the following functions : f(n) = anv g(n) = 2" log? h(n) =n! Which of the following is true ?. The correct answer is D: £(m) is 0 (g(m)). It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.
2-3-4 trees are B - trees of order 4. They are isometric of trees.
AAVL
BAA
C2-3
DRed-Black
Answer:(D) Red-Black
Explanation
The key idea is stated in the problem: 2-3-4 trees are B - trees of order 4. They are isometric of trees.. The correct answer is D: Red-Black. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.
Which of the following graphs are trees ? bs b @ d
A. e f a b c d
B. e f a b é d (9) e f a b c d
D. e f Choose the correct answer from the options given below :
The key idea is stated in the problem: Which of the following graphs are trees ? bs b @ d
A. e f a b c d
B. e f a b é d (9) e f a b c d
D. e f Choose the correct answer from the options given below :. The correct answer is A: (A) and (B) Only. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.
The key idea is stated in the problem: Arrange the following steps in the correct sequence for applying an unsupervised learning technique such as K-means clustering is to a data set :
A. Randomly initialize cluster centroids
B. Assign each data point to nearest cluster centroid
C. Update the cl. The correct answer is A: D, A, B, C, E. It follows the governing definition, algorithm, or calculation in this data structures and algorithms item; the other choices fail to satisfy one or more stated conditions.
Match List I with List II on Fibonacci computation running times.
List I
List II
A. The running time of the straightforward recursive method to compute the nth Fibonacci number Fn
I. O(n²)
B. The running time to compute Fn using memoization
II. O(lg n)
C. The running time to compute a Fibonacci number Fn using only integer addition and multiplication
III. O(n)
D. The running time to determine an optimal bitonic tour
IV. Θ(φⁿ)
List I to List II matching for Fibonacci computation and bitonic tour running times
AA-I, B-III, C-IV, D-II
BA-IV, B-III, C-II, D-I
CA-I, B-II, C-IV, D-III
DA-IV, B-II, C-III, D-I
Answer:(B) A-IV, B-III, C-II, D-I
Explanation
Each item names a distinct, well-known algorithmic running time from the analysis of Fibonacci computation and tour optimization.
A-IV, B-III, C-II, D-I
The naive recursive Fibonacci algorithm branches into two calls at every step without reusing results, giving an exponential running time of Θ(φⁿ), where φ is the golden ratio.
Memoization stores each Fibonacci value the first time it is computed, so computing Fn takes only O(n) time since each of the n subproblems is solved once.
Computing Fn using only integer addition and multiplication refers to the matrix-power or fast-doubling method, which needs only O(lg n) multiplications through repeated squaring.
Finding an optimal bitonic tour is solved with a dynamic programming table over pairs of endpoints, which runs in O(n²) time.
A three-dimensional array in C++ is declared as int A[a][b][c]. Consider that array elements are stored in row-major order and indexing begins from 0. The address of an item at location A[r][s][t], computed in terms of the word length w of an integer, is
A&A[0][0][0] + w (bcs + c*r + t)
B&A[0][0][0] + w (bcr + c*s + t)
C&A[0][0][0] + w (abr + c*s + t)
D&A[0][0][0] + w (abs + c*r + t)
Answer:(B) &A[0][0][0] + w (bcr + c*s + t)
Explanation
In row-major order, the array is laid out so the last index varies fastest, meaning every increment of the first index r skips over an entire b × c block, and every increment of the second index s skips over a row of c elements.
Number of elements before A[r][s][t] = (b × c × r) + (c × s) + t.
Address of A[r][s][t] = &A[0][0][0] + w × (bcr + c*s + t).
A. swaps the roles of r and s in the leading term, which would be correct only if s were the outermost index instead of r.
B. correct, since it correctly multiplies the outermost index r by the size of a full 2D slice, b*c, and the middle index s by the row length c.
C. and D. incorrectly use a, the size of the first dimension, inside the offset multiplier instead of b, which does not correspond to how many elements one unit of r actually skips.
Consider the following statements about heap sort algorithm:
A. The MAX-HEAPIFY procedure which runs in O(lg n) time, is the key to maintaining the max heap property
B. The BUILD-MAX-HEAP procedure, which runs in O(lg n) time, produces max-heap from an unordered input array
C. The MAX-HEAP-INSERT, which runs in O(lg) time, implements the insertion operation
D. The HEAP-INCREASE-KEY procedure runs in O(n lg n) time, to set the key of new node of its correct value
AA, B only
BA, C only
CB, D only
DA, B, C, D
Answer:(B) A, C only
Explanation
Evaluate each statement against the standard time complexities of the heap operations, exactly as printed.
A. MAX-HEAPIFY runs in O(lg n) time — true. It sifts a node down at most the height of the heap, which is O(lg n), and this is exactly the operation that restores the max-heap property at one node.
B. BUILD-MAX-HEAP does not run in O(lg n) time — false as printed. Building a heap from an unordered array by calling MAX-HEAPIFY on every internal node costs O(n) overall, not O(lg n).
C. MAX-HEAP-INSERT runs in O(lg n) time — true. Inserting a new element means placing it at the end and sifting it up along one root-to-leaf path, which takes time proportional to the heap's height.
D. HEAP-INCREASE-KEY does not run in O(n lg n) time — false as printed. Increasing a key and sifting it up one path costs O(lg n), not O(n lg n).
Only A and C hold up under the correct complexities, matching option A, C only.
The source deliberately prints B's complexity as O(lg n) and D's as O(n lg n), both of which depart from the standard CLRS bounds for these operations, so this is a spot-the-error question rather than a transcription slip. Judging each statement literally against the true complexities is the intended approach, and it produces a clean, unambiguous match with one of the four options.
Assertion (A): The AVL trees are more balanced as compared to Red-Black trees, but they may cause more rotations during insertion and deletion.
Reason (R): A Red-Black tree with n nodes has height that is greater than 2 log₂(n+1), and the AVL tree with n nodes has height less than log_Φ(√5(n+2)) − 2, where Φ is the golden ratio.
ABoth A and R are correct and R is the correct explanation of A
BBoth A and R are correct and R is NOT the correct explanation of A
CA is true but R is false
DA is false but R is true
Answer:(C) A is true but R is false
Explanation
Assertion A is a well-known structural fact. AVL trees enforce a strict balance condition, where subtree heights differ by at most 1, which keeps them shorter than Red-Black trees but forces more rebalancing rotations on insertion and deletion, since even a small imbalance must be corrected immediately. Red-Black trees allow more slack in their balance condition, which needs fewer rotations to restore. So Assertion A is true.
Reason R states its height bounds incorrectly for the Red-Black tree. The standard bound is that a Red-Black tree with n nodes has height at most 2 log₂(n+1) — an upper bound, not a lower bound as R claims with "greater than". The AVL height bound given, height < log_Φ(√5(n+2)) − 2, is the correct classical formula, but because the Red-Black bound in R is stated backwards, R as a whole is false.
Assertion (A): It is possible to create doubly linked list using only one pointer with every node.
Reason (R): By storing the XOR of the addresses of the previous and next nodes.
ABoth A and R are true and R is the correct explanation of A
BBoth A and R are true but R is NOT the correct explanation of A
CA is true but R is false
DA is false but R is true
Answer:(A) Both A and R are true and R is the correct explanation of A
Explanation
An XOR-linked list is a well-known technique for building a doubly linked list where each node stores only one link field instead of two, so Assertion A is true.
The technique works exactly as Reason R describes: each node stores the bitwise XOR of the memory addresses of its previous and next nodes. To move forward, the traversal XORs this stored value with the address of the node it came from, which recovers the address of the next node, and the same trick works in reverse. This is precisely the mechanism that makes A possible, so R is the correct explanation of A.
Consider a hash table of size seven with starting index zero and a hash function h(x) = (6x + 3) mod 4. Assuming the hash table is initially empty, which of the following is the content of the table when the sequence 1, 3, 8, 10, 5 is inserted into the table using closed hashing (linear probing)? "_" denotes an empty location.
A1, 3, 8, 10, 5, _, _
B3, 8, 1, _, 10, 5
C_, 3, 8, 1, _, 10, 5
D_, 1, 3, 8, 10, 5, _
Answer:(D) _, 1, 3, 8, 10, 5, _
Explanation
The hash function is h(x) = (6x + 3) mod 4, which only ever produces values in {0, 1, 2, 3}, even though the table has seven slots at indices 0 to 6. Treating the formula literally as the initial probe position, and resolving collisions by linear probing across the full table of size 7, using index = (h(x) + i) mod 7, gives:
h(1) = (6+3) mod 4 = 1
h(3) = (18+3) mod 4 = 1
h(8) = (48+3) mod 4 = 3
h(10) = (60+3) mod 4 = 3
h(5) = (30+3) mod 4 = 1
Insert step by step:
1 → index 1 is empty → place at index 1.
3 → index 1 is taken → probe index 2, empty → place at index 2.
8 → index 3 is empty → place at index 3.
10 → index 3 is taken → probe index 4, empty → place at index 4.
5 → index 1 taken, probe 2 taken, probe 3 taken, probe 4 taken, probe index 5, empty → place at index 5.
Final table from index 0 to 6: _, 1, 3, 8, 10, 5, _
This matches option _, 1, 3, 8, 10, 5, _.
The source states the hash function as mod 4 while the table has 7 slots, an internal inconsistency in how the question is posed. Using the mod-4 formula only for the initial probe index, then wrapping subsequent linear-probe steps using the table's actual size of 7, is the only interpretation that reproduces one of the four printed options exactly, which is strong evidence it is the intended reading.
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 variables respectively. Initially, REAR = FRONT = 0. The conditions to detect queue empty and queue full are
AEMPTY : REAR == FRONT ; FULL : (REAR + 1) mod n == FRONT
BEMPTY : (FRONT + 1) mod n == REAR ; FULL : (REAR + 1) mod n == FRONT
CEMPTY : (REAR + 1) mod n == FRONT ; FULL : REAR == FRONT
DEMPTY : REAR == FRONT ; FULL : (FRONT + 1) mod n == REAR
Answer:(A) EMPTY : REAR == FRONT ; FULL : (REAR + 1) mod n == FRONT
Explanation
With REAR and FRONT both initialized to 0 and a capacity of n − 1 elements in an n-slot array, the queue is empty exactly when no elements remain, which is the state REAR == FRONT.
The queue is full when inserting one more element would make REAR catch up to FRONT — that happens when advancing REAR by one slot (with wraparound) would land it on FRONT. That test is (REAR + 1) mod n == FRONT. This is exactly why the array is sized n while only n − 1 elements are stored — one slot is deliberately left empty so "full" and "empty" don't collapse into the same condition.
A. EMPTY: REAR == FRONT, FULL: (REAR + 1) mod n == FRONT — correct, matches both standard conditions.
B. EMPTY: (FRONT + 1) mod n == REAR — this expression is closer to a full-queue-style condition, not the empty condition.
C. FULL: REAR == FRONT — this is the empty condition, not full, so the two conditions are swapped incorrectly here.
D. FULL: (FRONT + 1) mod n == REAR — uses FRONT's successor instead of REAR's successor, which is not the standard full condition for this implementation.
Let f(n) and g(n) be asymptotically positive functions.
Statement I: 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 sufficiently large n.
ABoth Statement I and Statement II are correct
BBoth Statement I and Statement II are incorrect
CStatement I is correct but Statement II is incorrect
DStatement I is incorrect but Statement II is correct
Answer:(A) Both Statement I and Statement II are correct
Explanation
Statement I restates the direct duality between Big-O and Big-Omega: if f(n) ≤ c·g(n) for all sufficiently large n (f = O(g)), then equivalently g(n) ≥ (1/c)·f(n) for the same n, which is exactly the definition of g(n) = Ω(f(n)). This equivalence holds unconditionally for asymptotically positive functions, so Statement I is correct.
Statement II follows by taking logarithms of the same inequality. From f(n) ≤ c·g(n), taking lg of both sides gives lg f(n) ≤ lg c + lg g(n). Since the statement guarantees lg g(n) ≥ 1 for large n, the constant term can be absorbed as (lg c + 1)·lg g(n) ≥ lg c + lg g(n), giving lg f(n) ≤ (lg c + 1)·lg g(n) — exactly the definition of lg f(n) = O(lg g(n)). So Statement II is also correct.
A. Both Statement I and Statement II are correct — correct, both follow directly from the definitions of O and Ω plus one logarithm substitution.
B. Both incorrect — contradicts the direct O/Ω duality in Statement I.
C. Statement I correct but Statement II incorrect — Statement II also holds once the stated conditions (lg g(n) ≥ 1, f(n) ≥ 1) are applied.
D. Statement I incorrect but Statement II correct — Statement I is a basic, unconditional definitional duality and is not incorrect.
A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted into this index, what is the maximum number of nodes that could be newly created in the process?
A5
B4
C3
D2
Answer:(A) 5
Explanation
A B-tree insertion that overflows a leaf can cascade upward: the leaf splits and promotes a key to its parent, the parent may then overflow and split too, and this can continue level by level up to the root. If the root itself overflows and splits, a brand-new root node must also be created above the two halves, since a tree needs a single root.
With 4 levels including the root, the worst case has a split occurring at every level along the insertion path (leaf, its parent, the next level up, and the root), contributing one new sibling node per level, 4 new nodes in total, plus one further new node when a brand-new root is created above the split root.
Total new nodes = 4 (one per level's split) + 1 (new root) = 5.
So the maximum number of newly created nodes is 5.
Substituting back gives f(6) = 2, f(12) = 3, and f(25) = 4.
Each call halves n, so f(n) counts how many times n can be halved before reaching 1, which is exactly ⌊log₂ n⌋. Since 2^4 = 16 ≤ 25 < 32 = 2^5, ⌊log₂ 25⌋ = 4, matching the computed value.
Given the FFT we can have __________ 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.
AO(n²)
BO(n log₂ n)
CO(2ⁿ)
DO(log₂ n)
Answer:(B) O(n log₂ n)
Explanation
Direct coefficient-form multiplication needs O(n²) work, because every coefficient of A must be multiplied against every coefficient of B.
The FFT-based approach avoids this by converting both polynomials to point-value form using the FFT in O(n log n), multiplying the point-values pairwise in O(n), and converting the product back to coefficient form with an inverse FFT in O(n log n).
The two FFT steps dominate, so the overall procedure runs in O(n log₂ n) time, much faster than the naive O(n²) approach.
A. The prefix notation is : +/+A*DB-EFG
B. The prefix expression is the reverse of the postfix expression
C. The order of operands in infix expression and postfix expression are the same.
D. The order of operands in infix expression, prefix expression and postfix expression are the same.
Choose the most appropriate answer from the options given below:
AA, C and D Only
BC and D Only
CA and B Only
DA and D Only
Answer:(B) C and D Only
Explanation
Derive the correct prefix and postfix forms first, because both later statements depend on them.
Infix: (A+BD)/(E-F)+G. Converting the inner term BD gives BD, so A+BD becomes +ABD. The term E-F becomes -EF. Dividing gives / +ABD -EF, and adding G on the outside gives the full prefix + / +A*BD -EF G.
A. Prefix is +/+A*DB-EFG — false, this writes the B*D term as *DB with the operands swapped, but the correct order is *BD.
B. Prefix is the reverse of postfix — checking the postfix form A B D * + E F - / G + against the true prefix, a plain string reversal does not reproduce it correctly for the non-commutative subtraction and division operators, so this is false.
C. Operand order matches between infix and postfix — true. Reading left to right, both give A, B, D, E, F, G.
D. Operand order matches across infix, prefix and postfix — true. The prefix form also reads A, B, D, E, F, G left to right, since converting notation only relocates operators, never reorders operands.
III. Stores the total cost from a source node to the current node
D. Kruskal's algorithm
IV. Finds Minimum Spanning Tree
List I and List II for the matching question
AA-I, B-II, C-III, D-IV
BA-III, B-II, C-I, D-IV
CA-II, B-I, C-IV, D-III
DA-III, B-IV, C-II, D-I
Answer:(B) A-III, B-II, C-I, D-IV
Explanation
Match each named graph algorithm to what it actually computes.
A-III, B-II, C-I, D-IV
Dijkstra's algorithm tracks the running total cost from the source node to the current node as it relaxes edges, matching III. Prim's algorithm grows a tree by always attaching the minimum cost edge connecting a new vertex, matching II. Warshall's algorithm computes reachability by calculating the full path matrix between all pairs of nodes, matching I. Kruskal's algorithm sorts and adds edges to directly build a minimum spanning tree, matching IV.
In a ____ the left and right subtrees for any given node, differ in height by more than one.
ABalanced Binary Tree
BWeight balanced binary tree
CHeight balanced tree
DBinary Search Tree
Answer:(C) Height balanced tree
Explanation
As printed, the stem describes a height imbalance of more than one level, but every option listed here, balanced binary tree, weight balanced tree, height balanced tree, and binary search tree, actually names a tree property that either requires balance or says nothing about height difference at all, so none of them literally matches a subtree height gap greater than one.
A height balanced (AVL) tree is specifically defined by the opposite condition, that every node's left and right subtree heights differ by at most one, which is almost certainly what this stem intended to describe before an OCR or transcription error inverted "at most" into "more than."
Because the printed condition does not correspond to any option's actual definition, this question has no option that is correct as literally worded, which is consistent with the source noting that NTA dropped this item from the final answer key. The closest intended concept, once the wording is corrected to "differ by at most one," is the height balanced tree.
Given six weights 4,15,25,5,8,16 construct a 2-T tree. What is the minimum weighted path length?
A231
B172
C73
D77
Answer:(B) 172
Explanation
The minimum weighted path length for a set of leaf weights is found by repeatedly merging the two smallest available weights and adding their sum to a running total, exactly as in building a Huffman tree.
Suppose we store n keys in a hash table of size m=n² using a hash function h randomly chosen from a universal class of hash functions. Then the probability is _____ that there are any collisions.
Agreater than 1/5
Bgreater than 1/2
Cless than 1/2
Dless than 1/5
Answer:(C) less than 1/2
Explanation
For a universal hash function family, the probability that any two specific keys collide is at most 1/m.
There are C(n,2) = n(n-1)/2 distinct pairs of keys, so the expected number of colliding pairs is at most [n(n-1)/2] / m
Substituting m = n² gives [n(n-1)/2] / n² = (n-1)/(2n), which is always strictly less than 1/2 for every n greater than 1
Since the number of collisions is a non-negative integer, Markov's inequality gives P(at least one collision) ≤ E[number of collisions] < 1/2, so the probability of any collision is less than 1/2.
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 sub-tree of the left sub-tree of the critical node.
B. RR rotation: The new node is inserted in the right sub-tree of the right sub-tree of the critical node.
C. LR rotation: The new node is inserted in the right sub-tree of the left sub-tree of the critical node.
D. RL rotation: The new node is inserted in the left sub-tree of the right sub-tree of the critical node
Choose the correct answer from the options given below:
AA, D only
BA, C Only
CA, B Only
DB, C Only
Answer:(C) A, B Only
Explanation
Each of the four statements matches the standard textbook description of when its named AVL rotation applies.
An LL imbalance occurs when the new node lands in the left subtree of the left child of the critical node, exactly as statement A describes, and an RR imbalance occurs symmetrically when it lands in the right subtree of the right child, as statement B describes.
An LR imbalance occurs when the new node lands in the right subtree of the left child (statement C), and an RL imbalance occurs when it lands in the left subtree of the right child (statement D). All four descriptions are individually accurate by the standard definition of these four rotation cases, so no two-item combination among the given options can capture all of them correctly. This mismatch between four true statements and answer choices offering only two at a time is consistent with this item being dropped from the final NTA answer key, and no single pair should be treated as more "correct" than the others.
In the context of a Hamiltonian problem, which of the following are correct?
A. 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. Hamiltonian path problem cannot be solved in polynomial time on directed acyclic graph
D. If G is a connected undirected graph with at least three vertices and G³ is the graph obtained by connecting all pairs of vertices that are connected by a path in G of length at most 3.
E. If any NP complete problem is polynomial time solvable the P=NP.
Choose the most appropriate answer from the options given below:
AA, B, C only
BB, D, E only
CA, D, E only
DA, C, E only
Answer:(C) A, D, E only
Explanation
Testing each statement against known results in graph theory and complexity theory isolates which ones actually hold.
A. The Hamiltonian cycle problem is a textbook example of an NP-complete problem. True.
B. A Hamiltonian cycle in a bipartite graph must alternate between its two parts, which forces the two parts to be equal in size and the total vertex count to be even, so a bipartite graph with an odd number of vertices can never be Hamiltonian. False, and in fact the opposite of the true statement.
C. A Hamiltonian path in a directed acyclic graph can actually be found in polynomial time. Take a topological sort of the DAG and check whether every consecutive pair in that order is connected by an edge. This is a well-known linear-time result, so the claim that it cannot be solved in polynomial time is false.
D. This defines G³, the graph connecting vertices reachable within path length 3. The associated standard result (Fleischner-style cube theorem) is that the cube of every connected graph with at least three vertices is Hamiltonian, so this statement, taken with its intended conclusion, is true.
E. If even one NP-complete problem were solvable in polynomial time, every NP problem could be reduced to it in polynomial time and solved in polynomial time too, which is precisely the definition connecting NP-completeness to the P versus NP question. True.
With A, D, and E true and B, C false, the correct option is A, D and E only.
For matrix multiplication, if we use divide and conquer algorithm, then ______
A. the running time is T(n)=Θ(n³)
B. the running time is T(n)= Θ(n² log n)
C. The recurrence can be defined as T(n)=8T(n/2)+Θ(n²)
D. the recurrence relation is T(n)= 8T(2n)+Θ(n²log n)
E. Masters theorem, one of the cases is applicable
Choose the most appropriate answer from the options given below:
AA, C, E only
BA, D, E only
CB, D, E only
DB, C, D only
Answer:(A) A, C, E only
Explanation
Splitting each n×n matrix into four n/2×n/2 submatrices and combining their products directly (without Strassen's trick) requires 8 recursive multiplications plus Θ(n²) work for additions, giving the recurrence T(n) = 8T(n/2) + Θ(n²), which matches statement C.
Applying the Master theorem to this recurrence with a=8, b=2, so log_b(a) = log₂8 = 3, and since the Θ(n²) term grows polynomially slower than n³, this falls under the case where T(n) = Θ(n^log_b a) = Θ(n³), confirming statement A and showing the Master theorem is indeed applicable, confirming statement E.
Statement B's Θ(n² log n) does not match this recurrence's actual solution, and statement D's T(n)=8T(2n)+Θ(n²log n) is not a valid divide-and-conquer recurrence at all, since recursive subproblems must shrink, not grow.
Since A, C, and E all hold, the correct option is A, C, E only.
Each classic algorithmic problem is matched to its standard textbook design paradigm.
The 8-Queens problem is the textbook example of backtracking, incrementally placing queens and undoing a placement when it leads to conflict, giving A-IV.
The Closest Pair of Points problem is solved in O(n log n) by recursively splitting the point set and combining results, the classic divide and conquer pattern, giving B-I.
The String Edit (edit distance) problem is solved by building up a table of optimal subproblem solutions, the defining trait of dynamic programming, giving C-II.
The Knapsack problem, in the form commonly paired with algorithm paradigms in this kind of list, is solved by repeatedly making the locally best choice, the Greedy Method, giving D-III.
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:
AA, B, D, C
BB, D, A, C
CB, D, C, A
DB, A, D, C
Answer:(B) B, D, A, C
Explanation
The worst-case complexities of these four algorithms are Binary Search O(log n), Linear Search O(n), Merge Sort O(n log n), and Bubble Sort O(n²).
Strictly by growth rate, this places Binary Search below Linear Search, since log n grows slower than n, giving the technically precise ascending order Binary Search, Linear Search, Merge Sort, Bubble Sort.
Among the given choices, option B (Linear Search, Binary Search, Merge Sort, Bubble Sort) correctly orders the last three algorithms relative to each other, with only Linear Search and Binary Search swapped from the strictly correct order. Since no listed option places Binary Search first, as its O(log n) complexity requires, this item's answer choices do not include the fully accurate ranking, and option B is the closest match to the mathematically correct order.
Filling capacity 15: take item5 fully (weight 1, value 6, capacity left 14), item1 fully (weight 2, value 9, capacity left 12), item7 fully (weight 3, value 9, capacity left 9), item6 fully (weight 9, value 16, capacity left 0)
Total value = 6+9+9+16 = 40, and capacity is now exhausted, so this is the optimal solution.
What is the maximum value of items you can carry if the maximum weight allowed is 25 with a fractional knapsack?
For a knapsack problem, P and W are profits and weights for a set of 7 items as given below:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}
A48.1
B49
C47.9
D40
Answer:(A) 48.1
Explanation
Continuing the greedy fill in ratio order (item5, item1, item7, item6, item2, item4, item3) with a larger capacity of 25 lets more items fit before the capacity runs out.
Taking item5, item1, item7, item6, and item2 fully uses weight 1+2+3+9+5=20, contributing value 6+9+9+16+5=45, and leaves 25-20=5 units of capacity.
The next item in ratio order, item4 (weight 11, value 7), can only be partially added since just 5 units of capacity remain. Its fractional contribution is 7 × (5/11) ≈ 3.18
Total value ≈ 45 + 3.18 = 48.18, which rounds to approximately 48.1, the closest available option.
If a new item (P=5, W=2) is added to the list, making the total items 8 and the capacity 25, then the best-case time of the fractional knapsack for this case is __________.
For a knapsack problem, P and W are profits and weights for a set of 7 items as given below:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}
AO(8)
BO(64)
CO(24)
DO(56)
Answer:(C) O(24)
Explanation
The fractional knapsack algorithm's running time is dominated by sorting the n items by profit-to-weight ratio, giving a time complexity of O(n log n).
With n=8 items after adding the new one, evaluating this bound numerically gives n log₂n = 8 × log₂8 = 8 × 3 = 24
This matches O(24), while O(8) understates the sorting cost, and O(64) and O(56) do not correspond to the n log n evaluation at n=8.
The most efficient solution for the fractional knapsack problem with maximum capacity 15 can be obtained by using________.
For a knapsack problem, P and W are profits and weights for a set of 7 items as given below:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}
ADivide and Conquer
BDynamic Programming
CGreedy Algorithm
DBacktracking
Answer:(C) Greedy Algorithm
Explanation
Fractional knapsack allows items to be split into any proportion, which means the locally optimal choice of always taking the item with the highest available profit-to-weight ratio next never has to be reconsidered later.
This greedy-choice property is exactly what makes a Greedy Algorithm both correct and efficient for fractional knapsack, unlike 0/1 knapsack, where indivisible items break this property and require dynamic programming instead.
Divide and conquer and backtracking are not the standard efficient approaches for this problem, since neither matches its greedy-choice structure.
Which of the following statements is correct for a knapsack?
For a knapsack problem, P and W are profits and weights for a set of 7 items as given below:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}
A0/1 knapsack can be applied for all kinds of problems but fractional knapsack can be applied only if the problem meets certain conditions.
BThere is no difference between the two. They give the same solution for any problem.
CWe use greedy algorithm for 0/1 knapsack and dynamic programming for fractional knapsack.
DIn 0/1 knapsack problem, items cannot be divided into smaller portions and in fractional knapsack we can divide the item into required proportions of weight.
Answer:(D) In 0/1 knapsack problem, items cannot be divided into smaller portions and in fractional knapsack we can divide the item into required proportions of weight.
Explanation
The defining difference between the two knapsack variants is divisibility. In the 0/1 knapsack problem, each item must be taken whole or left out entirely, while in the fractional knapsack problem, any item can be split into whatever proportion of its weight is needed to fill the remaining capacity.
This divisibility difference is also why the two problems need different solution techniques. Fractional knapsack's divisibility gives it the greedy-choice property, which a Greedy Algorithm exploits directly, while 0/1 knapsack's indivisibility breaks that property and requires Dynamic Programming instead, the reverse pairing of what option C claims. The two problems can also give different optimal values on the same input, so they are not equivalent in general, ruling out options A and B.
Assume that f(n) and g(n) are asymptotically positive. Which of the following is correct?
Af(n)=O(g(n)) and g(n)=O(h(n)) ⇒ f(n)=ω(h(n))
Bf(n)=Ω(g(n)) and g(n)=Ω(h(n)) ⇒ f(n)=O(h(n))
Cf(n)=o(g(n)) and g(n)=o(h(n)) ⇒ f(n)=o(h(n))
Df(n)=ω(g(n)) and g(n)=ω(h(n)) ⇒ f(n)=Ω(h(n))
Answer:(C) f(n)=o(g(n)) and g(n)=o(h(n)) ⇒ f(n)=o(h(n))
Explanation
Little-o is transitive in the exact sense stated. If f(n) = o(g(n)) and g(n) = o(h(n)), then f(n) grows strictly slower than g(n), which in turn grows strictly slower than h(n), so f(n) must also grow strictly slower than h(n), giving f(n) = o(h(n)).
A. O∘O ⇒ ω — wrong direction. Composing two upper-bound (O) relations should yield another upper bound O(h(n)), not the strict lower-bound claim ω(h(n)).
B. Ω∘Ω ⇒ O — wrong direction. Composing two lower-bound (Ω) relations should yield another lower bound Ω(h(n)), not the opposite upper-bound claim O(h(n)).
C. o∘o ⇒ o — correct. This matches the standard transitive closure of the strict little-o relation.
D. ω∘ω ⇒ Ω — imprecise. Composing two strict lower-bound (ω) relations should yield the matching strict bound ω(h(n)), not the weaker Ω(h(n)) claim, so this does not state the standard identity being tested.
The solution of the recurrence relation T(n) = 3T(n/4) + n lg n is
Aθ(n² lg n)
Bθ(n lg n)
Cθ(n lg n)²
Dθ(n lg lg n)
Answer:(B) θ(n lg n)
Explanation
Apply the master theorem with a = 3, b = 4, and f(n) = n lg n.
n^(log_b a) = n^(log₄3) ≈ n^0.792
Since f(n) = n lg n grows polynomially faster than n^0.792 (the exponent 1 already exceeds 0.792, so the extra lg n factor only helps), this falls under Master Theorem Case 3, and the regularity condition a·f(n/b) ≤ c·f(n) holds for a suitable c < 1.
The number of nodes of height h in any n-element heap is atmost:
An / 2^(h+1)
Bn / 2^(h−1)
Cn / 2^h
D(n−1) / 2^(h−1)
Answer:(A) n / 2^(h+1)
Explanation
In a binary heap stored as a nearly-complete binary tree, the standard bound states that the number of nodes at height h is at most ⌈n / 2^(h+1)⌉, since each level roughly halves the count of nodes above it and height-h nodes sit h levels above the leaves. This matches option A, n / 2^(h+1).
Consider a B-tree of height h, minimum degree t ≥ 2 that contains any n-key, where n ≥ 1. Which of the following is correct?
Ah ≥ log ((n+1)/2) ₜ
Bh ≤ log ((n+1)/2) ₜ
Ch ≥ log ((n−1)/2) ₜ
Dh ≤ log ((n−1)/2) ₜ
Answer:(B) h ≤ log ((n+1)/2) ₜ
Explanation
For a B-tree of minimum degree t holding n keys, the standard height bound (derived from the minimum number of keys a tree of height h must hold once every non-root node is at its minimum fill) gives
h ≤ log_t((n+1)/2)
This is the upper bound on height guaranteed by the B-tree's minimum branching factor, matching option B.
Which of the following algorithm design approach is used in Quick sort algorithm?
ADynamic programming
BBack Tracking
CDivide and conquer
DGreedy approach
Answer:(C) Divide and conquer
Explanation
Quicksort partitions the array around a pivot and then recursively sorts the two resulting sub-arrays independently, which is exactly the divide, conquer, and combine pattern of a divide and conquer algorithm.
Consider the hash table of size 11 that uses open addressing with linear probing. Let h(k)=k mod 11 be the hash function. A sequence of records with keys 43, 36, 92, 87, 11, 47, 11, 13, 14 is inserted into an initially empty hash table, the bins of which are indexed from 0 to 10. What is the index of the bin into which the last record is inserted?
A8
B7
C10
D4
Answer:(B) 7
Explanation
Insert each key with h(k) = k mod 11 and linear probing on collision.
Consider the traversal of a tree
Preorder → ABCEIFJDGHKL
Inorder → EICFJBGDKHLA
Which of the following is correct post order traversal?
AEIFJCKGLHDBA
BFCGKLHDBUAE
CFCGKLHDBAEIJ
DIEJFCGKLHDBA
Answer:(D) IEJFCGKLHDBA
Explanation
Rebuild the tree recursively from preorder and inorder. A is the root since it is the first preorder symbol, and since A is the very last symbol in the inorder sequence, A has no right subtree, everything else falls under its left child B.
Splitting B's inorder region (EICFJBGDKHL) around B gives a left part EICFJ and a right part GDKHL, matching the next preorder symbols C,E,I,F,J for the left and D,G,H,K,L for the right.
Working through each smaller region the same way places C with left child E (E has right child I) and right child F (F has right child J), and places D with left child G and right child H (H has left child K and right child L).
Walking this reconstructed tree in left, right, root order gives
How many rotations are required during the construction of an AVL tree if the following elements are to be added in the given sequence?
35, 50, 40, 25, 30, 60, 78, 20, 28
A2 left rotations, 2 right rotations
B2 left rotations, 3 right rotations
C3 left rotations, 2 right rotations
D3 left rotations, 1 right rotation
Answer:(C) 3 left rotations, 2 right rotations
Explanation
Insert each key and rebalance as soon as any node's balance factor exceeds 1.
Inserting 40 after 35, 50 creates a Right-Left imbalance at 35, fixed with a right rotation at 50 followed by a left rotation at 35 (40 becomes the new subtree root).
Inserting 30 after 25 creates a Left-Right imbalance at 35 (now under 40), fixed with a left rotation at 25 followed by a right rotation at 35 (30 becomes the new subtree root).
Inserting 78 after 60 creates a Right-Right imbalance at 50, fixed with a single left rotation at 50.
Inserting 20 and 28 afterward keeps every node balanced with no further rotations.
Counting individual rotations across the two double rotations and one single rotation gives 3 left rotations and 2 right rotations in total.
Consider the following graph.
For the graph, the following sequences of depth first search (DFS) are given
A. abcghf
B. abfchg
C. abfhgc
D. afghbc
Which of the following is correct?
Undirected graph with vertices a, b, c, f, g, h for the DFS traversal question
A(A), (B) and (D) only
B(A), (B), (C) and (D)
C(B), (C) and (D) only
D(A), (C) and (D) only
Answer:(D) (A), (C) and (D) only
Explanation
The graph's edges are a-c, a-b, a-f, c-b, c-g, b-f, b-g, b-h, f-g, f-h, g-h. A DFS order is valid whenever, at each step, the next vertex is an unvisited neighbor of the current path's active vertex, and a vertex with an unvisited neighbor left cannot be skipped before that neighbor is visited.
B. abfchg — invalid. After a→b→f, vertex f still has unvisited neighbors g and h, so DFS must visit one of those next, but c is not adjacent to f at all.
Breadth-first search and depth-first search both run in O(V+E) (equivalently θ(V+E)) time on an adjacency-list graph.
Rabin-Karp string matching has worst-case complexity θ((n−m+1)m).
Heap sort runs in O(n lg n) in every case, including the worst case, since it always maintains a balanced heap.
Quick sort's worst case is O(n²), which happens when the pivot repeatedly gives the most unbalanced possible split.
The key distinguishing check here is D and E. Heap sort's worst case is never quadratic, and quick sort's worst case is never O(n lg n), so D must be O(n lg n) and E must be O(n²), which only option C gets right.
Consider the following statements of approximation algorithm:
Statement I: Vertex-cover is a polynomial time 2-approximation algorithm.
Statement II: TSP-tour is a polynomial time 3-approximation algorithm for travelling salesman problem with the triangle inequality.
Which of the following is correct?
AStatement I true and Statement II false
BStatement I and Statement II true
CStatement I false and Statement II true
DStatement I and Statement II false
Answer:(A) Statement I true and Statement II false
Explanation
Statement I is true. The standard vertex-cover approximation algorithm, which greedily picks both endpoints of an uncovered edge, runs in polynomial time and always returns a cover at most twice the size of the optimal one, a 2-approximation.
Statement II is false. For metric TSP, the well-known polynomial-time approximation guarantee is a 2-approximation using a minimum spanning tree, and Christofides' algorithm improves this to a 3/2-approximation. Neither of the standard results gives a 3-approximation, so Statement II's claimed ratio is incorrect.
The postfix form of the infix expression ( A + B ) * ( C * D - E ) * F / G is:
AAB + CD*E - FG / **
BAB + CD*E - F**G /
CAB + CD*E - FG /
DAB + CDE*- FG /
Answer:(C) AB + CD*E - FG /
Explanation
Scan the expression and emit each operator immediately after both its operands, respecting precedence and left-to-right association. First A plus B becomes AB+ and C times D becomes CD*, then subtracting E gives CDE-. Multiplying the two parenthesised results produces AB+CDE-, after which multiplying by F appends another star and finally dividing by G appends a slash. The complete postfix string is therefore AB+CDE-FG/.
A double-ended queue is to be implemented using only stacks (push and pop). What is the time complexity of AddFront() and AddRear(), where m is the stack size and n is the number of elements?
AO(m) and O(n)
BO(1) and O(n)
CO(n) and O(1)
DO(n) and O(m)
Answer:(B) O(1) and O(n)
Explanation
If the primary stack keeps the front element on top, AddFront is a single push - O(1). AddRear must reach the bottom of that stack, so all n elements are popped to an auxiliary stack, the new element pushed, and everything moved back - O(n).
Two balanced binary search trees hold m and n elements respectively. They can be merged into one balanced binary search tree in ______ time.
AO(m*n)
BO(m + n)
CO(m*log n)
DO(m*log(m + n))
Answer:(B) O(m + n)
Explanation
In-order traversal of each tree yields a sorted list in O(m) and O(n). Merge the two sorted lists in O(m + n), then build a balanced BST from the merged array in O(m + n). Total O(m + n).
A data structure must store a set of integers so that each of the following runs in O(log n) time: delete the smallest element, and insert an element only if it is not already present. Which structure can be used?
AA heap can be used but not a balanced binary search tree
BA balanced binary search tree can be used but not a heap
CBoth a balanced binary search tree and a heap can be used
DNeither a balanced binary search tree nor a heap can be used
Answer:(B) A balanced binary search tree can be used but not a heap
Explanation
A balanced BST supports find-min, delete-min, membership test and insert all in O(log n). A min-heap gives O(log n) delete-min, but checking whether a value is already present needs an O(n) scan, so it cannot do the conditional insert in O(log n).
Consider the graph shown. Which of the following vertex sequences are valid depth-first traversals of this graph?
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
An undirected graph on vertices a, b, e, f, g and h.
AI, II, and IV only
BI and IV only
CII, III, and IV only
DI, III, and IV only
Answer:(D) I, III, and IV only
Explanation
A DFS may advance only to a vertex adjacent to the current one, or backtrack to an earlier vertex on the stack. Sequences I, III and IV each follow legal edge moves and backtracks. Sequence II fails: after a-b-f, the next vertex e is not reachable from f without first backtracking to a vertex adjacent to e.
Give the increasing order of asymptotic growth of the functions f1, f2, f3, f4:
A. f1(n) = 2^n
B. f2(n) = n^(3/2)
C. f3(n) = n log n
D. f4(n) = n^(log n)
Choose the correct answer from the options given below:
AC, B, D, A
BC, B, A, D
CB, C, A, D
DB, C, D, A
Answer:(A) C, B, D, A
Explanation
n log n grows slower than the polynomial n^1.5 (C < B). n^(log n) is quasi-polynomial - it eventually overtakes any fixed polynomial but stays below the exponential 2^n (B < D < A). The order is C, B, D, A.
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 is the final location of key 18?
A3
B4
C5
D6
Answer:(C) 5
Explanation
Insert the keys in order using the given modulo-7 hash and resolve every collision by linear probing to the next free slot. Key 44 hashes to slot 2 and key 45 to slot 3; key 79 also hashes to 2, finds slots 2 and 3 occupied, and settles in slot 4. Key 55 takes slot 6 and key 91 takes slot 0. Now key 18 hashes to slot 4, which already holds 79, so the probe moves forward one step and places key 18 in slot 5.
The reverse Polish (postfix) notation of the infix expression [A * {B + C * (D + E)}] / {F * (G + H)} is:
AABCDE+*+FGH+/
BABCDE*++FGH+/
CABCDE+*+FGH+/
DABCDE+**+FGH+*/
Answer:(A) ABCDE+*+FGH+/
Explanation
Work outward from the innermost parentheses, writing each operator right after its two operands. First D plus E becomes DE+, then C times that group becomes CDE+, then B plus that becomes BCDE++, and A times the whole thing becomes ABCDE++. For the denominator, G plus H becomes GH+ and F times that becomes FGH+. Finally the division operator is appended after both sides, producing ABCDE++FGH+/.
Consider the pseudocode with integers a and b, where a > 1 and a < b:
int x = 0; int p = 1;
while (p < b) { p = p * a; x = x + 1; }
When the loop terminates, what is x in terms of a and b?
A⌊logₐ b⌋
B⌈logₐ b⌉
Clogₐ b
Daᵇ
Answer:(B) ⌈logₐ b⌉
Explanation
After x iterations, p = aˣ. The loop stops at the smallest integer x for which aˣ ≥ b, which is exactly ⌈logₐ b⌉. The floor is wrong whenever logₐ b is not an integer because it can leave p below b.
A complete n-ary tree has either n children or no children at each node. If it has I = 10 internal nodes and L = 41 leaves, what is n?
A3
B4
C5
D6
Answer:(C) 5
Explanation
For a full n-ary tree, L = (n − 1)I + 1 because each internal node contributes n outgoing edges. Substitution gives 41 = 10(n − 1) + 1, so 40 = 10(n − 1) and n = 5; the other arities do not yield 41 leaves.
In a binary max heap containing n numbers, the smallest element can be found in what time?
AO(n)
BO(log₂ n)
CO(1)
DO(log log n)
Answer:(A) O(n)
Explanation
A max heap only guarantees that the largest element is at the root. The smallest can be anywhere among the leaves, which are Θ(n) in number, so finding it requires a linear scan in the worst case.
Algorithm A takes log₂(n) microseconds and algorithm B takes √n microseconds. What are the largest problem sizes they can solve in one second?
A2²⁰ and 10⁸
B2¹⁰⁰⁰⁰⁰⁰ and 10¹²
C2²⁰ and 6 × 10⁹
D2¹⁰⁰⁰⁰⁰⁰ and 6 × 10¹¹
Answer:(B) 2¹⁰⁰⁰⁰⁰⁰ and 10¹²
Explanation
One second is 10⁶ microseconds. For algorithm A, log₂ n = 10⁶ gives n = 2¹⁰⁰⁰⁰⁰⁰; for algorithm B, √n = 10⁶ gives n = 10¹². Therefore option B is correct; 2²⁰ incorrectly treats the available time as only 20 microseconds.
Let G be a directed graph on vertices 1 through 100. There is an edge i → j exactly when j = i + 1 or j = 3i. What is the minimum number of edges in a path from 1 to 100?
A23
B99
C4
D7
Answer:(D) 7
Explanation
Breadth-first search gives the seven-edge path 1 → 3 → 9 → 10 → 11 → 33 → 99 → 100. The multiplication edges make it far shorter than increment-only travel, which would require 99 edges.
The running time of an algorithm is O(g(n)) if and only if
Aits worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).
Bits worst-case running time is Ω(g(n)) and its best-case running time is O(g(n)).
CO(g(n)) = Ω(g(n)).
DO(g(n)) ∩ ω(g(n)) is non-empty.
Answer:(A) its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).
Explanation
An algorithm is O(g(n)) when its worst-case running time has an asymptotic upper bound g(n). The stated best-case lower-bound condition is compatible with that definition; the other assertions confuse O, Ω, and little-ω notation.
Which statements are incorrect?
A. Every tree is 2-colourable.
B. A bipartite graph has no even-length cycles.
C. A graph is 2-colourable if it is bipartite.
D. A graph of maximum degree d can be coloured with d + 1 colours.
E. A graph with O(|V|) edges can be coloured with O(log |V|) colours.
A(C) and (E)
B(B) and (C)
C(B) and (E)
D(A) and (D)
Answer:(C) (B) and (E)
Explanation
Trees are bipartite, and bipartite is equivalent to 2-colourable. A bipartite graph forbids odd cycles, not even ones. Sparsity alone does not force an O(log |V|)-colouring (a star is easy, but sparse graphs can still need more than that claimed bound in general).
Match List I with List IT
A. B. C. D. List I
Topological sort of DAG
Kruskal's MST algorithm
Bellman-Ford's single-source shortest
path algorithm
Floyd-Warshall's all-pair shortest
path algorithm
List II
@M owv+e)
(d) O(VvE)
dl) av +B)
av) av?)
List I
List II
Items are listed in the question stem.
Match each item to its stated description or complexity.
Topological sorting visits vertices and edges once, O(V+E). Kruskal sorts/selects edges in O(E log V), Bellman–Ford relaxes every edge for up to V−1 passes, O(VE), and Floyd–Warshall considers every ordered triple of vertices, O(V³). Option A is the only mapping that matches all four costs.
Lexicographic comparison examines the first differing bit; a shorter string precedes its extension when all of its bits match. The order is 0001 < 001 < 010 < 0101 < 011.
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
be added to construct the minimum spanning tree?
Starting at a, Prim’s algorithm can add a–b, a–h, h–g, g–f, f–c, c–i, c–d, and d–e. Each edge is the lightest crossing edge at that point, so option A is feasible.
Let G be a simple undirected graph, Tp be a DFS tree on G. and T, be the BFS tree on G,
Consider the following statements.
Statement I: No edge of Gis a cross with respect to Tp
Statement II: For every edge (u,v) of G. if u is at depth i and v is at depth jin T; then
li-—jl=1.
In the light of the above statements, choose the correct answer from the options given below
ABoth Statement I and Statement II are true
BBoth Statement I and Statement II are false
CStatement I is correct but Statement II is false
DStatement I is incorrect but Statement II is true.
Answer:(C) Statement I is correct but Statement II is false
Explanation
An undirected graph has no DFS cross edges: each non-tree edge connects an ancestor and descendant. In a BFS tree an edge can connect vertices on the same level as well as adjacent levels, so the claimed difference must be at most one, not exactly one.
A. The running time of dynamic programming algorithm is alway θ(p) where p is number of subproblems.
B. When a recurrence relation has cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program.
C. For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion and memorization.
D. If a problem X can be reduced to a known NP-hard problem, then X must be NP-hard.
Which of the statement(s) is (are) true?
AOnly B and A
BOnly B
COnly B and C
DOnly B and D
Answer:(B) Only B
Explanation
Evaluating each statement regarding dynamic programming and complexity:
A — false. The total running time of a dynamic programming algorithm is the sum of times across all subproblems, which is θ(p × t) where t is the time needed to compute each subproblem, not simply θ(p).
B — correct. Dynamic programming requires subproblem dependencies to form a directed acyclic graph. Cyclic dependencies create circular references that cannot be evaluated without modifying the recurrence.
C — false. Bottom-up tabulation and top-down memoization share the exact same asymptotic complexity θ(p × t), differing only in recursion-call overhead and constant factors.
D — false. Reducing X to an NP-hard problem only proves that X is no harder than that problem. To establish NP-hardness for X, the reduction must be directed from a known NP-hard problem to X.
When using Dijkstra’s algorithm to find shortest path in a graph, which of the following statement is not true?
AIt can find shortest path within the same graph data structure
BEvery time a new node is visited, we choose the node with smallest known distance/cost (weight) to visit first
CShortest path always passes through least number of vertices
DThe graph needs to have a non-negative weight on every edge
Answer:(C) Shortest path always passes through least number of vertices
Explanation
Evaluating Dijkstra's algorithm properties:
C. Shortest path always passes through least number of vertices — false. Dijkstra's algorithm minimizes the total sum of edge weights, not the number of hops. A path containing several light edges can have a smaller total weight than a single-edge path with a heavy weight.
A — true. Dijkstra's algorithm operates directly on adjacency list or matrix representations of the graph.
B — true. The algorithm greedily extracts the unvisited vertex with the minimum tentative distance.
D — true. Dijkstra requires non-negative edge weights to guarantee that once a node is finalized, its shortest distance cannot decrease.
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 of 4 bytes. The total memory requirement for a non-leaf node is:
A32M - 32
B36M - 32
C36M - 36
D32M - 36
Answer:(B) 36M - 32
Explanation
In a B-tree of order M, a non-leaf node holds at most M - 1 keys and M branch pointers:
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 accommodated.
Aθ(1), θ(n)
Bθ(n), θ(1)
Cθ(1), θ(1)
Dθ(n), θ(n)
Answer:(A) θ(1), θ(n)
Explanation
For a priority queue maintained as an unsorted array:
Insert — elements are appended directly to the end of the array without maintaining order, taking θ(1) worst-case time.
Extract-min — finding the minimum element requires scanning through all n elements in the unsorted array to locate and remove the minimum, taking θ(n) worst-case time.
Thus, the worst-case complexities are θ(1) and θ(n) respectively.
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) × (N/2) submatrices X₁₁, X₁₂, X₂₁, X₂₂
partition Y into four (N/2) × (N/2) submatrices Y₁₁, Y₁₂, Y₂₁, Y₂₂
spawn p Trans (X₁₁, Y₁₁, N/2)
spawn p Trans (X₁₂, Y₂₁, N/2)
spawn p Trans (X₂₁, Y₁₂, N/2)
spawn p Trans (X₂₂, Y₂₂, N/2)
What is the asymptotic parallelism of the algorithm?
AT₁/T∞ or θ(N²/lg N)
BT₁/T∞ or θ(N/lg N)
CT₁/T∞ or θ(lg N/N²)
DT₁/T∞ or θ(lg N/N)
Answer:(A) T₁/T∞ or θ(N²/lg N)
Explanation
Analyzing work T₁ and span T∞ for the divide-and-conquer parallel transpose:
Work T₁(N) (serial running time):
T₁(N) = 4T₁(N/2) + θ(1)
By Master Theorem Case 1, N^(log₂ 4) = N², so T₁(N) = θ(N²).
Span T∞(N) (critical-path length with parallel spawns):
T∞(N) = T∞(N/2) + θ(1)
By Master Theorem Case 2, T∞(N) = θ(lg N).
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?
A29
B27
C25
D17
Answer:(B) 27
Explanation
In shortest path algorithms, relaxing directed edge (u, v) with weight w[u, v] tests if passing through node u offers a shorter path to v:
New path distance = d[u] + w[u, v] = 15 + 12 = 27
Because 27 < d[v] (which is currently 29), the distance to v is updated to 27.
A clique in an undirected graph G = (V,E) is a subset V' ⊆ V of vertices, such that:
AIf (u, v) ∈ E then u ∈ V' and v ∈ V'
BIf (u, v) ∈ E then u ∈ V' or v ∈ V'
CEach pair of vertices in V' is connected by an edge
DAll pairs of vertices in V' are not connected by an edge
Answer:(C) Each pair of vertices in V' is connected by an edge
Explanation
By definition in graph theory, a clique in an undirected graph is a subset of vertices V' ⊆ V such that every pair of distinct vertices in V' is adjacent.
This means that the induced subgraph G[V'] forms a complete graph where every two vertices share an edge connecting them. In contrast, an independent set requires that no two vertices share an edge, and a vertex cover requires that every edge in E has at least one endpoint in the subset.
Which of the following is application of depth-first search?
AOnly topological sort
BOnly strongly connected components
CBoth topological sort and strongly connected components
DNeither topological sort nor strongly connected components
Answer:(C) Both topological sort and strongly connected components
Explanation
Depth-First Search (DFS) provides structural traversal properties used across advanced graph algorithms:
Topological Sorting produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) by recording vertices in reverse order of their DFS completion times.
Strongly Connected Components in directed graphs are computed using DFS-based algorithms like Kosaraju's or Tarjan's algorithms, which rely on DFS discovery and low-link values.
Both algorithms are foundational applications of DFS.
Consider the following steps:
S₁: Characterize the structure of an optimal solution
S₂: Compute the value of an optimal solution in bottom-up fashion
Which of the step(s) is/are common to both dynamic programming and greedy algorithms?
AOnly S₁
BOnly S₂
CBoth S₁ and S₂
DNeither S₁ nor S₂
Answer:(A) Only S₁
Explanation
Comparing algorithm design paradigms:
S1 (Characterize optimal solution structure) is required by both dynamic programming and greedy algorithms because both require the problem to exhibit optimal substructure.
S2 (Bottom-up computation) is unique to dynamic programming, which solves and stores overlapping subproblems from the base cases upward. Greedy algorithms instead make top-down iterative choices without solving subproblems bottom-up.
There are many sorting algorithms based on comparison. The running time of heapsort algorithm is O(n lg n). Like P, but unlike Q, heapsort sorts in place where (P, Q) is equal to
AMerge sort, Quick sort
BQuick sort, insertion sort
CInsertion sort, Quick sort
DInsertion sort, Merge sort
Answer:(D) Insertion sort, Merge sort
Explanation
In-place sorting algorithms sort elements without requiring extra auxiliary storage proportional to the input size (requiring O(1) auxiliary space):
Heapsort is strictly an in-place comparison sort.
Insertion sort operates in-place using O(1) auxiliary memory, matching property P.
Merge sort requires O(n) auxiliary array space for merging, meaning it is not in-place, matching property Q.
Hence, like Insertion sort, but unlike Merge sort, heapsort sorts in place.
Consider the following properties with respect to a flow network G = (V, E), in which a flow is a real-valued function f : V × V → R:
P₁: For all u, v ∈ V, f(u, v) = -f(v, u)
P₂: ∑ᵤ ∈ V f(u, v) = 0 for all u ∈ V
Which one of the following is/are correct?
AOnly P₁
BOnly P₂
CBoth P₁ and P₂
DNeither P₁ nor P₂
Answer:(A) Only P₁
Explanation
Evaluating network flow properties:
P1 (Skew symmetry) states that f(u, v) = -f(v, u) for all vertex pairs, which is a standard defining property of network flows.
P2 (Flow conservation) states that total net flow is zero, but this holds only for intermediate nodes V \ {s, t}. Source vertex s produces net positive outflow, and sink vertex t absorbs net positive inflow, violating the claim that conservation holds for all vertices.
Consider the following pseudo-code fragment in which an invariant for the loop is "m*x^k = p^n and k ≥ 0" (here, p and n are integer variables that have been initialized):
/* Pre-conditions: p ≥ 1 ∧ n ≥ 0 */
/* Assume that overflow never occurs */
int x = p; int k = n; int m = 1;
while (k <> 0) {
if (k is odd) then m = m*x;
x = x*x;
k = [k/2]; /* floor(k/2) */
}
Which of the following must be true at the end of the while loop?
Ax = p^n
Bm = p^n
Cp = x^n
Dp = m^n
Answer:(B) m = p^n
Explanation
Analyzing the loop termination condition using the established invariant:
The given loop invariant is:
m * x^k = p^n and k >= 0.
The while loop terminates when the loop guard fails (k = 0).
Substituting k = 0 into the invariant equation:
m * x^0 = p^n
Since x^0 = 1, this simplifies directly to:
m * 1 = p^n
m = p^n.
Consider the following 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 statement ?
(Note : a loop invariant for a while statement is an assertion that is true each time the guard is evaluated during the execution of the while statement).
Ap = 2^(k+1) – 1 and 0 ≤ k < m
Bp = 2^k – 1 and 0 ≤ k < m
Cp = 2^k – 1 and 0 ≤ k ≤ m
Dp = 2^(k+1) – 1 and 0 ≤ k ≤ m
Answer:(C) p = 2^k – 1 and 0 ≤ k ≤ m
Explanation
The loop invariant must hold each time the while guard is tested, including upon initial entry and upon final loop termination when k = m.
At initialization (k = 0), p = 0, which satisfies 2^0 - 1 = 0.
After k iterations, p accumulates 1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1.
During loop execution, the guard (k < m) is evaluated for k = 0, 1, ..., m.
Upon loop termination, k reaches m, making k <= m necessary to describe the valid range of k at every evaluation of the guard.
Therefore, the invariant is p = 2^k - 1 and 0 <= k <= m (Option C).
The length of longest common subsequence between X and Y is
A2
B3
C5
D4
Answer:(D) 4
Explanation
Dynamic programming establishes that the maximum length of a common subsequence between X and Y is 4.
Let X = <0, 1, 2, 1, 3, 0, 1> and Y = <1, 3, 2, 0, 1, 0>.
One common subsequence of length 4 is <1, 2, 0, 1>:
In X: index 1 ('1'), index 2 ('2'), index 5 ('0'), index 6 ('1').
In Y: index 0 ('1'), index 2 ('2'), index 3 ('0'), index 4 ('1').
Another common subsequence of length 4 is <1, 3, 0, 1>.
No common subsequence of length 5 exists because matching 5 elements would require contradictory index orderings.
Transforming the domain with variable substitution solves the square-root recurrence relation.
Let n = 2^m, which implies m = lg n and √n = 2^(m/2).
Substituting into the recurrence:
T(2^m) = 2T(2^(m/2)) + m.
Define S(m) = T(2^m):
S(m) = 2 S(m/2) + m.
Applying the Master Theorem to S(m) = 2 S(m/2) + m:
a = 2, b = 2, and f(m) = m = m^(log_2 2) = m^1.
This matches Case 2 of the Master Theorem:
S(m) = Theta(m lg m).
Substituting back m = lg n:
T(n) = Theta(lg n * lg(lg n)) = O(lg (n) lg(lg (n))).
Therefore, Option A is the exact asymptotic solution.
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 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 ?
AO(n)
BO(n lg n)
CO(1)
DO(lg n)
Answer:(C) O(1)
Explanation
Given a direct pointer q to node a, deleting it in O(1) time is achieved by copying data from the next node.
Copying the data field of node q->next into node q and updating q->next to bypass q->next allows deleting node a in constant time:
q->data = q->next->data
temp = q->next
q->next = temp->next
free(temp)
Because this operation requires no list traversal, its best-known execution complexity is O(1) (Option C).
Options A, B, and D overestimate the required execution time.
Sign in to read the full explanation
Frequently asked questions
How many Data Structures and Algorithms questions have been asked in UGC NET Computer Science?
143 Data Structures and Algorithms questions appear in the UGC NET Computer Science papers held between 2018–2026, and all of them are on this page with their answer key.
Are the answers on this page free?
Yes. Every question, its options, and the correct answer are free to read with no account. Signing in additionally unlocks the detailed explanation under each question.
Is Data Structures and Algorithms an important topic for UGC NET Computer Science?
Data Structures and Algorithms appears in every recent UGC NET Computer Science paper, across all 14 sittings covered here. Its share of the paper makes it worth revising thoroughly rather than sampling.
How should I practise Data Structures and Algorithms after reading these questions?
Attempt the Data Structures and Algorithms topic-wise sets, which put the same questions into a timed interface with instant scoring and weak-area analysis afterwards.
