Huffman Coding
  • 1. Who introduced Huffman Coding?
A) Alice Jones
B) Robert Johnson
C) David A. Huffman
D) John Smith
  • 2. Which type of encoding does Huffman Coding use?
A) ASCII encoding
B) Variable-length encoding
C) Fixed-length encoding
D) Binary encoding
  • 3. In Huffman Coding, what type of symbols have shorter codes?
A) Symbols at odd indices
B) Frequent symbols
C) Rare symbols
D) Symbols starting with A
  • 4. What is a prefix code in Huffman Coding?
A) A code that starts with the same symbol
B) A code that uses only 0s and 1s
C) A code where no codeword is a prefix of another
D) A code with equal-length codewords
  • 5. What is a Huffman tree also known as?
A) Complete tree
B) Perfect tree
C) Balanced tree
D) Optimal binary tree
  • 6. How is the efficiency of Huffman Coding usually measured?
A) Memory consumption
B) Number of symbols
C) Compression ratio
D) Encoding speed
  • 7. What's the worst-case time complexity of building a Huffman tree?
A) O(log n)
B) O(n log n)
C) O(n2)
D) O(n)
  • 8. Which step comes after building the Huffman tree in the encoding process?
A) Building a linked list
B) Compressing the data
C) Assigning binary codes to symbols
D) Calculating symbol frequencies
  • 9. In Huffman Coding, what symbol is typically assigned the shortest code?
A) Most frequent symbol
B) Least 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) Queue
B) Linked list
C) Binary heap
D) Stack
  • 11. What kind of codes does Huffman Coding produce?
A) Infix codes
B) Postfix codes
C) Prefix codes
D) Suffix codes
  • 12. In which year was the paper 'A Method for the Construction of Minimum-Redundancy Codes' published?
A) 1952
B) 1960
C) 1955
D) 1949
  • 13. Which method can replace Huffman coding if a better compression ratio is required?
A) Arithmetic coding
B) Shannon-Fano coding
C) Run-length encoding
D) Lempel-Ziv-Welch (LZW)
  • 14. How is the information content h(a_i) of a symbol ai defined?
A) h(a_i) = w_i * log2(w_i)
B) h(a_i) = log2(1 / w_i)
C) h(a_i) = 2w_i
D) h(a_i) = -log2(w_i)
  • 15. What is the formula for entropy H(A)?
A) H(A) = ∑(w_i > 0) h(a_i) / w_i
B) H(A) = -∑(w_i > 0) w_i * log2(w_i)
C) H(A) = ∑(w_i > 0) w_i / log2(w_i)
D) H(A) = ∑(w_i > 0) log2(w_i)
  • 16. What is the contribution of a symbol with zero probability to entropy?
A) It equals the inverse of its weight
B) Zero, since lim_(w→0+) w * log2(w) = 0
C) It is equal to the symbol's information content
D) It contributes negatively to the entropy
  • 17. What does bit '0' represent in a Huffman tree?
A) Following the left child
B) Following the right child
C) A leaf node
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) Priority queue
C) Stack
D) Queue
  • 19. How many queues are used in the linear-time method to create a Huffman tree?
A) One
B) Two
C) Four
D) Three
  • 20. In the linear-time Huffman tree construction, where are initial weights enqueued?
A) The second queue
B) Both queues simultaneously
C) The first queue
D) Neither queue
  • 21. 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 randomly selecting nodes from either queue
C) By keeping initial weights in the first queue and combined weights in the second queue
D) By only enqueuing nodes with unique weights
  • 22. How do you break ties between queues to minimize variance in Huffman coding?
A) Choose the item in the first queue
B) Randomly select an item from either queue
C) Remove both items and start over
D) Choose the item in the second queue
  • 23. 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 remain as leaf nodes
C) They are removed from the tree
D) They become root nodes
  • 24. What is a common use of modified Huffman coding?
A) Text compression in word processors.
B) Image encoding for web pages.
C) Fax machines.
D) Audio file compression.
  • 25. What kind of problems can Huffman template algorithms solve?
A) Minimizing the maximum weighted path length, among others.
B) Only compression-related problems.
C) Problems related to sorting data.
D) Problems that do not involve weights.
  • 26. 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.
  • 27. Who solved the Huffman coding problem with unequal letter costs?
A) Adriano Garsia.
B) T. C. Hu.
C) Richard M. Karp.
D) Alan Turing.
  • 28. In alphabetic Huffman coding, what must be identical between inputs and outputs?
A) The transmission cost.
B) The binary representation.
C) The alphabetic order.
D) The frequency of occurrence.
Created with That Quiz — the math test generation site with resources for other subject areas.