TRB PG Assistant - Sorting and Searching - common sorting and searching algorithms, hashing Online Test (MCQ Quiz)

1. 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

2. 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)

3. 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

4. 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)

5. 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

6. 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

7. 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

8. 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

9. 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)

10. Which searching algorithm requires the data to be sorted beforehand?

A) Linear Search B) Binary Search C) Hashing D) Jump Search

11. 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)

12. 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

13. What is the average time complexity of Binary Search?

A) O(n) B) O(n log n) C) O(log n) D) O(1)

14. 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

15. 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

16. 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

17. 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

18. 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)

19. Which of the following is NOT a common hash function?

A) Division Method B) Multiplication Method C) Modulo Method D) Prime Factorization Method

20. 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

21. 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

22. 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)

23. Which sorting algorithm uses a heap data structure?

A) Quick Sort B) Merge Sort C) Heap Sort D) Radix Sort

24. What is the time complexity of Heap Sort?

A) O(n^2) B) O(n log n) C) O(n) D) O(log n)

25. Which of the following is a stable sorting algorithm?

A) Quick Sort B) Heap Sort C) Merge Sort D) Selection Sort

26. 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

27. 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

28. 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

29. 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

30. Which searching algorithm can be used on unsorted data?

A) Binary Search B) Hashing C) Linear Search D) Jump Search

31. 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)

32. 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

33. 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

34. 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.

35. 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

36. 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

37. 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)

38. 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

39. 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)

40. 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.

41. Which sorting algorithm can be used for non-numeric data like strings?

A) Heap Sort B) Bubble Sort C) Radix Sort D) Selection Sort

42. 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)

43. 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

44. 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).

45. 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

46. 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

47. 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

48. 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)

49. 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

50. 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

Sorting and Searching - common sorting and searching algorithms, hashing - Online Test

Test Results