Q.1 What is the main purpose of Huffman coding?
Sorting data
Searching data
Data compression
Error detection
Explanation - Huffman coding is a greedy algorithm designed to compress data by assigning shorter codes to frequent characters and longer codes to infrequent ones.
Correct answer is: Data compression
Q.2 Huffman coding is based on which algorithmic technique?
Divide and Conquer
Dynamic Programming
Greedy Algorithm
Backtracking
Explanation - Huffman coding repeatedly picks the two smallest frequency nodes, making it a greedy approach.
Correct answer is: Greedy Algorithm
Q.3 In Huffman coding, characters with higher frequency get:
Longer codes
Shorter codes
Equal codes
No codes
Explanation - Frequent characters get shorter binary codes to minimize total encoded length.
Correct answer is: Shorter codes
Q.4 What type of tree does Huffman coding construct?
Binary Search Tree
AVL Tree
Binary Tree
B-Tree
Explanation - Huffman coding builds a binary tree where each leaf node represents a character.
Correct answer is: Binary Tree
Q.5 The complexity of Huffman coding using a priority queue is:
O(n log n)
O(n^2)
O(n)
O(log n)
Explanation - Building the Huffman tree requires repeatedly extracting minimums from a priority queue, leading to O(n log n).
Correct answer is: O(n log n)
Q.6 Which data structure is commonly used to implement Huffman coding?
Stack
Heap
Graph
Linked List
Explanation - A min-heap is used to efficiently extract the two smallest frequency nodes while building the Huffman tree.
Correct answer is: Heap
Q.7 Huffman codes are always:
Fixed length
Variable length
Encrypted
Sorted
Explanation - Huffman coding produces variable-length codes depending on character frequency.
Correct answer is: Variable length
Q.8 Huffman coding ensures that no code is a prefix of another. This property is called:
Prefix-free property
Unique decoding property
Greedy property
Optimal property
Explanation - Huffman codes are prefix-free, meaning no codeword is a prefix of another, ensuring unambiguous decoding.
Correct answer is: Prefix-free property
Q.9 Which of the following is NOT true about Huffman coding?
It is optimal for symbol-by-symbol coding
It may produce different codes for the same frequencies
It guarantees maximum compression always
It uses greedy approach
Explanation - Huffman coding is optimal for symbol-by-symbol coding, but not always for block or arithmetic coding.
Correct answer is: It guarantees maximum compression always
Q.10 Which of the following is an application of Huffman coding?
JPEG compression
PNG compression
MP3 compression
ZIP file compression
Explanation - Huffman coding is widely used in file compression formats like ZIP and GZIP.
Correct answer is: ZIP file compression
Q.11 Huffman coding assigns codes based on:
Alphabetical order
Frequency of characters
File size
Word length
Explanation - The encoding process depends on how frequently each character appears in the data.
Correct answer is: Frequency of characters
Q.12 What is the worst-case height of a Huffman tree with n symbols?
n
n-1
log n
n log n
Explanation - If frequencies are highly skewed, the Huffman tree can be skewed with height n-1.
Correct answer is: n-1
Q.13 The code generated by Huffman algorithm is always:
Unique
Non-unique
Ambiguous
Encrypted
Explanation - Different valid Huffman trees may exist, leading to different but equally optimal codes.
Correct answer is: Non-unique
Q.14 In Huffman coding, the average code length is minimized by:
Using fixed-length codes
Assigning longer codes to frequent characters
Assigning shorter codes to frequent characters
Random code assignment
Explanation - The greedy strategy ensures frequently occurring characters have shorter codes.
Correct answer is: Assigning shorter codes to frequent characters
Q.15 Huffman coding is optimal for:
Any probability distribution
Independent symbol coding
Only large files
Encrypted data
Explanation - It is proven to be optimal for independent symbol-by-symbol coding.
Correct answer is: Independent symbol coding
Q.16 If all characters occur with equal frequency, Huffman coding gives:
Fixed length codes
Variable length codes
No codes
Compressed output always
Explanation - If all frequencies are equal, Huffman coding produces equal length codes.
Correct answer is: Fixed length codes
Q.17 Huffman coding guarantees:
Maximum compression ratio
No data loss
Fixed code length
Faster encoding
Explanation - Huffman coding is a lossless compression algorithm, preserving original data.
Correct answer is: No data loss
Q.18 What happens if a character never occurs in the input?
It gets a short code
It gets no code
It gets maximum code
It is compressed to zero
Explanation - Only characters present in the input data are included in Huffman tree and assigned codes.
Correct answer is: It gets no code
Q.19 Which step is repeated in Huffman coding construction?
Merge two highest frequencies
Merge two lowest frequencies
Split the tree
Randomly combine nodes
Explanation - At each step, two least frequent nodes are merged into a new node.
Correct answer is: Merge two lowest frequencies
Q.20 Huffman coding works best when:
Frequencies are uniform
Frequencies vary a lot
Data is random
Data is encrypted
Explanation - Compression is more effective when some symbols are much more frequent than others.
Correct answer is: Frequencies vary a lot
Q.21 The Huffman algorithm was invented by:
Alan Turing
David Huffman
Claude Shannon
Donald Knuth
Explanation - David A. Huffman invented Huffman coding in 1952 as part of his PhD research.
Correct answer is: David Huffman
Q.22 What kind of codes are Huffman codes?
Prefix codes
Postfix codes
Fixed codes
Suffix codes
Explanation - Huffman coding generates prefix codes, ensuring no ambiguity in decoding.
Correct answer is: Prefix codes
Q.23 Huffman coding belongs to which category of compression?
Lossy compression
Lossless compression
Hybrid compression
No compression
Explanation - It preserves all original information without loss.
Correct answer is: Lossless compression
Q.24 Which of the following is true about Huffman tree?
It is balanced always
It is full binary tree
It is AVL tree
It is multi-way tree
Explanation - Every internal node in Huffman tree has exactly two children, making it a full binary tree.
Correct answer is: It is full binary tree
Q.25 Which of the following compression formats uses Huffman coding internally?
JPEG
GIF
PNG
TIFF
Explanation - PNG image format uses a combination of LZ77 and Huffman coding for compression.
Correct answer is: PNG