Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 5
Q121:
In a bucket sort with linked lists, what operation is required to add an item to a bin's linked list?
A. O(n)
B. O(m)
C. O(1)
D. O(log n)
Correct Answer:
C
Chapter: 5
Q122:
In bucket sort, the step to "link all lists into one list" takes _____.
A. O(n)
B. O(m)
C. O(n + m)
D. O(log m)
Correct Answer:
B
Chapter: 5
Q123:
Which of the following describes Radix Sort?
A. Sorts numbers one digit at a time
B. Sorts numbers based on key
C. Sorts numbers in random order
D. Sorts numbers by bin range
Correct Answer:
A
Chapter: 5
Q124:
Radix Sort is advantageous for sorting large _______.
A. small integers
B. small characters
C. large integers
D. short text
Correct Answer:
C
Chapter: 5
Q125:
In Radix Sort, stable sorting occurs with respect to the ______ digit first.
A. highest order
B. second lowest order
C. lowest order
D. any random
Correct Answer:
C
Chapter: 5
Q126:
The Bucket Sort algorithm's sorting order depends on ______.
A. bin placement
B. linked list usage
C. initial array order
D. item uniqueness
Correct Answer:
A
Chapter: 5
Q127:
What is a limitation of counting sort, addressed by Radix Sort?
A. Small data storage
B. Requires linked lists
C. Limited to small integers
D. Needs sorting in O(n*m)
Correct Answer:
C
Chapter: 5
Q128:
Which data structure can replace bins in Bucket Sort for duplicate handling?
A. Stacks
B. Queues
C. Linked lists
D. Binary trees
Correct Answer:
C
Chapter: 5
Q129:
The time complexity of Radix Sort for n elements, each d digits, is O(______).
A. n+d
B. nd
C. d^2
D. 2n
Correct Answer:
B
Chapter: 5
Q130:
Which algorithm is better suited for data with wide-ranging integer values?
A. Bucket Sort
B. Radix Sort
C. Insertion Sort
D. Bubble Sort
Correct Answer:
B
Chapter: 5
Q131:
What does T(n) = c1n + c2m represent in bucket sort?
A. Number of bins
B. Total time complexity
C. Array order
D. Number of linked lists
Correct Answer:
B
Chapter: 6
Q132:
What is the Fibonacci sequence?
A. A sequence where each number is the sum of the previous two numbers
B. A sequence where each number is doubled from the previous one
C. A sequence of prime numbers
D. A sequence of even numbers
Correct Answer:
A
Chapter: 6
Q133:
Who introduced the Fibonacci sequence to Europe?
A. Leonardo Pisano
B. Isaac Newton
C. Albert Einstein
D. Galileo Galilei
Correct Answer:
A
Chapter: 6
Q134:
Which algorithm is used to compute Fibonacci numbers with memoization?
A. MEMOFIB
B. ITERFIB
C. RECFLIB
D. FIB
Correct Answer:
A
Chapter: 6
Q135:
What is the time complexity of the iterative Fibonacci algorithm?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(1)
Correct Answer:
A
Chapter: 6
Q136:
The edit distance measures the minimum number of ______ required to change one string into another.
A. insertions, deletions, substitutions
B. only deletions
C. only substitutions
D. only insertions
Correct Answer:
A
Chapter: 6
Q137:
In edit distance, changing a letter counts as a ______.
A. insertion
B. deletion
C. substitution
D. none of the above
Correct Answer:
C
Chapter: 6
Q138:
What does the term 'memoization' refer to in dynamic programming?
A. Storing results of expensive function calls and reusing them
B. Caching data in the database
C. Compressing data for storage
D. Writing data to a file
Correct Answer:
A
Chapter: 6
Q139:
In the edit distance algorithm, what does E(i, j) represent?
A. The edit distance between the first i characters of string A and the first j characters of string B
B. The edit distance between all characters of strings A and B
C. The total number of characters in string A
D. The total number of characters in string B
Correct Answer:
A
Chapter: 6
Q140:
What are the possible operations in calculating edit distance?
A. Only insertion and deletion
B. Insertion, deletion, and substitution
C. Only substitution
D. None of the above
Correct Answer:
B