Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 7
Q201:
Huffman encoding uses what type of codes?
A. Fixed-length codes
B. Variable-length codes
C. Random-length codes
D. Character codes
Correct Answer:
B
Chapter: 7
Q202:
What is the expected length of a string encoded with Huffman coding compared to ASCII?
A. Shorter
B. Longer
C. The same
D. Unpredictable
Correct Answer:
A
Chapter: 7
Q203:
In Huffman encoding, how do you determine the frequency of each character?
A. By analyzing the frequency of use in the world
B. By parsing the message string
C. By asking the user
D. By random assignment
Correct Answer:
B
Chapter: 7
Q204:
What does the prefix property in Huffman coding ensure?
A. No codeword is a prefix of another codeword
B. All codewords are the same length
C. All characters are represented equally
D. Every character has a unique codeword
Correct Answer:
A
Chapter: 7
Q205:
How does the cost of an encoding tree T relate to the character probabilities?
A. It is independent of the probabilities
B. It decreases as the probabilities increase
C. It increases as the probabilities decrease
D. It reflects the expected number of bits needed to encode text
Correct Answer:
D
Chapter: 7
Q206:
If a string has 10 characters, what is the length of the encoded string using 8-bit ASCII?
A. 10 bits
B. 80 bits
C. 60 bits
D. 40 bits
Correct Answer:
B
Chapter: 7
Q207:
The greedy approach in Huffman encoding aims to minimize which of the following?
A. The total length of the encoded string
B. The number of characters
C. The size of the tree
D. The time taken to encode text
Correct Answer:
A
Chapter: 7
Q208:
Fill in the blank: A greedy algorithm sometimes produces a solution that is optimal and is called a __________.
A. greedy heuristic
B. greedy approximation
C. greedy algorithm
D. greedy function
Correct Answer:
A
Chapter: 7
Q209:
Fill in the blank: The __________ algorithm for the coin change problem sets up a table for minimum coins required.
A. dynamic programming
B. greedy
C. hierarchical
D. direct search
Correct Answer:
A
Chapter: 7
Q210:
What is the main difference between the 0-1 knapsack problem and the fractional knapsack problem?
A. Only whole items can be taken in 0-1 knapsack
B. Only fractions of items can be taken in fractional knapsack
C. Both allow fractional items
D. Neither allow fractions
Correct Answer:
A
Chapter: 7
Q211:
In the fractional knapsack problem, which algorithm is typically used to find an optimal solution?
A. Brute force algorithm
B. Recursive algorithm
C. Greedy algorithm
D. Dynamic programming algorithm
Correct Answer:
C
Chapter: 7
Q212:
What does ρi represent in the context of the fractional knapsack problem?
A. Value per unit weight ratio
B. Weight of the item
C. Value of the item
D. Total weight of all items
Correct Answer:
A
Chapter: 7
Q213:
When applying the greedy approach to the fractional knapsack problem, items are sorted based on what criteria?
A. Weight
B. Value
C. Weight to value ratio
D. Total value
Correct Answer:
C
Chapter: 7
Q214:
In the greedy solution for the fractional knapsack, if an item does not fit completely, what is done?
A. The item is not taken at all
B. A fraction of the item is taken
C. The item is discarded
D. The item is prioritized for later
Correct Answer:
B
Chapter: 7
Q215:
Which of the following statements about the greedy algorithm for the fractional knapsack problem is true?
A. It is optimal
B. It is non-optimal
C. It does not consider item value
D. It only works for small weights
Correct Answer:
A
Chapter: 7
Q216:
In the example of the 0-1 knapsack problem, what is the total value obtained by taking weights of 5, 20, and 30?
A. 220
B. 260
C. 300
D. 90
Correct Answer:
A
Chapter: 7
Q217:
If a thief is collecting gold, silver, and bronze, which will they take first according to the greedy strategy?
A. Bronze
B. Silver
C. Gold
D. All equally
Correct Answer:
A
Chapter: 7
Q218:
In the context of the fractional knapsack problem, if an item has a weight of 40 and does not fit, what is done?
A. Ignore the item
B. Wait for more space
C. Take as much as possible
D. Resort the items
Correct Answer:
C
Chapter: 7
Q219:
The greedy algorithm is optimal for which of the following knapsack problems?
A. 0-1 knapsack problem
B. Fractional knapsack problem
C. Both A and B
D. Neither A nor B
Correct Answer:
B
Chapter: 7
Q220:
How does the greedy algorithm determine which item to take next?
A. Based on weight only
B. Based on total value
C. Based on value to weight ratio
D. Based on item availability
Correct Answer:
C