Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 6
Q181:
What would be the maximum value obtainable with a weight limit of W = 11 using the items listed?
A. 22
B. 28
C. 40
D. 18
Correct Answer:
C
Chapter: 6
Q182:
If the weight of an item exceeds the current capacity of the knapsack, what happens?
A. The item can be included anyway
B. The item cannot be included
C. The item is halved
D. The item is removed from consideration
Correct Answer:
B
Chapter: 6
Q183:
How many items are there in the provided example of the 0/1 Knapsack Problem?
A. 5
B. 4
C. 3
D. 6
Correct Answer:
A
Chapter: 6
Q184:
Fill in the blank: The maximum capacity of the knapsack is denoted by _____.
A. W
B. The total weight
C. Total value
D. Number of items
Correct Answer:
A
Chapter: 6
Q185:
The dynamic programming approach computes the optimal solution in a ____ fashion.
A. Top-down
B. Bottom-up
C. Recursive
D. Iterative
Correct Answer:
B
Chapter: 6
Q186:
If the first four items of the example are chosen, what is the total weight?
A. 14
B. 20
C. 26
D. 10
Correct Answer:
A
Chapter: 6
Q187:
Which of the following is a characteristic of the 0/1 Knapsack Problem?
A. Partial item selection allowed
B. Multiple selections allowed
C. Each item can be included once or not at all
D. Items can be duplicated
Correct Answer:
C
Chapter: 6
Q188:
What is the result when using an auxiliary boolean array keep[i, j]?
A. It shows which items are included in the optimal solution.
B. It calculates the weight of the knapsack.
C. It indicates the maximum value.
D. It counts the number of items included.
Correct Answer:
A
Chapter: 6
Q189:
If the knapsack has a weight limit of W and the first n items are considered, what is the state of V[n, W]?
A. The maximum value of the first n items that can fit into the knapsack.
B. The weight of the items.
C. The total number of items.
D. The maximum weight of items.
Correct Answer:
A
Chapter: 7
Q190:
What is the main goal of an optimization problem?
A. To find any solution
B. To find the best solution
C. To minimize time only
D. To maximize complexity
Correct Answer:
B
Chapter: 7
Q191:
A greedy algorithm works in how many phases?
A. One phase
B. Two phases
C. Three phases
D. Multiple phases
Correct Answer:
D
Chapter: 7
Q192:
In a greedy algorithm, what does each phase focus on?
A. Finding the best future solution
B. Taking the best current option
C. Considering all possibilities
D. Minimizing time spent
Correct Answer:
B
Chapter: 7
Q193:
The Coin Change problem aims to minimize what?
A. The number of coins used
B. The denominations used
C. The total value of coins
D. The types of coins used
Correct Answer:
A
Chapter: 7
Q194:
Which of the following is a characteristic of greedy algorithms?
A. They always find the optimal solution
B. They sometimes find the optimal solution
C. They never find the optimal solution
D. They always fail
Correct Answer:
C
Chapter: 7
Q195:
In the U.S.A., what is the smallest denomination of coin?
A. One cent
B. Ten cents
C. Five cents
D. Twenty-five cents
Correct Answer:
A
Chapter: 7
Q196:
Which of the following is an example of a greedy algorithm?
A. Dynamic programming
B. Huffman encoding
C. Linear search
D. Coin change algorithm
Correct Answer:
C
Chapter: 7
Q197:
In a fictional monetary system with denominations of 1 kron, 7 kron, and 10 kron, what is the optimal way to make 15 krons?
A. Five 1 kron pieces and one 10 kron piece
B. One 10 kron and five 1 kron pieces
C. Two 7 kron pieces and one 1 kron piece
D. Three 5 kron pieces and zero coins
Correct Answer:
C
Chapter: 7
Q198:
What is the main characteristic of the coins in the greedy approach?
A. They are all even numbers
B. They are all odd numbers
C. They are powers of a fixed denomination
D. They are random values
Correct Answer:
C
Chapter: 7
Q199:
The dynamic programming solution for the Coin Change problem involves creating a table with what dimensions?
A. k x N
B. 1 x k
C. N x k
D. k x k
Correct Answer:
A
Chapter: 7
Q200:
What is the time complexity of the greedy algorithm for the Coin Change problem?
A. O(k)
B. O(N)
C. O(kN)
D. O(1)
Correct Answer:
A