Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 4
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)
Correct Answer:
C
Chapter: 4
Q102:
Which sorting algorithm requires extra array storage to function?
A. Quick sort
B. Bubble sort
C. Mergesort
D. Insertion sort
Correct Answer:
C
Chapter: 4
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
Correct Answer:
D
Chapter: 5
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
Correct Answer:
B
Chapter: 5
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
Correct Answer:
A
Chapter: 5
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
Correct Answer:
C
Chapter: 5
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)
Correct Answer:
A
Chapter: 5
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
Correct Answer:
B
Chapter: 5
Q109:
The final sorted output in Counting Sort is stored in which array?
A. A
B. B
C. C
D. D
Correct Answer:
B
Chapter: 5
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
Correct Answer:
C
Chapter: 5
Q111:
In Counting Sort, the process of filling the output array B from the input array A is done in ____.
A. Ascending order
B. Descending order
C. Random order
D. Backward order
Correct Answer:
D
Chapter: 5
Q112:
Which variable in Counting Sort determines the final placement of elements in the output array?
A. k
B. A[j]
C. B[i]
D. C[x]
Correct Answer:
D
Chapter: 5
Q113:
What is the first step in the Counting Sort algorithm?
A. Initialize C
B. Calculate A
C. Initialize B
D. Copy elements to B
Correct Answer:
A
Chapter: 5
Q114:
Fill in the blank: Counting Sort is particularly effective when _____.
A. Elements are even
B. Range of values is small
C. Range is very large
D. Values are floating-point numbers
Correct Answer:
B
Chapter: 5
Q115:
Which operation is repeatedly applied to update array C in Counting Sort?
A. Addition
B. Comparison
C. Subtraction
D. Multiplication
Correct Answer:
A
Chapter: 5
Q116:
What is the main purpose of a bucket sort algorithm?
A. Sorting elements in ascending order
B. Storing elements
C. Counting elements
D. Filtering elements
Correct Answer:
A
Chapter: 5
Q117:
Bucket Sort is efficient when keys lie within a _______.
A. large fixed range
B. small fixed range
C. variable range
D. indefinite range
Correct Answer:
B
Chapter: 5
Q118:
In bucket sort, the collection is sorted after which step?
A. Placing items in bins
B. Sorting items within bins
C. Examining each bin
D. Removing items from bins
Correct Answer:
C
Chapter: 5
Q119:
The time complexity of Bucket Sort is O(______) under optimal conditions.
A. n + m
B. n
C. m
D. n*m
Correct Answer:
A
Chapter: 5
Q120:
If the number of bins (m) is much greater than the number of items (n), the Bucket Sort time complexity becomes O(______).
A. m
B. n
C. n^2
D. log(n)
Correct Answer:
A