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

Решење

1. Боље резултате ћемо добити ако дајемо већи приоритет "старијим" члановима реда, тј. стаблима мање висине. Бирањем нижих стабала добијамо краће кодове те је алгоритам ефикаснији.
2. Дубина стека директно зависи од броја десних подстабала у стаблу. У првом случају разматрамо стабло највеће дубине - дегенерисано стабло. Када су сви чворови редом са леве стране у оваквом стаблу, на стек се ставља само корен и ништа друго, те је за овакво стабло довољан стек величине 1, независно од броја чворова у стаблу. Насупрот томе, ако у стабло дегенерисано на лево додамо десне чворове на сваки чвор, на стек ће при сваком посећивању левог детета бити додато десно дете па ће на крају посећивања све леве деце на стеку бити сва десна деца, што је укупно $\left\lfloor\frac{n}{2}\right\rfloor$ чворова.

8. задатак

Поставка

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

Решење

Видети решење шестог задатка са другог колоквијума 2018. године.