Sorting and Searching - common sorting and searching algorithms, hashing - Question Bank

1. What is the main purpose of rehashing in a dynamic hash table?
A) To decrease the load factor and maintain performance
B) To increase the load factor and save memory
C) To simplify the hash function
D) To remove duplicate keys
2. Which collision resolution technique uses a linked list at each array index to store elements that hash to the same value?
A) Linear Probing
B) Quadratic Probing
C) Separate Chaining
D) Double Hashing
3. What is the space complexity of Quick Sort (in-place version)?
A) O(1)
B) O(n)
C) O(log n) on average, O(n) in worst case
D) O(n^2)
4. Which searching algorithm has a worst-case time complexity of O(n) but can be faster than Binary Search if the element is likely to be near the beginning of the list?
A) Binary Search
B) Hashing
C) Linear Search
D) Interpolation Search
5. What is the primary advantage of using a hash table with a good hash function and collision resolution strategy?
A) Guaranteed worst-case performance
B) Simplicity of implementation
C) Fast average-case lookup, insertion, and deletion
D) Ability to sort data efficiently
6. Which sorting algorithm is generally considered the fastest for average-case performance on random data?
A) Merge Sort
B) Heap Sort
C) Quick Sort
D) Insertion Sort
7. What happens to the performance of hashing if the load factor becomes very high?
A) Performance improves due to more elements.
B) Performance degrades significantly due to increased collisions.
C) Performance remains constant.
D) Performance becomes O(log n).
8. Which of the following is NOT a common probing strategy for open addressing in hashing?
A) Linear Probing
B) Quadratic Probing
C) Block Probing
D) Double Hashing
9. What is the time complexity of Radix Sort for numbers with d digits and a base b?
A) O(d * (n + b))
B) O(n log n)
C) O(n^2)
D) O(d * n)
10. Which sorting algorithm can be used for non-numeric data like strings?
A) Heap Sort
B) Bubble Sort
C) Radix Sort
D) Selection Sort
11. In hashing, what is 'primary clustering'?
A) When keys hash to the same initial index.
B) When collisions cause long runs of occupied slots, affecting subsequent insertions.
C) When the hash table becomes too full.
D) When two different keys produce the same hash value.
12. What is the average time complexity of Jump Search on a sorted array?
A) O(n)
B) O(log n)
C) O(sqrt(n))
D) O(n log n)
13. Which searching algorithm involves jumping ahead by fixed steps and then performing a linear search?
A) Binary Search
B) Hashing
C) Linear Search
D) Jump Search
14. What is the worst-case space complexity for Merge Sort?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
15. Which sorting algorithm is known for its efficiency on large datasets and is often used in standard libraries?
A) Bubble Sort
B) Insertion Sort
C) Quick Sort
D) Selection Sort
16. In Quadratic Probing, if the initial hash index is h(k), the probe sequence is typically represented as:
A) h(k) + i
B) h(k) + c * i
C) h(k) + c1*i + c2*i^2
D) h(k) * i
17. Which of the following is a characteristic of a 'good' hash function?
A) It should be computationally intensive.
B) It should map similar keys to different indices.
C) It should be deterministic and produce a uniform distribution.
D) It should depend on the order of insertion.
18. What is the primary advantage of using a hash table over an array for lookups?
A) Guaranteed O(log n) lookup time
B) Ability to handle duplicate keys easily
C) Average O(1) lookup time
D) Lower memory overhead
19. Which sorting algorithm has a time complexity of O(n^k) where k is typically greater than 1, for certain inputs?
A) Merge Sort
B) Heap Sort
C) Quick Sort
D) Bubble Sort
20. What is the time complexity of searching for an element in a hash table when using Separate Chaining and assuming uniform hashing?
A) O(n)
B) O(log n)
C) O(1) on average
D) O(n^2)
21. Which searching algorithm can be used on unsorted data?
A) Binary Search
B) Hashing
C) Linear Search
D) Jump Search
22. What is the primary disadvantage of Quadratic Probing compared to Linear Probing?
A) It suffers more from primary clustering
B) It can lead to secondary clustering
C) It is always slower
D) It requires more memory
23. Which collision resolution technique uses a secondary hash function to determine the step size for probing?
A) Linear Probing
B) Quadratic Probing
C) Separate Chaining
D) Double Hashing
24. In the context of hashing, what is the 'load factor'?
A) The number of elements in the hash table
B) The ratio of the number of elements to the table size
C) The average number of probes per operation
D) The size of the hash table
25. What is the main advantage of Shell Sort over Insertion Sort?
A) It is always faster
B) It has a better worst-case time complexity
C) It is simpler to implement
D) It requires less memory
26. Which of the following is a stable sorting algorithm?
A) Quick Sort
B) Heap Sort
C) Merge Sort
D) Selection Sort
27. What is the time complexity of Heap Sort?
A) O(n^2)
B) O(n log n)
C) O(n)
D) O(log n)
28. Which sorting algorithm uses a heap data structure?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Radix Sort
29. What is the space complexity of Bubble Sort and Selection Sort (in-place versions)?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
30. Which sorting algorithm is adaptive, meaning its performance improves if the input array is already partially sorted?
A) Heap Sort
B) Merge Sort
C) Insertion Sort
D) Selection Sort
31. What is the main goal of a good hash function?
A) To produce as many collisions as possible
B) To distribute keys uniformly across the hash table
C) To always return the same index for all keys
D) To be computationally very expensive
32. Which of the following is NOT a common hash function?
A) Division Method
B) Multiplication Method
C) Modulo Method
D) Prime Factorization Method
33. What is the ideal time complexity for search, insertion, and deletion operations in a hash table with no collisions?
A) O(n)
B) O(log n)
C) O(1)
D) O(n log n)
34. Separate Chaining is a collision resolution technique where each slot in the hash table points to what?
A) Another hash table
B) A linked list of elements that hash to that slot
C) A binary search tree
D) A static array
35. Which collision resolution technique involves probing for the next available slot in a linear fashion?
A) Separate Chaining
B) Quadratic Probing
C) Double Hashing
D) Linear Probing
36. What is a collision in the context of hashing?
A) When two keys map to the same index
B) When a key is not found in the hash table
C) When the hash table is full
D) When the hash function generates a negative index
37. Which searching technique uses a hash function to map keys to indices in an array?
A) Linear Search
B) Binary Search
C) Hashing
D) Interpolation Search
38. What is the average time complexity of Binary Search?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(1)
39. In Binary Search, at each step, how is the search space reduced?
A) By eliminating half of the remaining elements
B) By checking only the next element
C) By comparing with the first and last elements
D) By moving one element at a time
40. What is the time complexity of Linear Search in the worst case?
A) O(log n)
B) O(n)
C) O(n log n)
D) O(1)
41. Which searching algorithm requires the data to be sorted beforehand?
A) Linear Search
B) Binary Search
C) Hashing
D) Jump Search
42. What is the worst-case time complexity of Quick Sort?
A) O(n log n)
B) O(n)
C) O(n^2)
D) O(log n)
43. Which sorting algorithm works by repeatedly finding the minimum element from the unsorted part and putting it at the beginning?
A) Bubble Sort
B) Selection Sort
C) Insertion Sort
D) Merge Sort
44. What is the primary advantage of Merge Sort over Quick Sort in certain scenarios?
A) It is generally faster in practice
B) It is stable and guarantees O(n log n) performance
C) It requires less auxiliary space
D) It is easier to implement
45. In Insertion Sort, how is an element inserted into its correct position in the already sorted part of the array?
A) By swapping with the next element until it's in place
B) By shifting larger elements to the right
C) By performing a binary search for its position
D) By using a temporary variable
46. Which sorting algorithm has a time complexity of O(n log n) in all cases (best, average, and worst)?
A) Quick Sort
B) Heap Sort
C) Bubble Sort
D) Insertion Sort
47. What is the best-case time complexity of Bubble Sort?
A) O(n^2)
B) O(n log n)
C) O(n)
D) O(1)
48. Which sorting algorithm divides the list into two halves, sorts them recursively, and then merges the sorted halves?
A) Insertion Sort
B) Selection Sort
C) Merge Sort
D) Shell Sort
49. What is the average time complexity of Quick Sort?
A) O(n log n)
B) O(n^2)
C) O(n)
D) O(log n)
50. Which sorting algorithm is known for its simplicity and is often taught first, but has a worst-case time complexity of O(n^2)?
A) Merge Sort
B) Quick Sort
C) Bubble Sort
D) Heap Sort
All Question Banks
E-Book Sorting and Searching - common sorting and searching algorithms, hashing One Line Questions Sorting and Searching - common sorting and searching algorithms, hashing Online Test Sorting and Searching - common sorting and searching algorithms, hashing