Paper - II (vi) — Data structures and Algorithms MCQ — 45 Practice Questions with Answers

Explanation

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.

Explanation

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.

Explanation

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.

Explanation

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.

Explanation

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.