АСП1/К2 2019

Задаци

1. задатак

Поставка

Нека је скоро комплетно или комплетно бинарно стабло представљено секвенцијалном меморијском репрезентацијом (низом). На основу прослеђеног низа у коме су смештене целобројне вредности које представљају информациони садржај чворова, формирати еквивалентно бинарно стабло уланчане репрезентације.

Решење

FORM TREE(arr, n)
ALLOCATE(nodes[n])
if n = 0 then
    return nil
end_if
j = 1
nodes[1] = GETNODE(arr[1])
for i = 1 to n do
    if j < n then
        j = j + 1
        nodes[j] = GETNODE(arr[j])
        left(nodes[i]) = nodes[j]
    end_if
    if j < n then
        j = j + 1
        nodes[j] = GETNODE(arr[j])
        right(nodes[i]) = nodes[j]
    end_if
end_for
return nodes[1]

GETNODE(value)
ALLOCATE(node)
left(node) = nil
right(node) = nil
value(node) = value
return node

2. задатак

Поставка

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

Решење

Кодовано: 014234

Симбол	Кôд
К	0
У	1
Р	2
I	3
КУ	4
УК	5
КУР	6
РИ	7
ИК	8

3. задатак

Поставка

За неко бинарно стабло преордер обилазак даје поредак ХБИКЦФДАЕЈГ, а инордер обилазак ХБИАДЈЕГФЦК. Одредити поредак који се добија левел-ордер обиласком и објаснити поступак.

Решење

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

Левел-ордер обилазак: ХБИКЦФДАЕЈГ. Поступак се своди на то да идемо по сваком нивоу бинарног стабла и читамо садржај тог нивоа слева на десно.

4. питање

Поставка

Дато је стабло формирано применом статичког Хуффман-овог алгоритма. Имплементирати функцију ФИНД_ЦОДЕС која за такво стабло на чији корен показује показивач роот враћа симболе чији су кодови дужине тачно к.

Решење

FIND CODES(root, k)
if (root = nil) or (k ≤ 0) then
    return nil
end_if
symbols = nil
node = nil
depth = 0
symb_node = nil
p = symbols
QUEUE_INIT(Q1)
QUEUE_INIT(Q2)
QUEUE_INSERT(Q1, root)
QUEUE_INSERT(Q2, 0)
while not QUEUE_EMPTY(Q1) do
    node = QUEUE_DELETE(Q1)
    depth = QUEUE_DELETE(Q2)
    if depth = k then
        if symbol(node) ≠ nil then
            symb_node = GETNODE
            value(symb_node) = symbol(node)
            if symbols = nil then
                symbols = p = symb_node
            else
                next(p) = symb_node
                p = next(p)
            end_if
        end_if
    else
        if left(node) ≠ nil then
            QUEUE_INSERT(Q1, left(node))
            QUEUE_INSERT(Q2, depth + 1)
        end_if
        if right(node) ≠ nil then
            QUEUE_INSERT(Q1, right(node))
            QUEUE_INSERT(Q2, depth + 1)
        end_if
    end_if
end_while
return symbols

5. задатак

Поставка

Применом алгоритма динамички Хуффман кодирати поруку АБРАКАДАБРА, уколико су почетни фиксни кодови за слова А, Б, Р, К, D редом 000, 001, 010, 011 и 100. Процес кодирања приказати по корацима.

Решење

• Крајње трансмитовано: А 0Б 00Р 0 100К 0 1100Д 0 110 110 0
• Крајње кодирано: 000 0001 00010 0 100011 0 1100100 0 110 110 0
• Крајње стабло:

   11
  /  \
 A     6
 5   /   \
    2     4
   / \   / \
  1   K R   B
 / \  1 2   2
NYT D
 0  1

6. задатак

Поставка

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

Решење

Може се модификовати тако што чувамо показивач на претходно обрађени чвор (prev) и пре обрађивања тренутног чвора (P(next), где је next тренутно обрађивани чвор) радимо следеће:

if prev ≠ nil then
    if left(next) = nil then
        left(next) = prev
        lf(next) = 0
    end_if
    if right(prev) = nil then
        right(prev) = next
        rf(prev) = 0
    end_if
end_if
prev = next

7. задатак

Поставка

У каквом бинарном стаблу интерна дужина пута постиже максимум за дати број чворова? Извести и објаснити израз за израчунавање максималне интерне дужине пута у бинарном стаблу са н чворова. Нацртати пример таквог стабла са 4 чвора и израчунати интерну дужину пута.

Решење

Интерна дужина пута постиже максимум у дегенерисаном бинарном стаблу у којем има један чвор по нивоу, на пример (за n = 4):

      A
     /
    B
   /
  C
 /
D

Интерна дужина пута је збир дужина путева од корена стабла до сваког интерног чвора, што је у овом случају $PI = 1 + 2 + 3 = 6$. Можемо приметити да је до сваког интерног чвора путања за један краћа од нивоа на којем се налази и да има за један мање путева од броја чворова из чега добијамо да је интерна дужина пута за бинарно стабло са $n$ чворова једнака $PI_n = 1 + 2 + 3 + ... + (n - 1) = \frac{(n-1) n}{2}$.

8. задатак

Поставка

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

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

Решење

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

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

FOLLOWERS(G, i)
followers = 0
p = IAL[i]
while' p ≠ nil do
    followers = followers + 1
    p = next(p)
end_while
return followers