АСП1/К2 2016
1. задатак
Поставка
На слици је дато једно некомплетно приказано бинарно стабло (десно. Уколико преордер обилазак таквог стабла даје поредак чворова АЦБДФЕ, нацртати све могуће изгледе овог стабла.
A / \ C ... \ B
Решење
Погледајмо најпре обилазак А ЦБ ДФЕ
Леви део је комплетан и D мора бити корен десног подстабла. Одатле долазе комбинације:
A A A A A
/ \ / \ / \ / \ / \
C D C D C D C D C D
\ / \ \ / \ / \ \ \ \
B F E B F B F B F B F
/ \ \ /
E E E E
2. задатак
Поставка
Написати у псеудокоду функцију која у бинарном стаблу на чији корен показује показивач роот утврђује да ли постоји чвор чија позиција у стаблу (у односу на корен) је симетрична у односу на позицију чвора на који показује показивач ноде. Сматрати да сваки чвор бинарног стабла поред информационог садржаја садржи показиваче на лево и десно подстабло и показивач на родитељски чвор.
Решење
Решење се састоји од тога да се вратимо уназад, памтећи пут, и онда силазимо опет али обрнутим путем. Уколико се испразни уланчана листа (која глуми стек), то значи да постоји симетрични члан.
CHECK_SYMMETRIC(root, node)
path = nil
step = nil
parent = nil
p = node
while p ≠ root do
step = GETNODE
parent = parent(p)
if left(parent) = p then
info(step) = 0
else
info(step) = 1
end_if
p = parent
next(step) = path
path = step
end_while
while p ≠ nil do
if path = nil then
return true
end_if
if info(path) = 0 then
p = right(p)
else
p = left(p)
end_if
step = path
path = next(path)
FREENODE(step)
end_while
return false
3. задатак
Поставка
Декодовати поруку 0 1 3 3 4 5 4 9 применом ЛЗW алгоритма, за дати почетни садржај табеле симбола.
Решење
- Декодована порука: АБАБАББААБАБАБАБ
- Таблица кодова:
| Симбол | Кôд |
|---|---|
| А | 0 |
| Б | 1 |
| C | 2 |
| АБ | 3 |
| БА | 4 |
| АБА | 5 |
| АББ | 6 |
| БАА | 7 |
| АБАБ | 8 |
| БАБ | 9 |
4. задатак
Поставка
Уколико је усмерени граф са н чворова представљен листом суседности, написати у псеудокоду функције за израчунавање улазног и излазног степена задатог чвора и.
Решење
Решење задатка је теоријски описано на 159. страни књиге. Полази се од претпоставке да Г представља низ уланчаних листа, па се са Г[и] узима листа суседности чвора и.
VERTEX IN DEG(G, n, i)
in_deg = 0
for k = 1 to n do
curr = next(G[k])
while (curr ≠ nil) do
if (info(curr) = i) then in_deg = in_deg + 1
end_if
curr = next(curr)
end_while
end_for
return in_deg
VERTEX OUT DEG(G, n, i) out_deg = 0 curr = next(G[i]) while (curr ≠ nil) do out_deg = out_deg + 1 curr = next(curr) end_while return out_deg
5. задатак
Поставка
Коришћењем динамичких Хуффман-ових кодова, кодирати секвенцу симбола ЦБЦБДАААБАБА, ако се симболи А, Б, C и D кодовима фиксне дужине кодирају са по два бита 00, 01, 10, 11, респективно
Решење
Кодирана порука гласи: 10 001 1 01 0011 10000 1001 01 01 11 10 0.
6. задатак
Поставка
Дато је бинарно стабло Б, на чији корен показује показивач роот. Стабло Б добијено је конверзијом м-арног стабла Т у одговарајуће бинарно. Написати у псеудокоду итеративну функцију која одређује ред стабла Т.
Решење
TREE ORDER BIN(root)
7. задатак
Поставка
Питања:
- Коментарисати стратегију обраде истих приоритета у приоритетном реду примењеном у статичком Хуффман-овом алгоритму.
- Колика је минимална, а колика максимална дубина стека коришћеног у итеративној реализацији преордер обиласка бинарног стабла са н чворова. Нацртати таква стабла.
Решење
- Боље резултате ћемо добити ако дајемо већи приоритет "старијим" члановима реда, тј стаблима мање висине. Бирањем нижих стабала добијамо краће кодове те је алгоритам ефикаснији.
8. задатак
Поставка
Дато је бинарно стабло повезано по инордер-у. Написати и објаснити псеудокод алгоритма обиласка по инверзном инордер поретку.
Решење
INVERSE INORDER T(root)