Heaps power priority queues and heapsort, and hash tables give near constant-time lookups - two ideas interviewers love to combine. This set covers heap properties, array representation, heap operations, hash functions, load factor and collision resolution.
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 16 questions.
Q1. In a max-heap, which statement is always true?
a) Every left child is smaller than the right child
b) Every parent is greater than or equal to its children
c) The array is fully sorted
d) Leaves always hold the smallest values in order
Q2. In an array-based binary heap with 0-based indexing, the children of the node at index i are at:
a) i + 1 and i + 2
b) 2i and 2i + 1
c) 2i + 1 and 2i + 2
d) i/2 and i/2 + 1
Q3. What is the time complexity of inserting an element into a binary heap of n elements?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Q4. Building a binary heap from an unsorted array of n elements using the bottom-up (heapify) method takes:
a) O(n)
b) O(n log n)
c) O(log n)
d) O(n^2)
Q5. What is the worst-case time complexity of heapsort?
a) O(n)
b) O(n log n)
c) O(n^2)
d) O(log n)
Q6. In a min-heap with n distinct elements, where can the largest element be?
a) At the root
b) Only at the last array index
c) At one of the leaf nodes
d) Exactly in the middle of the array
Q7. The array [90, 15, 10, 7, 12, 2] represents a valid max-heap. After deleting the maximum, what is the new array?
a) [15, 12, 10, 7, 2]
b) [15, 2, 10, 7, 12]
c) [12, 15, 10, 7, 2]
d) [15, 10, 12, 7, 2]
Q8. A priority queue is most efficiently implemented with a:
a) Sorted linked list
b) Binary heap
c) Stack
d) Unsorted array with binary search
Q9. The load factor of a hash table is defined as:
a) Number of collisions / table size
b) Number of stored keys / number of buckets
c) Table size / number of keys
d) Number of empty buckets / table size
Q10. Separate chaining resolves collisions by:
a) Probing the next empty slot
b) Storing all keys that hash to the same bucket in a linked list (or similar) at that bucket
c) Rehashing the whole table immediately
d) Rejecting the new key
Q11. With linear probing in a table of size 10 and hash function h(k) = k mod 10, the keys 12, 22 and 32 are inserted in that order. At which index is 32 stored?
a) 2
b) 3
c) 4
d) 5
Q12. Primary clustering is a problem mainly with which collision resolution technique?
a) Separate chaining
b) Linear probing
c) Double hashing
d) Perfect hashing
Q13. What is the average-case time to search a well-designed hash table with a low load factor?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Q14. What is the worst-case search time in a hash table that uses separate chaining?
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Q15. Why is a prime number often chosen as the table size when using the division method h(k) = k mod m?
a) Prime numbers make the table use less memory
b) It spreads keys more evenly when they share common patterns or factors
c) It makes hashing reversible
d) It removes all collisions
Q16. Which of these is NOT a desirable property of a hash function used in a hash table?
a) Fast to compute
b) Distributes keys uniformly
c) Same key always gives the same hash
d) Maps many different keys to the same index on purpose
Recommended MCQs
Comments
Post a Comment