Question 36
In open addressing, resolving collisions by probing consecutive table slots (i+1, i+2, ...) is called -
Linear Probing checks adjacent sequential array slots sequentially (hash(key) + i) % size until an empty slot is discovered.
In open addressing, resolving collisions by probing consecutive table slots (i+1, i+2, ...) is called -
Linear Probing checks adjacent sequential array slots sequentially (hash(key) + i) % size until an empty slot is discovered.
Space complexity of an adjacency matrix representation for a graph with V vertices is -
An adjacency matrix uses a V x V 2D grid to store edge connectivity, requiring O($V^2)$ space regardless of the number of edges E.
Space complexity of an adjacency list representation for a graph with V vertices and E edges is -
Adjacency lists store an array of V list heads along with node entries for all E edges, taking memory proportional to O(V + E).
In a full binary tree (every internal node has exactly two children), if there are L leaves, how many internal nodes are there?
Let I be the number of internal nodes. Every internal node contributes two child edges, so the tree has 2I edges. A tree with I+L total nodes has I+L-1 edges. Equating gives 2I=I+L-1, hence $I=L-1$.
Topological sorting can be performed only on which type of graph?
Topological sorting provides a linear ordering of vertices such that for every directed edge u -> v, u comes before v, which is valid only for DAGs.