Data Structures — Set 3

Correct Answer: D. Underflow

• **Underflow** = the error condition that occurs when a pop or dequeue operation is attempted on an empty data structure; there is no element to remove, so the operation is invalid and the program must handle this gracefully. • **Prevention** — in a Stack, a standard best practice is to check isEmpty() before every pop; if the stack is empty, the program raises an error or returns a sentinel value instead of crashing. • Underflow is the logical opposite of Overflow: overflow happens when you try to insert into a full fixed-size structure, while underflow happens when you try to delete from an empty one. • 💡 Option A (Overflow) is wrong because overflow occurs when you try to add to a structure that is already full, not remove from an empty one; Option B (Null Pointer) is wrong because a null pointer error relates to accessing an uninitialised reference, not an empty structure operation; Option C (Collision) is wrong because collision is a Hash Table concept where two keys map to the same bucket, unrelated to empty structure deletion.

Correct Answer: C. Tree

• **Tree** = a Spanning Tree is a subgraph of a connected graph that includes all V vertices and exactly V-1 edges, forming a tree (connected and acyclic) that spans every vertex without any cycles. • **Minimum Spanning Tree (MST)** — among all possible spanning trees of a weighted graph, the MST is the one with the lowest total edge weight; Prim and Kruskal algorithms find MSTs and are used to design minimum-cost networks like electrical grids and pipelines. • A graph with V vertices can have many different spanning trees; the exact count can be computed using Kirchhoff Matrix Tree Theorem. • 💡 Option A (Circle) is wrong because a spanning tree must be acyclic — adding any cycle would violate the tree definition; Option B (Complete Graph) is wrong because a complete graph has edges between every pair of vertices, far more than the V-1 edges of a spanning tree; Option D (Directed Graph) is wrong because spanning trees are an undirected graph concept and do not require directed edges.

Correct Answer: A. 2

• **2** = the maximum number of children any node can have in a Binary Tree, which is the defining constraint of the structure; each node has at most a left child and a right child, and never more than two. • **Why the limit of two** — restricting children to two simplifies recursive algorithms enormously: every operation (search, insert, delete, traversal) can be written with a simple left/right branch decision at each node, leading to clean O(log n) or O(n) algorithms. • A binary tree with n nodes has at most n-1 edges, and a full binary tree with height h has at most 2^(h+1) - 1 nodes. • 💡 Option B (1) is wrong because a node with only one child is allowed in a general binary tree, but the maximum is 2, not 1; Option C (3) is wrong because a tree allowing 3 children per node is a ternary tree, not a binary tree; Option D (Unlimited) is wrong because unlimited children per node describes a general tree or an N-ary tree, not a binary tree.

Correct Answer: D. Array

• **Array** = a linear data structure that stores elements of the same type in a single contiguous block of memory, with each element identified by a zero-based index, enabling O(1) random access to any position. • **Fixed size** — the size of an array must be declared before use and cannot be changed at runtime in most low-level languages like C; this fixed allocation is the source of both its speed advantage and its inflexibility. • Arrays are the foundation of many higher-level structures: stacks, queues, heaps, and hash tables are all typically built on top of an underlying array. • 💡 Option A (Linked List) is wrong because linked list nodes are scattered in non-contiguous memory and connected via pointers, not stored in a fixed-size block; Option B (Binary Tree) is wrong because it is a non-linear hierarchical structure, not a fixed-size flat memory block; Option C (Graph) is wrong because it is a non-linear structure of vertices and edges with no inherent fixed-size contiguous memory layout.

Correct Answer: A. Collision

• **Collision** = the situation in a Hash Table where two different keys produce the same hash index, causing both to compete for the same bucket; this happens because the number of possible keys usually far exceeds the finite array size. • **Resolution techniques** — Chaining stores multiple colliding keys in a linked list at the same bucket, while Open Addressing probes for the next available slot; both maintain correctness at the cost of some performance. • A good hash function minimises collision frequency by distributing keys uniformly, but collisions can never be completely eliminated when the key space is larger than the table size. • 💡 Option B (Overflow) is wrong because overflow refers to inserting into a full fixed-size structure, not two keys mapping to the same index; Option C (Underflow) is wrong because underflow refers to deleting from an empty structure; Option D (Mapping) is wrong because mapping is the normal successful operation of a hash function, not the error condition where two keys share the same index.

Correct Answer: C. Stack

• **Stack** = the data structure used to implement the browser Back button because each URL you visit is pushed onto the stack, and clicking Back pops the current URL to reveal the previous one — a perfect LIFO pattern. • **Forward button pairing** — browsers typically use a second stack for the Forward button: when you click Back, the current URL is pushed onto the forward stack and popped from the back stack; clicking Forward reverses the operation. • The call stack in your programming language runtime works on the same LIFO principle, returning to the previous function after the current one finishes. • 💡 Option A (Queue) is wrong because a queue follows FIFO — it would take you to the first page you ever visited, not the most recent previous one; Option B (Linked List) is wrong because while it can store URLs, it has no built-in LIFO discipline for the back-navigation pattern; Option D (Array) is wrong because a plain array requires manual index management and does not natively enforce the push/pop LIFO behaviour needed for back navigation.

Correct Answer: D. Cycle

• **Cycle** = a closed path in a graph where you can start at a vertex, traverse a sequence of edges, and return to the same starting vertex without repeating any edge, forming a loop within the graph. • **Acyclic graphs** — graphs that contain no cycles are called acyclic; a Directed Acyclic Graph (DAG) is fundamental to scheduling problems, dependency resolution in package managers, and course prerequisite systems. • Cycle detection algorithms (using DFS colouring or Union-Find) are critical in network routing to prevent infinite loops and in deadlock detection in operating systems. • 💡 Option A (Bridge) is wrong because a bridge is an edge whose removal disconnects the graph, not a closed loop; Option B (Leaf) is wrong because a leaf is a node with no children (degree 1 in a tree), not a path concept; Option C (Degree) is wrong because degree is the count of edges connected to a vertex, not a type of path.

Correct Answer: D. Trie

• **Trie** = a tree-based data structure that stores strings character by character, sharing common prefixes across multiple strings so that each node represents one character and each root-to-leaf path spells out a complete word. • **O(L) lookup speed** — searching for a word of length L in a Trie takes exactly L steps regardless of how many words are stored, making it faster than a hash table for prefix-based queries and vastly faster than a linear scan of a word list. • Tries power auto-complete in search engines and IDEs, spell checkers, and IP routing tables, where prefix matching is the core operation. • 💡 Option A (Red-Black Tree) is wrong because it is a self-balancing BST that stores comparable keys by value, not character-by-character for prefix sharing; Option B (Heap) is wrong because it is a priority-based structure for finding min/max elements, with no capability for string prefix matching; Option C (B+ Tree) is wrong because it is a disk-optimised multi-way tree used for database indexing, not for character-level prefix storage.

Correct Answer: D. The number of edges connected to it

• **The number of edges connected to it** = the degree of a vertex in an undirected graph; every edge incident on the vertex contributes 1 to its degree, so a vertex with 4 edges has degree 4. • **In-degree and Out-degree** — in a directed graph, the degree is split into in-degree (edges arriving at the vertex) and out-degree (edges leaving the vertex); this distinction is critical in algorithms like topological sorting and PageRank. • A vertex with degree 0 is called an isolated vertex, and the sum of all vertex degrees in any undirected graph always equals twice the number of edges (Handshaking Lemma). • 💡 Option A (The value of the node) is wrong because node value is the data stored in the node, completely unrelated to its connectivity; Option B (The distance from the root) is wrong because that is depth or level of a node in a tree, not a graph degree concept; Option C (The level of the node) is wrong because levels are a tree concept measured from the root, while degree counts edge connections in a graph.

Correct Answer: B. Priority Queue

• **Priority Queue** = the data structure used to handle system interrupts because it processes events by importance (priority) rather than by arrival time, ensuring that a critical hardware interrupt is serviced by the CPU before a low-priority background task. • **Interrupt priority levels** — modern CPUs assign numeric priority levels to interrupts; a Priority Queue (usually implemented as a Min-Heap) always extracts the highest-priority pending interrupt in O(log n) time, preventing critical events from being blocked. • Priority Queues are also used in Dijkstra shortest-path, A* pathfinding, Huffman encoding, and operating system process scheduling. • 💡 Option A (Stack) is wrong because a stack uses LIFO order — the most recently arrived interrupt would be handled first regardless of priority, which is dangerous for system stability; Option C (Hash Table) is wrong because a hash table provides fast key lookup but has no ordering or priority mechanism for sequenced event processing; Option D (Binary Tree) is wrong because a general binary tree has no built-in priority extraction operation — only a Heap (a specific binary tree with the heap property) implements Priority Queue efficiently.