Data Structures — Set 2

Correct Answer: A. Priority Queues

• **Priority Queues** = the primary application of a Heap; the Heap guarantees that the element with the highest (Max-Heap) or lowest (Min-Heap) priority is always at the root, enabling O(1) access and O(log n) insertion or deletion. • **Heap property** — in a Max-Heap, every parent is greater than or equal to its children; after each insert or delete, the tree is restructured by heapify to restore this property and maintain priority order. • OS task schedulers use Min-Heaps to always run the highest-priority process next, and Dijkstra's shortest-path algorithm uses a Min-Heap to greedily select the nearest unvisited vertex. • 💡 Option B (Undo/Redo) is wrong because undo/redo is implemented with a Stack (LIFO access), not a Heap; Option C (Hashing) is wrong because hashing uses a hash function and an array, not a tree-based structure; Option D (Linear Search) is wrong because linear search scans elements one by one and requires no special data structure at all.

Correct Answer: D. Double Linked List

• **Double Linked List** = a linked list where each node contains three parts: data, a next pointer, and a previous pointer, enabling traversal in both the forward and backward directions without needing to restart from the head. • **Bidirectional navigation** — the previous pointer is the defining feature that distinguishes it from a singly linked list; it allows the browser back-button or a music player previous-track feature to reach the prior node in O(1) time. • The trade-off is additional memory: each node stores two pointers instead of one, doubling the pointer overhead per element. • 💡 Option A (Single Linked List) is wrong because each node has only a next pointer, so backward traversal requires restarting from the head each time; Option B (Static Linked List) is wrong because it simulates linking using arrays and does not include a backward pointer; Option C (Circular Linked List) is wrong because its last node points back to the head for circular forward traversal, but it has no previous pointer enabling true backward movement.

Correct Answer: C. Index

• **Index** = the zero-based numerical position used to identify each element in an array; the first element is at index 0, the second at index 1, and so on, allowing the CPU to compute any element's exact memory address in constant time. • **O(1) random access** — because array elements occupy contiguous memory, the address of element at index i equals base_address + (i × element_size), giving instant direct access without scanning other elements. • Zero-based indexing is the universal standard in C, Java, Python, and most modern languages, making arrays the fastest structure for positional access. • 💡 Option A (Key) is wrong because a key is used in Hash Tables or dictionaries to look up associated values, not to denote a positional slot in an array; Option B (Value) is wrong because value refers to the data stored at a position, not the position itself; Option D (Pointer) is wrong because a pointer stores an absolute memory address, not a relative zero-based offset within an indexed array.

Correct Answer: C. Tree

• **Tree** = the data structure that naturally models a file system because directories and subdirectories form a strict hierarchy, with the root directory at the top, folders as internal nodes, and files as leaf nodes at the bottom. • **Efficient path resolution** — the OS locates any file by following the branch path (e.g., C: → Users → Documents → report.docx), reaching the target in O(depth) steps rather than scanning all files in a flat list. • Both Windows (NTFS) and Linux (ext4) file systems use tree-based directory structures internally for fast path traversal and permission inheritance. • 💡 Option A (Stack) is wrong because a stack only supports LIFO access and has no mechanism to represent branching folder hierarchies; Option B (Queue) is wrong because it handles sequential FIFO processing and cannot model nested directory-within-directory relationships; Option D (Hash Table) is wrong because while it enables fast lookup by filename, it cannot represent the nested hierarchical nesting of directories inside other directories.

Correct Answer: C. O(log n)

• **O(log n)** = the search time complexity for a balanced BST because at each node the algorithm compares the target value and discards the irrelevant half of the tree, halving the remaining search space with every single comparison. • **Balance is essential** — an unbalanced BST degrades to O(n) in the worst case (degenerating into a linked list), which is why self-balancing variants like AVL Trees and Red-Black Trees automatically re-balance after every insertion or deletion. • For a balanced BST with 1 million nodes, at most ~20 comparisons suffice to find any element, versus up to 1 million comparisons in a linear search. • 💡 Option A (O(1)) is wrong because O(1) lookup requires direct index or hash access as in a Hash Table, not tree traversal; Option B (O(n)) is wrong because that is the worst-case of an unbalanced BST or a linear scan, not a balanced one; Option D (O(n²)) is wrong because quadratic complexity appears in inefficient sorting algorithms like Bubble Sort, never in a balanced tree search.

Correct Answer: A. Adjacency Matrix

• **Adjacency Matrix** = a square V×V matrix (where V is the number of vertices) in which a cell at row i, column j holds 1 if an edge exists between vertex i and vertex j, and 0 otherwise, giving an instant O(1) edge-existence check. • **Dense graph suitability** — the matrix representation is ideal when the graph has many edges (dense), but wastes O(V²) memory when the graph is sparse, because most cells remain 0. • For a weighted graph, the cell stores the edge weight instead of just 1, making the matrix directly usable in algorithms like Floyd-Warshall for all-pairs shortest paths. • 💡 Option B (Adjacency List) is wrong because it uses a list of neighbours per vertex, not a 2D matrix, and is preferred for sparse graphs; Option C (Spanning Tree) is wrong because it is a subgraph concept, not a graph representation format; Option D (Binary Tree) is wrong because it is a specific tree structure, not a general graph representation method.

Correct Answer: D. Queue

• **Queue** = the data structure used to implement BFS because BFS explores nodes level by level; a queue ensures that all neighbours of the current node are visited before moving deeper, maintaining the correct breadth-first order via FIFO. • **Level-by-level exploration** — BFS starts at the source, enqueues it, then repeatedly dequeues a node, visits its unvisited neighbours, and enqueues them; this FIFO discipline guarantees nodes at distance k are all visited before nodes at distance k+1. • BFS on an unweighted graph finds the shortest path (in terms of number of edges) between the source and every reachable vertex. • 💡 Option A (Stack) is wrong because a stack implements DFS (Depth-First Search), not BFS — DFS dives deep into one path before backtracking; Option B (Array) is wrong because a plain array has no enqueue/dequeue semantics to enforce level-order traversal; Option C (Tree) is wrong because a tree is a data structure that BFS traverses, not the auxiliary structure used to implement the traversal.

Correct Answer: A. Every node has either 0 or 2 children

• **Every node has either 0 or 2 children** = the defining property of a Full Binary Tree; no node in this structure can have exactly one child, which distinguishes it from a general binary tree where one-child nodes are permitted. • **Huffman coding relevance** — Huffman compression trees are always full binary trees because every internal node is formed by merging exactly two subtrees, ensuring the optimal prefix-free encoding property. • A Full Binary Tree with n internal nodes always has exactly n+1 leaf nodes, a provable mathematical property used in algorithm analysis. • 💡 Option B (Every node has exactly one child) is wrong because that describes a degenerate or skewed tree, the opposite of a full binary tree; Option C (The tree is perfectly balanced) is wrong because balance refers to equal height of subtrees, not the count of children per node; Option D (All leaves are at different levels) is wrong because that describes a skewed tree, whereas a full binary tree can have leaves at the same or different levels.

Correct Answer: D. Sorting

• **Sorting** = the process of rearranging elements in a defined order (ascending or descending) so that subsequent search operations can use efficient algorithms like Binary Search instead of slow linear scans. • **Algorithm variety** — common sorting algorithms include Bubble Sort (O(n²), simple but slow), Merge Sort (O(n log n), stable, divide-and-conquer), and Quick Sort (O(n log n) average, widely used in practice); each suits different scenarios. • Efficient sorting is the backbone of database query optimisation, and most programming languages ship with a built-in sort based on Timsort or Introsort. • 💡 Option A (Searching) is wrong because searching locates an element within existing data without reordering it; Option B (Traversing) is wrong because traversal visits every element in a structure one by one without changing their order; Option C (Hashing) is wrong because hashing maps keys to indices using a hash function and has nothing to do with ordering elements in sequence.

Correct Answer: A. De-queue (Double-ended queue)

• **De-queue (Double-ended queue)** = a generalised queue that supports insertion and deletion at both the front and the rear, giving it the combined capabilities of both a Stack and a Queue in a single structure. • **Input and output restricted variants** — a deque can be configured as input-restricted (insert at one end only) or output-restricted (delete from one end only), making it highly flexible for different algorithmic needs. • Deques are used in the sliding window maximum algorithm, browser cache eviction policies, and palindrome checking. • 💡 Option B (Stack) is wrong because a stack only allows insertion and deletion at one end (the top), not both ends; Option C (Single Linked List) is wrong because while it supports insertion/deletion at either end with pointers, it does not inherently enforce the deque interface or O(1) access at both ends; Option D (Binary Tree) is wrong because it is a non-linear hierarchical structure with no concept of front/rear insertion or deletion.