Greedy Strategy Interview Question Part 3

23. ___________ is to be sent with Huffman code for its decompression.
a. Original string
b. only tree
c. Only frequent occurring characters
d. Coded string
Ans. d
24. In Huffman coding,the code with highest frequency character contains _________ bit(s).
a. Maximum
b. Minimum
c. One
d. Equal
Ans. b
25. Greedy algorithms are
a. simple and straightforward
b. longsighted in approach
c. many problems can be solved correctly by greedy approach
d. all of the above
Ans. a
Greedy algorithms are simple and straightforward. They are shortsighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot be solved correctly by greedy approach. Greedy algorithms are used to solve optimization problems
26. To construct the solution in an optimal way,Greedy algorithm maintains two sets. One contains ___________ and the other contains ___________ .
Ans. chosen items and rejected items .
27. The greedy algorithm consists of following functions.
1. A function that checks whether chosen set of items provide a solution.
2. A function that checks the feasibility of a set.
3. The selection function tells which of the candidates is the most promising.
4. An objective function, which does not appear explicitly, gives the value of a solution.
The correct options are
a. 1 and 2
b. 2 and 4
c. 1,2 and 3
d. All the above
Ans. d
The greedy algorithm consists of four (4) function.
1. A function that checks whether chosen set of items provide a solution.
2. A function that checks the feasibility of a set.
3. The selection function tells which of the candidates is the most promising.
4. An objective function, which does not appear explicitly, gives the value of a solution.

28. The ____________ and _________________ are two ingredients in the problem that lend to a greedy strategy .
Ans. Greedy-choice property and optimal substructure.
The "greedy-choice property" and "optimal substructure" are two ingredients in the problem that lend to a greedy strategy.
29. A greedy strategy usually progresses in a _____________, making one greedy choice after another.
a. bottom-up fashion
b. linear fashion
c. top-down fashion
d. none of the above
Ans. c
A greedy strategy usually progresses in a top-down fashion, making one greedy choice after another, reducing each problem to a smaller one.
30. Greedy-Choice Property says that a globally optimal solution can be arrived at by making a ________ optimal choice.
Ans. locally
Greedy-Choice Property says that a globally optimal solution can be arrived at by making a locally optimal choice .
31. A spanning tree of a graph is any tree that includes every ________ in the graph.
Ans. vertex