Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q101: What is the worst-case time complexity of any comparison-based sorting algorithm?
- A: O(n log n)
- B: O(n^2)
- C: Ω(n log n)
- D: Ω(n^2)
View Answer
C
Q102: Which sorting algorithm requires extra array storage to function?
- A: Quick sort
- B: Bubble sort
- C: Mergesort
- D: Insertion sort
View Answer
C
Q103: What is the purpose of a comparison-based sorting algorithm's decision tree?
- A: To determine order only
- B: To visualize sorting steps
- C: To compare all permutations
- D: To identify sorting path
View Answer
D
Q104: In Counting Sort, what does array C store?
- A: Initial input values
- B: Rank of each element
- C: Final sorted elements
- D: Element frequencies
View Answer
B
Q105: Which of the following conditions must be true for Counting Sort to work efficiently?
- A: Array values are small
- B: Array is large
- C: Values are distinct
- D: Values are even
View Answer
A
Q106: What is the purpose of decrementing C[i] in the Counting Sort algorithm?
- A: To ensure accuracy
- B: To avoid duplicate entries
- C: To handle duplicates
- D: To reset the value
View Answer
C
Q107: What is the time complexity of Counting Sort when k=O(n)k = O(n)k=O(n)?
- A: Θ(n)
- B: Θ(n²)
- C: Θ(log n)
- D: Θ(n log n)
View Answer
A
Q108: Fill in the blank: Counting Sort is efficient for sorting elements that are in the range from _____.
- A: 1 to n
- B: 1 to k
- C: 1 to m
- D: 1 to p
View Answer
B
Q109: The final sorted output in Counting Sort is stored in which array?
- A: A
- B: B
- C: C
- D: D
View Answer
B
Q110: What does C[x] represent in Counting Sort once all updates are completed?
- A: Sum of sub-array
- B: Frequency of x
- C: Rank of x
- D: Position of x
View Answer
C