ThatQuiz Test Library Take this test now
Huffman Coding
Contributed by: Singh
  • 1. Who introduced Huffman Coding?
A) David A. Huffman
B) Robert Johnson
C) John Smith
D) Alice Jones
  • 2. Which type of encoding does Huffman Coding use?
A) Fixed-length encoding
B) Variable-length encoding
C) Binary encoding
D) ASCII encoding
  • 3. In Huffman Coding, what type of symbols have shorter codes?
A) Frequent symbols
B) Symbols starting with A
C) Symbols at odd indices
D) Rare 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 with equal-length codewords
D) A code that starts with the same symbol
  • 5. What is a Huffman tree also known as?
A) Optimal binary tree
B) Complete tree
C) Perfect tree
D) Balanced tree
  • 6. How is the efficiency of Huffman Coding usually measured?
A) Memory consumption
B) Compression ratio
C) Number of symbols
D) Encoding speed
  • 7. What's the worst-case time complexity of building a Huffman tree?
A) O(n2)
B) O(n log n)
C) O(log n)
D) O(n)
  • 8. Which step comes after building the Huffman tree in the encoding process?
A) Assigning binary codes to symbols
B) Calculating symbol frequencies
C) Compressing the data
D) Building a linked list
  • 9. In Huffman Coding, what symbol is typically assigned the shortest code?
A) Symbol with a prime number
B) Most frequent symbol
C) Least frequent symbol
D) Symbol with the longest name
  • 10. Which data structure is commonly used to implement a priority queue in Huffman Coding?
A) Queue
B) Linked list
C) Binary heap
D) Stack
  • 11. What kind of codes does Huffman Coding produce?
A) Prefix codes
B) Postfix codes
C) Suffix codes
D) Infix codes
  • 12. In which year was the paper 'A Method for the Construction of Minimum-Redundancy Codes' published?
A) 1949
B) 1955
C) 1952
D) 1960
  • 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) Stack
C) Array
D) Queue
  • 14. What is a common use of modified Huffman coding?
A) Audio file compression.
B) Fax machines.
C) Text compression in word processors.
D) Image encoding for web pages.
  • 15. Which university was David A. Huffman attending when he developed the algorithm?
A) MIT
B) Harvard University
C) Princeton University
D) Stanford University
  • 16. What happens to the two nodes with the smallest probability during Huffman tree construction?
A) They are removed from the tree
B) They are combined into a new internal node
C) They become root nodes
D) They remain as leaf nodes
  • 17. In the linear-time Huffman tree construction, where are initial weights enqueued?
A) The second queue
B) Neither queue
C) Both queues simultaneously
D) The first queue
  • 18. What is the formula for entropy H(A)?
A) H(A) = ∑(w_i > 0) log2(w_i)
B) H(A) = ∑(w_i > 0) h(a_i) / w_i
C) H(A) = ∑(w_i > 0) w_i / log2(w_i)
D) H(A) = -∑(w_i > 0) w_i * log2(w_i)
  • 19. 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 first queue
C) Choose the item in the second queue
D) Remove both items and start over
  • 20. How is the information content h(a_i) of a symbol ai defined?
A) h(a_i) = log2(1 / w_i)
B) h(a_i) = w_i * log2(w_i)
C) h(a_i) = -log2(w_i)
D) h(a_i) = 2w_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) Only compression-related problems.
D) Problems related to sorting data.
  • 22. Which method can replace Huffman coding if a better compression ratio is required?
A) Lempel-Ziv-Welch (LZW)
B) Shannon-Fano coding
C) Run-length encoding
D) Arithmetic coding
  • 23. What does bit '0' represent in a Huffman tree?
A) An internal node
B) Following the right child
C) A leaf node
D) Following the left child
  • 24. Who solved the Huffman coding problem with unequal letter costs?
A) T. C. Hu.
B) Alan Turing.
C) Richard M. Karp.
D) Adriano Garsia.
  • 25. What is required when using Huffman coding with unknown input probabilities?
A) An encryption key must accompany the compressed data.
B) The original text must be stored alongside the compressed version.
C) No additional information needs to be stored.
D) A frequency table must be stored with the compressed text.
  • 26. When constructing a Huffman tree using two queues, how do you ensure the lowest weight is always at the front?
A) By sorting both queues by weight after each insertion
B) By only enqueuing nodes with unique weights
C) By keeping initial weights in the first queue and combined weights in the second queue
D) By randomly selecting nodes from either queue
  • 27. What algorithm solves the problem of length-limited Huffman coding?
A) Template Huffman algorithm.
B) Adaptive Huffman algorithm.
C) Binary Huffman algorithm.
D) The package-merge algorithm.
  • 28. What is the contribution of a symbol with zero probability to entropy?
A) It equals the inverse of its weight
B) It contributes negatively to the entropy
C) It is equal to the symbol's information content
D) Zero, since lim_(w→0+) w * log2(w) = 0
  • 29. How many queues are used in the linear-time method to create a Huffman tree?
A) Two
B) Three
C) Four
D) One
  • 30. In alphabetic Huffman coding, what must be identical between inputs and outputs?
A) The frequency of occurrence.
B) The binary representation.
C) The transmission cost.
D) The alphabetic order.
Created with That Quiz — the math test generation site with resources for other subject areas.