АСП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

4. задатак

Поставка

Уколико је усмерени граф са н чворова представљен листом суседности, написати у псеудокоду функције за израчунавање улазног и излазног степена задатог чвора и.

Решење

VERTEX IN DEG(G, n, i)

VERTEX OUT DEG(G, n, i)

5. задатак

Поставка

Коришћењем динамичких Хуффман-ових кодова, кодирати секвенцу симбола ЦБЦБДАААБАБА, ако се симболи А, Б, C и D кодовима фиксне дужине кодирају са по два бита 00, 01, 10, 11, респективно

6. задатак

Поставка

Дато је бинарно стабло Б, на чији корен показује показивач роот. Стабло Б добијено је конверзијом м-арног стабла Т у одговарајуће бинарно. Написати у псеудокоду итеративну функцију која одређује ред стабла Т.

Решење

TREE ORDER BIN(root)

7. задатак

Поставка

Питања:

1. Коментарисати стратегију обраде истих приоритета у приоритетном реду примењеном у статичком Хуффман-овом алгоритму.
2. Колика је минимална, а колика максимална дубина стека коришћеног у итеративној реализацији преордер обиласка бинарног стабла са н чворова. Нацртати таква стабла.

Решење

1. Боље резултате ћемо добити ако дајемо већи приоритет "старијим" члановима реда, тј стаблима мање висине. Бирањем нижих стабала добијамо краће кодове те је алгоритам ефикаснији.

8. задатак

Поставка

Дато је бинарно стабло повезано по инордер-у. Написати и објаснити псеудокод алгоритма обиласка по инверзном инордер поретку.

Решење

INVERSE INORDER T(root)