АСП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$ чворова, и да је стога укупан број чворова у стаблу једнак $n = 2^0 + 2^1 + ... + 2^h = 2^{h + 1} - 1$. То значи да је $log_2(n + 1)$ једнако $h + 1$ и тиме добијамо да је $h_{min} = log_2(n + 1) - 1$.

3. задатак

Поставка

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

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

Решење

      A
     /
    B
   / \
  D   C
     /
    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)
list = root
p = list
next(p) = GETNODE(nil)
p = next(p)
max_depth = 1
num_max = 0
t = nil
while list ≠ nil do
    if value(list) = nil then
        if list ≠ p then
            next(p) = GETNODE(nil)
            p = next(p)
            max_depth = max_depth + 1
            num_max = 0
        end_if
    else
        if IS_EXTERNAL_NODE(value(list)) then
            num_max = num_max + 1
        else
            if left(value(list)) ≠ nil then
                next(p) = GETNODE(left(value(list)))
                p = next(p)
            end_if
            if right(value(list)) ≠ nil then
                next(p) = GETNODE(right(value(list)))
                p = next(p)
            end_if
        end_if
    end_if
    t = next(list)
    FREENODE(list)
    list = 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

Решење

Датотека:АСП1 К2 2018 6 задатак стабло.пнг

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

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

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  B
 0   3

8. задатак

Поставка

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

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