Exam prep

What advantage does selecting a hash function at random from a large family provide?

• AIt ensures the hash table uses constant space.
• BIt guarantees that all inputs will hash to distinct buckets.
• CIt eliminates the need for a hash function altogether.
• DThe algorithm’s expected performance is good regardless of the input distribution.

What is the minimum height required for a binary decision tree that represents any comparison‑based sorting algorithm on n items?

• AExactly n
• BAt most log n
• CAt least log n
• DAt most n/2

What lower bound does the comparison model impose on the running time of sorting n items?

• AΩ(log n)
• BΩ(n)
• CΩ(n log n)
• DΩ(n^2)

When does a direct‑access array sort run in linear time?

• AWhen the key range u is Θ(n) and all keys are unique.
• BWhen the key range u is larger than n².
• CWhen the keys are strings of arbitrary length.
• DWhen the algorithm uses a comparison‑based method.

In radix sorting, which digit is considered the most significant?

• AThe digit that appears first in the input list.
• BThe digit representing the lowest place value (the “ones” digit).
• CThe digit with the largest numerical value regardless of position.
• DThe digit representing the highest place value (the “n’s” digit).

What property must a sorting algorithm have to correctly combine results from sorting by less significant digits after sorting by more significant digits?

• AStability – it preserves the relative order of equal keys.
• BIn‑place operation – it uses only O(1) extra space.
• CRandomness – it chooses pivots randomly.
• DDeterminism – it always produces the same output for the same input.

What is the time complexity of radix sort that uses counting sort on each digit and processes all digits?

• AΘ(n + u)
• BΘ(n log n)
• CΘ(u²)
• DΘ(n²)

How many base‑n digits are needed to represent a number up to u?

• A√u
• Bn log u
• Cu / n
• Dlog_n(u)