Greedy Strategy Interview Question Part 1

1. Huffman’s greedy algorithm
a is a lossy compression technique
b. computes frequency of occurrence of characters
c. assigns binary codes to a string of characters
d. b and c
Ans. d

2. Huffman’s greedy algorithm has a total running time of
a. O(log n)
b.O(n)
c. O(nlogn)
d. O(n*n)
Ans. c

3. Greedy algorithms are used for
i)optimization problems
ii)always make a locally optimal choice
iii)widely applied:Dijkstra’s algorithm and MST
The correct options are
a)i and ii
b)i and iii
c)all of the above
d)only i
Ans. c
4. A graph may have ________ number of spanning trees.
Ans. many
5. Kruskal’s algorithm is also known as _________ algorithm.
Ans. Greedy algorithm
6. Kruskal’s algorithm works faster on sparse graphs.( True or False).
Ans. True
7. Every spanning tree on n points contains exactly
a. n edges
b. n-1 edges
c. n(n-1) edges
d. n-2 edges
Ans . b
8. the time required by Kruskal’s algorithm is _______ where E stands for edges and V for vertices
a. O( |E| + log |V| )
b. O( ElogV)
c. O( |E|log|V| )
d. O( log |V| )
Ans. c
9. A minimum spanning tree is a minimum-weight tree in a ________ graph which contains all of the graph’s vertices.
Ans. weighted
10. Travelling salesman problem can be best solved by using a
a. Minimum spanning tree algorithm
b. Dijkstra algorithm
c. Floyd algorithm
d. None of the above
Ans. a