Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 2
Q41:
According to the limit rule, if f(n)/g(n) approaches a constant c (c > 0) as n → ∞, then f(n) ∈ ______.
A. Θ(g(n))
B. O(g(n))
C. Ω(g(n))
D. None of these
Correct Answer:
A
Chapter: 2
Q42:
If f(n) = 8n^2 + 2n - 3, which of these could serve as a lower bound constant in Θ-notation?
A. 7
B. 2
C. 10
D. √3
Correct Answer:
A
Chapter: 2
Q43:
Which complexity class denotes algorithms with exponential time complexity?
A. Θ(n^2)
B. Θ(2^n)
C. Θ(log n)
D. Θ(1)
Correct Answer:
B
Chapter: 2
Q44:
Fill in the blank: Asymptotic notation focuses on how functions behave as ______ becomes large.
A. n
B. g(n)
C. f(n)
D. c
Correct Answer:
A
Chapter: 2
Q45:
In Θ-notation, which of the following does NOT need to be specified?
A. Upper bound
B. Lower bound
C. Exact function
D. Both upper and lower bounds
Correct Answer:
C
Chapter: 2
Q46:
Fill in the blank: To prove f(n) ∈ O(g(n)), you need to establish a(n) ______ bound.
A. asymptotic
B. upper
C. lower
D. exact
Correct Answer:
B
Chapter: 2
Q47:
Which function's growth rate would typically fall into Θ(n log n) class?
A. Binary search
B. Merge sort
C. Linear search
D. Exponential calculation
Correct Answer:
B
Chapter: 3
Q48:
What is the primary strategy of "Divide and Conquer"?
A. Breaking problems into parts
B. Combining results without recursion
C. Using only one step to solve
D. Ignoring smaller problems
Correct Answer:
A
Chapter: 3
Q49:
In the "Conquer" step of Divide and Conquer, what is generally done?
A. Problems are ignored
B. Problems are combined directly
C. Each piece is solved recursively
D. All pieces are re-sorted
Correct Answer:
C
Chapter: 3
Q50:
Which sorting algorithm is used as an example of the Divide and Conquer strategy?
A. Quick Sort
B. Bubble Sort
C. Merge Sort
D. Selection Sort
Correct Answer:
C
Chapter: 3
Q51:
What is the purpose of the Merge Sort algorithm?
A. To decrease elements
B. To sort elements in descending order
C. To multiply elements
D. To sort elements in increasing order
Correct Answer:
D
Chapter: 3
Q52:
What is the first step in the Merge Sort algorithm?
A. Combine
B. Divide
C. Compare
D. Sort
Correct Answer:
B
Chapter: 3
Q53:
In the Divide step of Merge Sort, how is the array A split?
A. Into quarters
B. Into single elements
C. Into two halves
D. Into four sections
Correct Answer:
C
Chapter: 3
Q54:
What does the Merge function do in the Merge Sort algorithm?
A. Adds a constant to elements
B. Sorts elements without recursion
C. Merges two sorted lists
D. Compares every pair of elements
Correct Answer:
C
Chapter: 3
Q55:
The recursion tree used in analyzing Merge Sort represents what?
A. A divide-only process
B. Only the final merge
C. The entire recursion process
D. A non-recursive process
Correct Answer:
C
Chapter: 3
Q56:
Fill in the blank: The Merge Sort algorithm is an example of the __________ strategy.
A. brute force
B. divide and conquer
C. recursive sorting
D. heap
Correct Answer:
B
Chapter: 3
Q57:
In Merge Sort, if the array has only one element, what happens?
A. It is ignored
B. It is split again
C. It is returned as sorted
D. It is merged with other arrays
Correct Answer:
C
Chapter: 3
Q58:
What does the time complexity Θ(n log n) indicate about Merge Sort?
A. It takes linear time
B. It is slower than other sorting algorithms
C. It is efficient for large inputs
D. It requires multiple passes through the data
Correct Answer:
C
Chapter: 3
Q59:
During the Combine phase of Merge Sort, if two elements are equal, what happens?
A. The smaller element is discarded
B. They are merged without copying
C. They are copied in original order
D. Sorting stops
Correct Answer:
C
Chapter: 4
Q60:
What is one reason for focusing on sorting in software systems?
A. It makes the system faster
B. It increases memory usage
C. It helps in efficient algorithm design
D. It enhances software security
Correct Answer:
C