Huffman Coding

1. Who introduced Huffman Coding?

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

2. Which type of encoding does Huffman Coding use?

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

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

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

4. What is a prefix code in Huffman Coding?

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

5. What is a Huffman tree also known as?

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

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

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

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

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

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

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

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

A) Least frequent symbol
B) Symbol with a prime number
C) Most frequent symbol
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) Linked list
D) Binary heap

11. What kind of codes does Huffman Coding produce?

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

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

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

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

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

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

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

15. 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24. 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.

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

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

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

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

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

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

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

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

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

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

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

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

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