Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 48

Символы от a до h имеют набор частот на основе первых 8 чисел Фибоначчи следующим образом

a: 1, b: 1, c: 2, d: 3, e: 5, f: 8, g: 13, h: 21 /
Код Хаффмана используется для представления символов. Какая последовательность символов соответствует следующему коду?
110111100111010
(A) FDHEG
(B) ecgdf
(С) dchfg
(D) Fehdg

Ответ: (А)
Объяснение:

Необходимый фон — Генерация кодов префиксов с использованием кодирования Хаффмана.

Сначала мы применяем жадный алгоритм на частотах символов для генерации двоичного дерева, как показано на рисунке ниже. Присваивая 0 левому краю и 1 правому краю, префиксные коды для символов:
ниже.

а — 1111110
б — 1111111
с — 111110
д — 11110
е — 1110
f — 110
г — 10
ч — 0

Данная строка может быть разложена как

110 11110 0 1110 10

ф д э г

Это решение предоставлено Пранджул Ахаджа .
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE IT 2006 | Вопрос 48

0.00 (0%) 0 votes