Huffman Coding

1. Who introduced Huffman Coding?

A) David A. Huffman
B) Robert Johnson
C) Alice Jones
D) John Smith

2. Which type of encoding does Huffman Coding use?

A) ASCII encoding
B) Binary encoding
C) Fixed-length encoding
D) Variable-length encoding

3. In Huffman Coding, what type of symbols have shorter codes?

A) Symbols starting with A
B) Symbols at odd indices
C) Frequent symbols
D) Rare symbols

4. What is a prefix code in Huffman Coding?

A) A code with equal-length codewords
B) A code that starts with the same symbol
C) A code that uses only 0s and 1s
D) A code where no codeword is a prefix of another

5. What is a Huffman tree also known as?

A) Optimal binary tree
B) Balanced tree
C) Perfect tree
D) Complete tree

6. How is the efficiency of Huffman Coding usually measured?

A) Compression ratio
B) Number of symbols
C) Encoding speed
D) Memory consumption

7. What's the worst-case time complexity of building a Huffman tree?

A) O(log n)
B) O(n)
C) O(n²)
D) O(n log n)

8. Which step comes after building the Huffman tree in the encoding process?

A) Building a linked list
B) Assigning binary codes to symbols
C) Compressing the data
D) Calculating symbol frequencies

9. In Huffman Coding, what symbol is typically assigned the shortest code?

A) Least frequent symbol
B) Most frequent symbol
C) Symbol with a prime number
D) Symbol with the longest name

10. Which data structure is commonly used to implement a priority queue in Huffman Coding?

A) Stack
B) Queue
C) Binary heap
D) Linked list

11. What kind of codes does Huffman Coding produce?

A) Infix codes
B) Suffix codes
C) Prefix codes
D) Postfix codes

12. In which year was the paper 'A Method for the Construction of Minimum-Redundancy Codes' published?

A) 1960
B) 1949
C) 1955
D) 1952

13. Which data structure is used for efficient insertion and retrieval of nodes by probability in a simple Huffman tree construction algorithm?

A) Priority queue
B) Array
C) Stack
D) Queue

14. What is a common use of modified Huffman coding?

A) Audio file compression.
B) Fax machines.
C) Image encoding for web pages.
D) Text compression in word processors.

15. Which university was David A. Huffman attending when he developed the algorithm?

A) Princeton University
B) Stanford University
C) MIT
D) Harvard University

16. What happens to the two nodes with the smallest probability during Huffman tree construction?

A) They are combined into a new internal node
B) They are removed from the tree
C) They remain as leaf nodes
D) They become root nodes

17. In the linear-time Huffman tree construction, where are initial weights enqueued?

A) Neither queue
B) Both queues simultaneously
C) The second queue
D) The first queue

18. What is the formula for entropy H(A)?

A) H(A) = ∑(w_i > 0) log₂(w_i)
B) H(A) = -∑(w_i > 0) w_i * log₂(w_i)
C) H(A) = ∑(w_i > 0) h(a_i) / w_i
D) H(A) = ∑(w_i > 0) w_i / log₂(w_i)

19. How do you break ties between queues to minimize variance in Huffman coding?

A) Choose the item in the first queue
B) Choose the item in the second queue
C) Remove both items and start over
D) Randomly select an item from either queue

20. How is the information content h(a_i) of a symbol ai defined?

A) h(a_i) = log₂(1 / w_i)
B) h(a_i) = w_i * log₂(w_i)
C) h(a_i) = -log₂(w_i)
D) h(a_i) = 2^w_i

21. What kind of problems can Huffman template algorithms solve?

A) Minimizing the maximum weighted path length, among others.
B) Problems that do not involve weights.
C) Problems related to sorting data.
D) Only compression-related problems.

22. Which method can replace Huffman coding if a better compression ratio is required?

A) Shannon-Fano coding
B) Arithmetic coding
C) Lempel-Ziv-Welch (LZW)
D) Run-length encoding

23. What does bit '0' represent in a Huffman tree?

A) Following the left child
B) A leaf node
C) Following the right child
D) An internal node

24. Who solved the Huffman coding problem with unequal letter costs?

A) Adriano Garsia.
B) Alan Turing.
C) T. C. Hu.
D) Richard M. Karp.

25. What is required when using Huffman coding with unknown input probabilities?

A) An encryption key must accompany the compressed data.
B) A frequency table must be stored with the compressed text.
C) No additional information needs to be stored.
D) The original text must be stored alongside the compressed version.

26. When constructing a Huffman tree using two queues, how do you ensure the lowest weight is always at the front?

A) By randomly selecting nodes from either queue
B) By keeping initial weights in the first queue and combined weights in the second queue
C) By sorting both queues by weight after each insertion
D) By only enqueuing nodes with unique weights

27. What algorithm solves the problem of length-limited Huffman coding?

A) Binary Huffman algorithm.
B) Adaptive Huffman algorithm.
C) Template Huffman algorithm.
D) The package-merge algorithm.

28. What is the contribution of a symbol with zero probability to entropy?

A) It contributes negatively to the entropy
B) It equals the inverse of its weight
C) It is equal to the symbol's information content
D) Zero, since lim_(w→0+) w * log₂(w) = 0

29. How many queues are used in the linear-time method to create a Huffman tree?

A) Four
B) Two
C) One
D) Three

30. In alphabetic Huffman coding, what must be identical between inputs and outputs?

A) The frequency of occurrence.
B) The transmission cost.
C) The binary representation.
D) The alphabetic order.

Created with That Quiz — the math test generation site with resources for other subject areas.