This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Huffman Code”.

1. Which of the following algorithms is the best approach for solving Huffman codes?

a) exhaustive search

b) greedy algorithm

c) brute force algorithm

d) divide and conquer algorithm

View Answer

Explanation: Greedy algorithm is the best approach for solving the Huffman codes problem since it greedily searches for an optimal solution.

2. How many printable characters does the ASCII character set consists of?

a) 120

b) 128

c) 100

d) 98

View Answer

Explanation: Out of 128 characters in an ASCII set, roughly, only 100 characters are printable while the rest are non-printable.

3. Which bit is reserved as a parity bit in an ASCII set?

a) first

b) seventh

c) eighth

d) tenth

View Answer

Explanation: In an ASCII character set, seven bits are reserved for character representation while the eighth bit is a parity bit.

4. How many bits are needed for standard encoding if the size of the character set is X?

a) log X

b) X+1

c) 2X

d) X^{2}

View Answer

Explanation: If the size of the character set is X, then [log X] bits are needed for representation in a standard encoding.

5. The code length does not depend on the frequency of occurrence of characters.

a) true

b) false

View Answer

Explanation: The code length depends on the frequency of occurrence of characters. The more frequent the character occurs, the less is the length of the code.

6. In Huffman coding, data in a tree always occur?

a) roots

b) leaves

c) left sub trees

d) right sub trees

View Answer

Explanation: In Huffman encoding, data is always stored at the leaves of a tree inorder to compute the codeword effectively.

7. From the following given tree, what is the code word for the character ‘a’?

a) 011

b) 010

c) 100

d) 101

View Answer

Explanation: By recording the path of the node from root to leaf, the code word for character ‘a’ is found to be 011.

8. From the following given tree, what is the computed codeword for ‘c’?

a) 111

b) 101

c) 110

d) 011

View Answer

Explanation: By recording the path of the node from root to leaf, assigning left branch as 0 and right branch as 1, the codeword for c is 110.

9. What will be the cost of the code if character c_{i} is at depth d_{i} and occurs at frequency f_{i}?

a) c_{i}f_{i}

b) ∫c_{i}f_{i}

c) ∑f_{i}d_{i}

d) f_{i}d_{i}

View Answer

Explanation: If character c

_{i}is at depth d

_{i}and occurs at frequency f

_{i}, the cost of the codeword obtained is ∑f

_{i}d

_{i}.

10. An optimal code will always be present in a full tree.

a) true

b) false

View Answer

Explanation: An optimal tree will always have the property that all nodes are either leaves or have two children. Otherwise, nodes with one child could move up a level.

11. The type of encoding where no character code is the prefix of another character code is called?

a) optimal encoding

b) prefix encoding

c) frequency encoding

d) trie encoding

View Answer

Explanation: Even if the character codes are of different lengths, the encoding where no character code is the prefix of another character code is called prefix encoding.

12. What is the running time of the Huffman encoding algorithm?

a) O(C)

b) O(log C)

c) O(C log C)

d) O( N log C)

View Answer

Explanation: If we maintain the trees in a priority queue, ordered by weight, then the running time is given by O(C log C).

13. What is the running time of the Huffman algorithm, if its implementation of the priority queue is done using linked lists?

a) O(C)

b) O(log C)

c) O(C log C)

d) O(C^{2})

View Answer

Explanation: If the implementation of the priority queue is done using linked lists, the running time of Huffman algorithm is O(C

^{2}).

**Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.**

To practice all areas of Data Structures & Algorithms, __here is complete set of 1000+ Multiple Choice Questions and Answers__.