548
Graphs and Trees
exerciSeS 6.4
1. Is the following code a prefix code? Why or why not?
Character
m
b
d
w
Encoding scheme 01 100 011 101
2. Using the code of Exercise 1, decode the string 01101.
3. Given the codes
Character
a
e
i
o
u
Encoding scheme 00
01
10
110 111
decode the sequences
a. 11011011101
b. 1000110111
c. 010101
4. Given the codes
Character
b
h
q
w
%
Encoding scheme 1000
1001 0
11 101
decode the sequences
a. 10001001101101
b. 11110
c. 01001111000
5. Given the codes
Character
a
p
w
(
)
Encoding scheme
001
1010 110 1111 1110
decode the sequences
a. 111110101101110001
b. 1010001110
c. 1111111100111101110
6. Given the nonprefix codes
Character
1
3
5
7
9
Encoding scheme
1
111
101 10
10101
give all possible decodings of the sequence 111110101.
7. Write the Huffman codes for a, b, c, and d in the binary tree shown.
d
c
b
a