АСП1/К2 2018

Задаци

1. задатак

Поставка

Написати у псеудокоду итеративну функцију која врши генерализовани преордер обилазак м-арног стабла на које показује показивач роот. Сваки чвор стабла садржи ознаку чвора и м показивача на потомке. Функција треба да врати низ који за сваки чвор стабла садржи његову ознаку и ниво у стаблу на коме се чвор налази. Коментарисати решење. Дозвољено је користити готове линеарне структуре података.

Решење

PREORDER M I(root, m)
if root = nil then
    return nil
end_if
INIT_STACK(S1)
INIT_STACK(S2)
STACK_PUSH(S1, root)
STACK_PUSH(S2, 1)
node = nil
depth = 0
list = nil
p = nil
while not STACK_EMPTY(S1) do
    node = STACK_POP(S1)
    depth = STACK_POP(S2)
    if list = nil then
        list = p = GETNODE
    else
        next(p) = GETNODE
        p = next(p)
    end_if
    symbol(p) = symbol(node)
    depth(p) = depth
    for i = m to 1 do
        if children(node)[i] ≠ nil then
            STACK_PUSH(S1, children(node)[i])
            STACK_PUSH(S2, depth + 1)
        end_if
    end_for
end_while
return list

Ово решење се заснива на чувању чвора и нивоа чвора у два одвојена стека и коришћењу повезане листе (пошто не знамо унапред количину чворова у стаблу како бисмо алоцирали низ). За сваки чвор у стеку додајемо његову децу на један стек, с тим што их додајемо с десна на лево како би први посећени чвор био најлевље (односно прво) дете чвора (као што је то и случај код преордер обиласка), а његов ниво увећан за један на други стек.

2. задатак

Поставка

Извести и објаснити израз за одређивање минималне висине х_мин за бинарно стабло са н чворова. Какве особине има бинарно стабло са минималном висином?

Решење

Бинарно стабло са минималном висином тежи да има сваки ниво попуњен, тј. тежи да буде комплетно стабло. Пошто знамо да комплетно стабло на нивоу $i$ има $2^i$ чворова (сваки чвор осим листова има максимални излазни степен, што је 2), и да је стога укупан број чворова у стаблу једнак $n = 2^0 + 2^1 + ... + 2^h = 2^{h + 1} - 1$. То значи да је $\log_2(n + 1)$ једнако $h + 1$ и тиме добијамо да је $h_{min} = \left\lceil{\log_2(n + 1)}\right\rceil - 1$.

3. задатак

Поставка

За неко бинарно стабло преордер обилазак даје поредак АБДЦЕФГХИ, а постордер обилазак ДБФИХГЕЦА.

1. Навести све чворове који представљају листове овог стабла.
2. Одредити све претке чвора Е.
3. Навести све чворове који се налазе у подстаблу чији је корен чвор Е.

Решење

    A
   / \
  B   C
 /   /
D   E
   / \
  F   G
     /
    H
   /
  I

1. D, Ф, I
2. C, А
3. Ф, Г, Х, I

4. задатак

Поставка

Применом ЛЗW алгоритма приказати поступак кодирања знаковног низа ЛЕСQУЕЛЛЕС, ако је дата почетна табела са кодовима симбола. Написати кодирану поруку и изглед табеле симбола након поступка кодирања.

Решење

Кодирана порука: 012341052

Симбол	Кôд
L	0
Е	1
С	2
Q	3
У	4
ЛЕ	5
ЕС	6
СQ	7
QУ	8
УЕ	9
ЕЛ	10
ЛЛ	11
ЛЕС	12

5. задатак

Поставка

Дато је стабло формирано применом алгоритма статички Хуффман. Имплементирати функцију ФИНД_ЛОНГЕСТ_ЦОДЕС која враћа број симбола који се кодирају највећим бројем бита према формираном стаблу. Функцији је прослеђен показивач на корен стабла роот. Написати у псеудокоду и методу ИС ЕXТЕРНАЛ НОДЕ која проверава да ли је чвор на који показује прослеђени показивач екстерни.

Решење

FIND LONGEST CODES(root)
tail = head = GETNODE(root)
next(head) = GETNODE(nil)
head = next(head)
num_max = 0
t = nil
while tail ≠ nil do
    if value(tail) = nil then
        if tail ≠ head then
            next(head) = GETNODE(nil)
            head = next(head)
            num_max = 0
        end_if
    else
        if IS_EXTERNAL_NODE(value(tail)) then
            num_max = num_max + 1
        else
            if left(value(tail)) ≠ nil then
                next(head) = GETNODE(left(value(tail)))
                head = next(head)
            end_if
            if right(value(tail)) ≠ nil then
                next(head) = GETNODE(right(value(tail)))
                head = next(head)
            end_if
        end_if
    end_if
    t = next(tail)
    FREENODE(tail)
    tail = t
end_while
return num_max

IS EXTERNAL NODE(node)
if left(node) = nil and right(node) = nil then
    return true
else
    return false
end_if

GETNODE(value)
ALLOCATE(node)
next(node) = nil
value(node) = value
return node

FREENODE(node)
DEALLOCATE(node)

6. задатак

Поставка

Посматра се стабло са слике. Повезати га по инордер-у и илустровати сликом на којој су обележене све потребне додатне информације. Прецизно објаснити на који начин се може извршити исписивање стабла по инверзном инордер поретку.

    A
   / \
  B   C
 / \   \
F   G   Y
   /   /
  E   M
   \
    X

Решење

Решење првог дела задатка.

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

REVERSE INORDER T(root)
node = root
while right(node) ≠ nil do
    node = right(node)
end_while
while node ≠ nil do
    P(node)
    if lf(node) = 0 then
        node = left(node)
    else
        node = left(node)
        while node ≠ nil and rf(node) = 1 do
            node = right(node)
        end_while
    end_if
end_while

7. задатак

Поставка

Применог алгоритма динамички Хуффман декодовати поруку 0000100101011011111101101101 уколико се састоји од карактера А, Б и C који имају почетне фиксне кодове 00, 01 и 10. Процес декодовања приказати по корацима.

Решење

• Декодована порука: АБЦЦААЦБББ
• Крајње Хуффман-ово стабло:

  10
 /  \
B    6
4   / \
   3   C
  / \  3
NYT  A
 0   3

8. задатак

Поставка

У једном програму треба моделирати односе дуговања и потраживања између н фирми.

1. Предложити одговарајућу логичку структуру и детаљно описати њене особине.
2. Предложити и образложити одговарајаћу меморијску репрезентацију ове структуре ако је потребно оптимизовати операцију израчунавања укупног износа дуговања према некој фирми, као и одређивање њеног највећег дужника.
3. Написати псеудокод функције која за задату фирму враћа укупна износ дуговања која она потражује.

Решење

1. Граф који нам је у овом случају потребан јесте тежински усмерен граф у ком чворови представљају фирме а гране представљају дуговања, где грана тежине w од чвора А до чвора Б означава да фирма А дугује фирми Б износ од w јединица валуте. Операције које над њим морају бити реализоване јесу додавање новог чвора и повезивање два чвора.
2. Оптимална меморијска репрезентација јесте преко инверзне листе суседности, тј. низа дужине н који садржи показиваче ка уланчаним листама у којима се налазе сви чворови који су повезани са тренутним чвором. Тежине грана се могу чувати или у самим чворовима уланчане листе или у одвојеној матрици w где w[и, ј] означава тежину гране од и ка ј и може бити постављена на ∞ уколико та грана не постоји.

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

   Операција одређивања највећег дужника може се исто реализовати линеарним проласком кроз листу који чува највећег дужника и највећи дуг. Додатна оптимизација може се постићи тиме што се повезане листе претворе у приоритетне редове што операцији повезивања два чвора повећава сложеност са константне на логаритамску али операцији проналажења највећег дужника смањује сложеност са линеарне на константну, за шта смо и оптимизовали.

3. У имплементацији испод сматра се да оптимизације поменуте изнад нису примењене (јер би то мало обесмислило алгоритам). Такође се сматра да су тежине грана чуване у матрици тежина w.

DEBT(G, i)
total_debt = 0
p = first(e[i])
while p ≠ nil do
    total_debt = total_debt + w[i, value(p)]
    p = next(p)
end_while
return total_debt