C Programming Search & Sort MCQs
Search Algorithms in C (25 Questions)
1. What is the time complexity of linear search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n²)
Answer: C) O(n)
Linear search checks each element once in worst case, giving linear time complexity.
2. Binary search requires the array to be:
A) Unsorted
B) Partially sorted
C) Sorted
D) Any of the above
Answer: C) Sorted
Binary search relies on the array being sorted to efficiently divide the search space.
3. What is the time complexity of binary search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
Binary search halves the search space with each comparison, resulting in logarithmic time complexity.
4. Which search algorithm is best for unsorted data?
A) Binary search
B) Jump search
C) Linear search
D) Fibonacci search
Answer: C) Linear search
Linear search is the only option that works on unsorted data without preprocessing.
5. What is the base case for recursive binary search?
A) When array has 1 element
B) When element is found
C) When search space is empty
D) Both B and C
Answer: D) Both B and C
Recursion stops when the element is found or when the search space is exhausted.
6. Which search algorithm uses a hash function?
A) Binary search
B) Linear search
C) Hashing
D) Interpolation search
Answer: C) Hashing
Hashing uses a hash function to map keys to array indices for O(1) average case lookup.
7. What is the main advantage of interpolation search over binary search?
A) Works on unsorted data
B) Better for uniformly distributed data
C) Simpler implementation
D) No advantage
Answer: B) Better for uniformly distributed data
Interpolation search can achieve O(log log n) performance on uniformly distributed data.
8. Which search algorithm is best for very large datasets that don't fit in memory?
A) Linear search
B) Binary search
C) External search
D) B-tree search
Answer: D) B-tree search
B-trees are designed for efficient disk-based searching of large datasets.
9. What is the worst-case scenario for linear search?
A) Element is first
B) Element is middle
C) Element is last
D) Element not present
Answer: D) Element not present
The worst case occurs when the algorithm checks all elements without finding a match.
10. Which search algorithm is best when the data changes frequently?
A) Binary search
B) Linear search
C) Hashing
D) Jump search
Answer: B) Linear search
Linear search doesn't require any preprocessing or special data structure maintenance.
11. What is the main disadvantage of binary search?
A) Slow for small arrays
B) Requires sorted data
C) Complex implementation
D) High memory usage
Answer: B) Requires sorted data
Maintaining sorted data can be expensive for frequently changing datasets.
12. Which search algorithm is best for searching in a linked list?
A) Binary search
B) Linear search
C) Jump search
D) Interpolation search
Answer: B) Linear search
Linked lists don't support random access needed by other search algorithms.
13. What is the space complexity of iterative binary search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n²)
Answer: A) O(1)
Iterative binary search uses constant extra space for indices.
14. Which search algorithm is best when elements are accessed with non-uniform probabilities?
A) Binary search
B) Linear search
C) Self-organizing search
D) Fibonacci search
Answer: C) Self-organizing search
Self-organizing searches move frequently accessed elements toward the front.
15. What is the main advantage of jump search over binary search?
A) Faster for small arrays
B) Doesn't require random access
C) Simpler implementation
D) Works on unsorted data
Answer: C) Simpler implementation
Jump search is easier to implement while still providing O(√n) performance.
16. Which search algorithm is best for multidimensional arrays?
A) Binary search
B) Linear search
C) K-d tree search
D) Hashing
Answer: C) K-d tree search
K-d trees are space-partitioning data structures for organizing multidimensional data.
17. What is the time complexity of exponential search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
Exponential search has logarithmic complexity like binary search.
18. Which search algorithm is best for searching in a rotated sorted array?
A) Linear search
B) Binary search
C) Jump search
D) Fibonacci search
Answer: B) Binary search
A modified binary search can efficiently find elements in rotated sorted arrays.
19. What is the main advantage of ternary search over binary search?
A) Faster convergence
B) Works on unsorted data
C) Better for unimodal functions
D) No advantage
Answer: C) Better for unimodal functions
Ternary search is useful for finding maximum/minimum of unimodal functions.
20. Which search algorithm is best for searching in an infinite sorted array?
A) Linear search
B) Binary search
C) Exponential search
D) Fibonacci search
Answer: C) Exponential search
Exponential search first finds a range where the element may be present.
21. What is the main advantage of Fibonacci search over binary search?
A) Fewer comparisons
B) Works on unsorted data
C) Better for large datasets
D) No division operation
Answer: D) No division operation
Fibonacci search uses addition/subtraction instead of division which can be faster on some systems.
22. Which search algorithm is best when comparisons are expensive?
A) Linear search
B) Binary search
C) Interpolation search
D) Hashing
Answer: D) Hashing
Hashing typically requires just one comparison after computing the hash.
23. What is the time complexity of searching in a hash table with chaining?
A) O(1)
B) O(log n)
C) O(n)
D) Depends on load factor
Answer: D) Depends on load factor
With a good hash function and proper load factor, average case is O(1).
24. Which search algorithm is best for searching in a nearly sorted array?
A) Linear search
B) Binary search
C) Jump search
D) Adaptive search
Answer: D) Adaptive search
Adaptive algorithms can adjust their strategy based on how sorted the data is.
25. What is the main disadvantage of hashing for search?
A) High memory usage
B) Doesn't support range queries
C) Complex implementation
D) All of the above
Answer: D) All of the above
Hashing has several tradeoffs including these limitations.
Sorting Algorithms in C (25 Questions)
1. What is the time complexity of bubble sort in worst case?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
Answer: C) O(n²)
Bubble sort requires up to n² comparisons in the worst case.
2. Which sorting algorithm is most efficient for small datasets?
A) Merge sort
B) Quick sort
C) Insertion sort
D) Heap sort
Answer: C) Insertion sort
Insertion sort has low overhead and performs well on small datasets.
3. What is the best case time complexity of quick sort?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
Answer: B) O(n log n)
With good pivot selection, quick sort achieves n log n performance.
4. Which sorting algorithm is not comparison-based?
A) Merge sort
B) Quick sort
C) Counting sort
D) Heap sort
Answer: C) Counting sort
Counting sort uses key values to determine position directly.
5. What is the space complexity of merge sort?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
Merge sort requires additional space proportional to the input size.
6. Which sorting algorithm is in-place?
A) Merge sort
B) Quick sort
C) Counting sort
D) Radix sort
Answer: B) Quick sort
Quick sort uses only a small amount of additional space for recursion.
7. What is the worst case time complexity of selection sort?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
Answer: C) O(n²)
Selection sort always requires n² comparisons.
8. Which sorting algorithm is stable?
A) Quick sort
B) Heap sort
C) Merge sort
D) Selection sort
Answer: C) Merge sort
Merge sort preserves the relative order of equal elements.
9. What is the main advantage of heap sort?
A) Fastest for small datasets
B) Guaranteed O(n log n) performance
C) Stable sorting
D) Simple implementation
Answer: B) Guaranteed O(n log n) performance
Heap sort doesn't have a worst case scenario like quick sort.
10. Which sorting algorithm is best for nearly sorted data?
A) Bubble sort
B) Insertion sort
C) Selection sort
D) Quick sort
Answer: B) Insertion sort
Insertion sort approaches O(n) time for nearly sorted data.
11. What is the time complexity of radix sort?
A) O(n)
B) O(n log n)
C) O(nk) where k is digit length
D) O(n²)
Answer: C) O(nk) where k is digit length
Radix sort's complexity depends on the number of digits in the numbers.
12. Which sorting algorithm is typically used for external sorting?
A) Quick sort
B) Merge sort
C) Heap sort
D) Bubble sort
Answer: B) Merge sort
Merge sort is well-suited for external sorting due to its sequential access pattern.
13. What is the main disadvantage of quick sort?
A) Not stable
B) Worst case O(n²) performance
C) Complex implementation
D) All of the above
Answer: D) All of the above
Quick sort has several tradeoffs including these limitations.
14. Which sorting algorithm is best when memory writes are expensive?
A) Selection sort
B) Insertion sort
C) Merge sort
D) Quick sort
Answer: A) Selection sort
Selection sort minimizes writes with O(n) swaps.
15. What is the time complexity of shell sort?
A) O(n)
B) O(n log n)
C) Between O(n) and O(n²)
D) O(n²)
Answer: C) Between O(n) and O(n²)
Shell sort's complexity depends on the gap sequence used.
16. Which sorting algorithm is best for sorting linked lists?
A) Quick sort
B) Merge sort
C) Heap sort
D) Insertion sort
Answer: B) Merge sort
Merge sort is well-suited for linked lists due to sequential access.
17. What is the main advantage of timsort?
A) Fastest for small datasets
B) Adaptive to real-world data patterns
C) Simplest implementation
D) Lowest memory usage
Answer: B) Adaptive to real-world data patterns
Timsort combines merge sort and insertion sort to optimize for real data.
18. Which sorting algorithm is used by C's qsort() function?
A) Quick sort
B) Merge sort
C) Heap sort
D) Implementation-defined
Answer: D) Implementation-defined
The C standard doesn't specify the algorithm, but most implementations use quick sort.
19. What is the main advantage of counting sort?
A) Works for any data type
B) O(n) time for small integer ranges
C) In-place sorting
D) Simple implementation
Answer: B) O(n) time for small integer ranges
Counting sort can sort in linear time when the range of numbers is limited.
20. Which sorting algorithm is best when the data is uniformly distributed?
A) Bucket sort
B) Quick sort
C) Merge sort
D) Heap sort
Answer: A) Bucket sort
Bucket sort works well when data is uniformly distributed across a range.
21. What is the main disadvantage of merge sort?
A) Not stable
B) High memory usage
C) Worst case O(n²) performance
D) Complex implementation
Answer: B) High memory usage
Merge sort requires O(n) additional space.
22. Which sorting algorithm is best when stability is required and memory is limited?
A) Merge sort
B) Insertion sort
C) Quick sort
D) Heap sort
Answer: B) Insertion sort
Insertion sort is stable and in-place, though not the most efficient.
23. What is the main advantage of introsort?
A) Combines quick sort and heap sort
B) Always O(n log n)
C) In-place
D) All of the above
Answer: D) All of the above
Introsort combines the best features of quick sort and heap sort.
24. Which sorting algorithm is best when the range of keys is small compared to number of items?
A) Counting sort
B) Radix sort
C) Bucket sort
D) Any of the above
Answer: D) Any of the above
All these non-comparison sorts work well with limited key ranges.
25. What is the main advantage of cycle sort?
A) Fastest for small datasets
B) Minimal memory writes
C) Stable sorting
D) Simple implementation
Answer: B) Minimal memory writes
Cycle sort is optimal for situations where writes are expensive.
Related Resources