АСП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. задатак
Поставка
Дато је бинарно стабло Б, на чији корен показује показивач роот. Стабло Б добијено је конверзијом м-арног стабла Т у одговарајуће бинарно. Написати у псеудокоду итеративну функцију која одређује ред стабла Т.
Решење
Функција користи ред за чекање као додатну структуру при имплементацији. У ред се ређају најлевљи синови, а неxт иде десно, по браћи, и броји колико се чворова налази повезано десно за дати чвор (то су му управо његова браћа). Излаз функције биће максимални број браће при неком од пролазака, што и јесте ред стабла.
TREE ORDER BIN(root)
INIT_QUEUE(Q)
m = 0
next = root
INSERT(Q, next)
while (not QUEUE_EMPTY(Q)) do
m_curr = 0
next = DELETE(Q)
while (next ≠ nil) do
m_curr = m_curr + 1
if (left(next) ≠ nil) then
INSERT(Q, left(next))
end_if
next = right(next)
end_while
if (m_curr > m) then
m = m_curr
end_if
end_while
return m
7. задатак
Поставка
Питања:
- Коментарисати стратегију обраде истих приоритета у приоритетном реду примењеном у статичком Хуффман-овом алгоритму.
- Колика је минимална, а колика максимална дубина стека коришћеног у итеративној реализацији преордер обиласка бинарног стабла са н чворова. Нацртати таква стабла.
Решење
- Боље резултате ћемо добити ако дајемо већи приоритет "старијим" члановима реда, тј стаблима мање висине. Бирањем нижих стабала добијамо краће кодове те је алгоритам ефикаснији.
- Дубина стека директно зависи од броја десних подстабала у стаблу. У оба случаја разматрамо стабло највеће дубине - дегенерисано стабло. У случају да су сви чворови редом са леве стране у оваквом стаблу, на стек се ставља само корен и ништа друго, те је за овакво стабло довољан стек величине 1, независно од броја чворова у стаблу. Насупрот томе, ако су сви чворови редом са десне стране у оваквом стаблу, сваки чвор би се по једном морао ставити на стек па скинути са њега, те је потребан стек оне величине колико има и чворова - н.
8. задатак
Поставка
Дато је бинарно стабло повезано по инордер-у. Написати и објаснити псеудокод алгоритма обиласка по инверзном инордер поретку.
Решење
INVERSE INORDER T(root)