Question 71
Which condition characterizes a bipartite graph?
A graph is bipartite if its vertices can be 2-coloured so that no edge connects vertices of the same colour. Equivalently, it has no odd-length cycle.
Which condition characterizes a bipartite graph?
A graph is bipartite if its vertices can be 2-coloured so that no edge connects vertices of the same colour. Equivalently, it has no odd-length cycle.
How many edges does a tree with V vertices contain?
A tree is connected and acyclic. Every connected acyclic graph with V vertices has exactly V-1 edges.
What is the maximum number of edges in a simple undirected graph with V vertices?
A simple undirected graph has at most one edge for each unordered pair of distinct vertices. The number of such pairs is the binomial coefficient V choose 2.
What is the load factor $\alpha of a hash table$ with n stored keys and m buckets?
The load factor measures average occupancy and is defined as the number of stored keys divided by the number of buckets: $\alpha =n/m$.
Which collision-resolution method is especially associated with primary clustering?
Linear probing checks consecutive slots. Occupied runs tend to grow and attract further collisions, producing primary clustering.