Data Structures — Set 1

Correct Answer: A. Stack

• **Stack** = a linear data structure that follows the Last-In-First-Out principle, meaning the most recently added element is always removed first, just as the top plate on a stack of plates is taken off before any other. • **Push and Pop** — the two core operations of a Stack; push adds an element to the top, and pop removes from the top, keeping the LIFO order intact at every step. • Stacks are used by the call stack in every programming language to manage function calls and local variables during recursion. • 💡 Option B (Linked List) is wrong because it has no inherent order of removal — elements can be accessed from any node; Option C (Queue) is wrong because it follows FIFO, the exact opposite of LIFO; Option D (Array) is wrong because it supports random access by index, not restricted LIFO insertion/deletion.

Correct Answer: A. B-Tree

• **B-Tree** = a self-balancing multi-way search tree that keeps sorted data and allows searches, insertions, and deletions in O(log n) time, making it the standard index structure in relational databases like MySQL and PostgreSQL. • **Minimised disk I/O** — a B-Tree stores multiple keys per node so the tree height stays very low, meaning the CPU needs far fewer disk reads to locate a record compared to a simple binary tree. • B-Trees and their variant B+ Trees support efficient range queries because all keys are ordered, which is critical for SQL WHERE clauses. • 💡 Option B (Stack) is wrong because it is a LIFO structure with no sorting or searching capability; Option C (Queue) is wrong because it only supports sequential FIFO access, not indexed retrieval; Option D (Circular List) is wrong because it provides linear traversal with no tree hierarchy for fast lookup.

Correct Answer: D. Tree

• **Tree** = a non-linear, hierarchical data structure consisting of nodes connected by edges, with a single root at the top and child nodes branching downward, making it ideal for representing parent-child relationships like folder structures. • **Non-linear nature** — unlike arrays or linked lists that form a single flat sequence, a tree branches in multiple directions, allowing one parent to have several children at different levels simultaneously. • HTML DOM, company org charts, and operating system file systems all rely on tree structures because their data is naturally hierarchical. • 💡 Option A (Array) is wrong because it stores elements in a flat, indexed linear sequence with no hierarchy; Option B (Stack) is wrong because it is a linear LIFO structure with no branching; Option C (Queue) is wrong because it is a linear FIFO structure that cannot represent parent-child relationships.

Correct Answer: A. Queue

• **Queue** = a linear data structure following the First-In-First-Out principle, where the element added first is the one removed first, exactly like people waiting at a ticket counter — the earliest arrival is served first. • **Enqueue and Dequeue** — enqueue adds an element at the rear, and dequeue removes from the front; these two operations maintain the FIFO order strictly at all times. • Queues are used in CPU process scheduling, printer spooling, and network packet management where arrival order determines priority. • 💡 Option B (Stack) is wrong because it uses LIFO — the newest element leaves first, which is the opposite of FIFO; Option C (Tree) is wrong because it is a non-linear hierarchical structure with no sequential order of removal; Option D (Graph) is wrong because it represents network connections between vertices, not an ordered sequence of element processing.

Correct Answer: D. Dynamic memory allocation

• **Dynamic memory allocation** = the primary advantage of a Linked List; nodes are created at runtime and added or removed without pre-declaring a fixed size, unlike an array whose size must be fixed at the time of declaration. • **Non-contiguous storage** — each linked list node holds its data plus a pointer to the next node, so nodes can be scattered anywhere in memory, enabling the list to grow or shrink freely during program execution. • This flexibility is especially valuable when the total number of elements is unknown in advance, such as in dynamic playlists or real-time data streams. • 💡 Option A (Faster random access) is wrong because linked lists require O(n) traversal to reach any node, while arrays offer O(1) direct access by index; Option B (Easier sorting) is wrong because sorting linked lists involves complex pointer manipulation, making it harder than sorting arrays; Option C (Lower memory usage) is wrong because each linked list node carries an extra pointer field, consuming more memory per element than a plain array.

Correct Answer: A. Graph

• **Graph** = a non-linear data structure consisting of a finite set of vertices and edges, used to model real-world networks such as road maps, social platforms, and computer networks where many-to-many relationships exist. • **Directed vs. undirected** — in a directed graph, each edge has a specific direction (A→B differs from B→A), while in an undirected graph, edges are bidirectional; this distinction models one-way roads as well as mutual friendships. • Graphs are fundamental to algorithms like Dijkstra (shortest path), BFS, DFS, and PageRank, which power Google Maps and search engines. • 💡 Option B (Array) is wrong because it stores elements linearly with no relationship edges between them; Option C (Stack) is wrong because it is a restricted LIFO structure that cannot represent arbitrary multi-directional connections; Option D (Linked List) is wrong because it chains nodes in a single sequential path and cannot represent many-to-many vertex connections.

Correct Answer: D. Hash Table

• **Hash Table** = a data structure that applies a hash function to each key to compute a direct array index (bucket), enabling average O(1) time complexity for search, insert, and delete — far faster than O(log n) for trees or O(n) for linear structures. • **Hash function** — this mathematical function converts a key (e.g., a name or number) into an integer array index; a well-designed hash function distributes keys uniformly across buckets to keep collisions rare. • Hash Tables are the underlying mechanism for Python dictionaries, Java HashMaps, and database caches where near-instant key lookup is essential. • 💡 Option A (Binary Search Tree) is wrong because BST lookup is O(log n), not O(1), and requires maintaining sorted key order; Option B (Queue) is wrong because it is a FIFO structure with no key-to-index mapping capability; Option C (Stack) is wrong because it retrieves only the top element via LIFO, not a specific key by value.

Correct Answer: A. The pointer wraps around to the first position

• **The pointer wraps around to the first position** = in a circular queue, after filling the last array index the rear pointer resets to index 0 (if that slot is free), treating the array as a circle and reusing vacated front slots instead of wasting them. • **Memory efficiency** — a standard linear queue permanently loses space at the front after each dequeue; the circular design solves this by reusing those freed slots, achieving full utilisation of the fixed-size array. • Circular queues are used in CPU round-robin scheduling, audio/video streaming buffers, and traffic signal control systems. • 💡 Option B (The queue overflows) is wrong because overflow only occurs when every slot including wrapped slots is genuinely occupied; Option C (The queue size doubles) is wrong because a circular queue has a fixed array size and does not resize dynamically; Option D (The data is deleted) is wrong because no data is deleted when the last position is reached — only the pointer wraps to position 0.

Correct Answer: D. Post-order

• **Post-order** = a tree traversal that visits nodes in Left → Right → Root sequence, meaning both child subtrees are fully processed before their parent node is visited, which directly matches the question. • **Tree deletion use case** — post-order is the correct traversal for deleting an entire tree because it ensures child nodes are freed from memory before their parent, preventing dangling pointer errors. • Postfix (Reverse Polish Notation) expression evaluation also follows post-order logic: operands are processed before the operator sitting at the root. • 💡 Option A (Pre-order) is wrong because pre-order visits Root → Left → Right, processing the root first, not last; Option B (In-order) is wrong because in-order visits Left → Root → Right, visiting the root in the middle; Option C (Level-order) is wrong because it visits nodes level by level from top to bottom using a queue, not a depth-first left-right-root pattern.

Correct Answer: A. Stack

• **Stack** = the data structure used by every program's call stack to manage recursive function calls; each new call pushes a fresh stack frame (holding parameters and local variables) onto the top, maintaining the exact chain of active calls. • **LIFO matches recursion's return order** — when the base case is reached, results are computed and the frames are popped in reverse order, which is precisely how a recursive Factorial unwinds: n! returns after (n-1)! returns, and so on. • If recursion runs too deep without reaching the base case, the system call stack runs out of space and raises a Stack Overflow error. • 💡 Option B (Queue) is wrong because FIFO would return the first recursive call before inner calls complete, breaking the recursive dependency chain; Option C (Array) is wrong because a plain array has no built-in push/pop mechanism for automatically tracking execution context frames; Option D (Linked List) is wrong because while it can simulate a stack, the hardware call stack used during actual recursion is specifically a stack structure maintained by the CPU.