АСП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. Колика је минимална, а колика максимална дубина стека коришћеног у итеративној реализацији преордер обиласка бинарног стабла са н чворова. Нацртати таква стабла.

8. задатак

Поставка

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

Решење

INVERSE INORDER T(root)