This fourth Algorithms set covers sorting, searching and hashing, which are tested both as theory and as short tracing problems. You will compare the best, average and worst cases of common sorts, reason about stability and extra space, and trace binary search and hash table insertions.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 15 questions.
Topics covered in this set
- Quicksort, merge sort and heap sort
- Insertion, selection and bubble sort
- Comparison lower bound and non-comparison sorts
- Stability and in-place sorting
- Binary search and selection
- Hashing, collisions and load factor
Algorithms MCQs with answers and explanations
Q1. When does quicksort with the first element as the pivot show its worst-case O(n²) behaviour?
a) When the input is in random order
b) When all elements are distinct
c) When the input is already sorted
d) When n is a power of 2
Q2. Which statement about merge sort is correct?
a) It runs in O(n log n) in every case, is stable, and needs O(n) extra space for arrays
b) It is in-place and unstable
c) It only works on linked lists
d) Its worst case is O(n²)
Q3. Which of these sorting algorithms is NOT stable in its standard form?
a) Insertion sort
b) Counting sort
c) Merge sort
d) Heap sort
Q4. What is the lower bound on the worst-case number of comparisons for any comparison-based sorting algorithm on n elements?
a) Ω(n²)
b) Ω(n log n)
c) Ω(n)
d) Ω(log n)
Q5. Counting sort sorts n integers whose values lie in the range 0 to k. What is its time complexity?
a) O(k log n)
b) O(n log n)
c) O(nk)
d) O(n + k)
Q6. Radix sort processes integers digit by digit, starting from the least significant digit. What property must the sort used for each digit have?
a) It must be comparison-based
b) It must be in-place
c) It must be stable
d) It must be recursive
Q7. What is the best-case time complexity of insertion sort, and when does it occur?
a) O(n), when the input is already sorted
b) O(n²), when the input is sorted
c) O(n log n), on random input
d) O(1), when n is small
Q8. How many element shifts does insertion sort make when sorting the array [3, 1, 4, 2] into ascending order?
a) 3
b) 2
c) 4
d) 5
Q9. What is the array after the first full pass of bubble sort (ascending) on [5, 1, 4, 2, 8]?
a) [1, 4, 2, 5, 8]
b) [1, 2, 4, 5, 8]
c) [5, 1, 2, 4, 8]
d) [1, 5, 4, 2, 8]
Q10. In the worst case, how many comparisons does binary search need to search a sorted array of 1000 elements?
a) 9
b) 500
c) 11
d) 10
Q11. What is the average-case time complexity of quickselect for finding the k-th smallest element in an unsorted array?
a) O(log n)
b) O(n)
c) O(n log n)
d) O(n²)
Q12. What is the time complexity of building a binary heap from n unsorted elements using bottom-up heapify?
a) O(n²)
b) O(n log n)
c) O(log n)
d) O(n)
Q13. A hash table has 10 slots, uses h(k) = k mod 10 and linear probing. The keys 12, 22, 15, 32 and 25 are inserted in that order into an empty table. In which slot does 25 end up?
a) 4
b) 6
c) 7
d) 5
Q14. Which problem is linear probing especially prone to?
a) Primary clustering, where long runs of occupied slots form and grow
b) Needing a second hash function
c) Requiring the table size to be a power of 2
d) Unbounded memory use
Q15. A hash table with separate chaining has m slots and stores n keys. Under simple uniform hashing, what is the expected time for an unsuccessful search?
a) O(n)
b) O(log n)
c) O(m)
d) O(1 + α), where α = n/m is the load factor
Quick revision notes
- Quicksort: O(n log n) average, O(n²) worst, in-place, not stable. Merge sort: O(n log n) always, stable, O(n) extra space.
- Heap sort: O(n log n), in-place, not stable; bottom-up heap building is O(n).
- Comparison sorts need Ω(n log n); counting sort is O(n + k); radix sort needs a stable digit sort.
- Insertion sort: O(n) best case, shifts = inversions. Binary search: ⌊log₂ n⌋ + 1 comparisons in the worst case.
- Hashing: load factor α = n/m; chaining search O(1 + α); linear probing suffers primary clustering.
Frequently asked questions
Which sorting algorithm should I use in practice?
Use the built-in sort of your language. Most use hybrid algorithms such as Timsort or introsort, which combine merge sort or quicksort with insertion sort for small parts.
Why is quicksort often faster than merge sort despite its worse worst case?
It sorts in place, has good cache behaviour and small constant factors, and random pivots make the O(n²) case very unlikely.
What should I memorise for sorting questions?
Learn the best, average and worst case, extra space and stability of each common sort, and practise tracing one pass of each on a small array.
Comments
Post a Comment