Other IT & Programming Subjects
DSA
Which of the operations is simpler in the doubly linked list than it is in the simple linked list?
Explanation:
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.
Which of the following is NOT a basic function of a linked list?
Explanation:
Deletion of a leaf is a tree operation, not linked list. Basic linked list operations are: creation, insertion, deletion of nodes, and traversal.
A simple graph in which there exists an edge between every pair of vertices is called a/an _________.
Explanation:
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 simple graph with n vertices and k components can have at the most _______.
Explanation:
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.
Which of the following operations in the simple linked list will modify the beginning of the linked list?
Explanation:
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.
The number of distinct simple graphs with up to three nodes is _______.
Explanation:
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.
What is the worst-case time complexity of the simple Ford-Fulkerson algorithm for finding the maximum flow in a graph given a source and a sink, and all integer capacities on edges? Assume the graph G = (V,E) has a finite, integer maximum flow value of f.
Explanation:
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.
What is the best definition of a collision in a hash table?
Explanation:
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.
Filter by Difficulty
Difficulty Filter
Sign in to unlock
Sign in to unlock