Question 91
Which hash function collision resolution method suffers from Primary Clustering?
Linear probing inserts colliding elements into adjacent sequential slots, creating long continuous blocks of occupied cells (primary clusters).
Which hash function collision resolution method suffers from Primary Clustering?
Linear probing inserts colliding elements into adjacent sequential slots, creating long continuous blocks of occupied cells (primary clusters).
What is the asymptotic time complexity of finding the Minimum Spanning Tree of a graph using Prim's algorithm with a Fibonacci Heap?
Using a Fibonacci Heap, Prim's decrease-key operation takes O(1) amortized time, giving a total runtime of O(E + V log V).
In a graph, a simple path that visits every vertex exactly once is called a:
A Hamiltonian path visits every vertex in the graph exactly once. (An Eulerian path visits every edge exactly once).
What is the time complexity of inserting N elements one by one into an initially empty Binary Search Tree in worst-case?
In worst-case (sorted input), inserting each element takes 1 + 2 + ... + $N = O(N^2)$ total time for an unbalanced BST.
What is the maximum number of leaf nodes in a binary tree of height h (where height of root is 0)?
In a full binary tree, level 0 has 1 node, level 1 has 2, ..., and level h has $2^h$ nodes, which are all leaf nodes.