MCQ
Paper - II (vi) — Data structures and Algorithms MCQ - Practice Questions with Answers
Solve 45 Paper - II (vi) — Data structures and Algorithms questions for RAS/RPSC preparation.
Practice questions
Q1In a binary search tree, a node z with two children is deleted by replacing its key with its inorder successor's key and then deleting that successor node. Which property makes the second deletion simpler than deleting z directly?
The inorder successor of a two-child node is the smallest key in its right subtree. By definition, that node cannot have a left child, because any left child would contain an even smaller key still greater than z. Therefore after copying the successor's key into z, the actual node removed has at most one child, reducing the deletion to a simpler splice operation.
Q2For an undirected graph with V vertices and E edges, which representation is usually more space-efficient for a sparse graph and still permits iteration over all neighbours of a vertex in time proportional to its degree?
Sparse graphs have far fewer edges than V^2, so an adjacency matrix wastes space on absent edges. An adjacency-list representation stores a list of neighbours for each vertex, taking Θ(V + E) space in an undirected graph representation and allowing all neighbours of a vertex to be visited by scanning just that vertex's list.
Q3A stack S receives the operations push(4), push(7), push(1), pop(), push(9), pop(), pop(). Which value is returned by the final pop operation?
A stack follows last-in-first-out order. After push(4), push(7), push(1), the first pop removes 1. push(9) puts 9 on top, and the next pop removes 9. The remaining stack from bottom to top is 4, 7, so the final pop returns 7.
Q4A dictionary ADT is implemented for compiler symbol-table use. It must support insert, delete and search by identifier, and the workload has many failed searches. Which implementation choice best preserves expected constant-time search without requiring identifiers to remain in sorted order?
A symbol table is a dictionary-like ADT: it stores bindings and retrieves them by key. A hash table is the standard fit when ordering is not required, because a well-distributed hash function plus collision handling gives expected O(1) search, insertion and deletion. Sorted arrays trade this for O(log n) search and costly updates; stacks are too restrictive for arbitrary lookup.
Q5For an undirected simple graph with V vertices and E edges, which statement correctly compares adjacency matrix and adjacency list representations for the operation 'test whether edge (u, v) exists'?
An adjacency matrix is a two-dimensional table, so the presence of edge (u, v) can be checked by one indexed lookup. A plain adjacency list is more space-efficient for sparse graphs, but checking a specific edge can require searching through the neighbours of u. Thus the matrix wins on direct edge-existence testing, while the list usually wins on sparse-space usage.
You've seen 5 of 45 sample questions
Unlimited practice on Paper - II (vi) — Data structures and Algorithms comes with the RAS Test Series + Practice pack or Gate Pass.
More questions
6A queue is implemented in an array of size m using front and rear indices with one array slot deliberately left unused to distinguish full from empty. Which condition is correct for a full queue?
7A file containing 1,024 sorted records is stored in an array. The target key is absent. If standard binary search is implemented with inclusive low and high indices, what is the maximum number of key comparisons before the search reports failure?
8An undirected simple graph has 10 vertices and 12 edges. Which comparison between adjacency matrix and adjacency list representations is correct for this graph?
9Consider the postfix expression 8 2 3 ^ / 2 3 * +, where ^ has already been converted to postfix and evaluation uses the usual stack algorithm. What value is produced?
10For a simple undirected graph with n vertices and e edges, an examiner asks which representation is asymptotically better for listing all neighbours of every vertex exactly once when e is much smaller than n^2. Which answer is most accurate?
11In the shunting-yard style conversion of an infix expression to postfix, the input token is an operator op. Which rule is correct for left-associative operators of ordinary precedence?
12A sequence stores n records. The workload is 90% random access by rank, 9% appending at the end, and 1% deletion from the middle after the position is already known. Memory locality is important. Which representation is generally the best fit?
13Which statement correctly compares arrays and singly linked lists for storing a dynamic sequence of records?
14A stack is implemented using two queues Q1 and Q2. The designer wants push to be O(1) and pop to return the most recently pushed item. Which method correctly implements pop when Q1 contains the stack items in their normal queue order?
15A compiler symbol table is implemented by hashing with separate chaining. If the hash function maps every identifier in a program to the same bucket, what is the worst-case time to search one identifier among n stored identifiers?