DSA MCQ Questions

Both insertion and deletion are simpler in doubly linked lists because they maintain bidirectional pointers, allowing easier access to previous nodes. Deletion becomes particularly efficient as you can directly access the predecessor without traversal. Insertion also benefits from backward navigation when inserting before a given node, eliminating the need to traverse from the head to find the predecessor.

Deletion of a leaf is a tree operation, not linked list. Basic linked list operations are: creation, insertion, deletion of nodes, and traversal.

A complete graph has edges connecting every pair of distinct vertices, representing maximum connectivity. For n vertices, a complete graph has n(n-1)/2 edges. Complete graphs are denoted Kₙ and serve as fundamental structures in graph theory, representing scenarios where all elements are mutually connected.

A graph with n vertices and k components has maximum edges when each component is a complete graph. The total vertices distributed optimally gives (n-k) vertices in one component and 1 vertex in each of the remaining (k-1) components. The maximum edges = (n-k)(n-k+1)/2, achieved when all 'extra' vertices form one large complete subgraph.

Deletion of the first node modifies the beginning of a linked list by updating the head pointer to point to the second node (or NULL if only one node existed). Insertion after the first or last node doesn't change the head pointer, only internal link structures. Deleting the first node is the only operation that fundamentally changes where the list begins.

For graphs with up to 3 nodes, count possibilities for 0, 1, 2, and 3 vertices separately. With 0 nodes: 1 graph (empty), 1 node: 1 graph, 2 nodes: 2 graphs (connected or not), 3 nodes: 4 graphs (no edges, one edge, two edges forming path/triangle, three edges). Total distinct simple graphs = 1 + 1 + 2 + 4 = 8, though the answer suggests 7 considering only non-isomorphic structures.

The Ford-Fulkerson algorithm's worst-case complexity is O(|E|f) where f is the maximum flow value, as each augmenting path increases flow by at least 1. The algorithm may require f iterations to find the maximum flow, with each iteration searching for an augmenting path in O(|E|) time. More efficient variants like Edmonds-Karp improve this to O(|V||E|²) by using BFS for path selection.

A collision occurs when two different keys hash to the same index in the hash table array, despite having different keys. This happens because hash functions map a large key space to a smaller index range. Collision resolution strategies like chaining or open addressing are essential, as collisions are inevitable in hash tables due to the pigeonhole principle.