АСП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
FORM TREE(arr, n)
if n = 0 then
return nil
end_if
for i = 1 to floor(n/2) do
node = GETNODE
info(node) = arr[i]
if i = 1 then
root = node
left(node) = GETNODE
info(left(node)) = arr[2 * i]
if 2 * i + 1 <= n then
right(node) = GETNODE
info(right(node)) = arr[2 * i + 1]
return rootGETNODE()
ALLOCATE(node)
info(node) = nil
left(node) = nil
right(node) = nil
return node2. задатак
Поставка
Применом ЛЗ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 symbols5. задатак
Поставка
Применом алгоритма динамички Хуффман кодирати поруку АБРАКАДАБРА, уколико су почетни фиксни кодови за слова А, Б, Р, К, 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. задатак
Поставка
Прецизно објаснити како се итеративни алгоритам за обилазак по инордер-у може модификовати тако да се задато стабло трансформише у повезано (тхреадед) стабло по истом обиласку.
Решење
Може се модификовати тако што чувамо показивач на претходно обрађени чвор и пре процесирања тренутног чвора (P(node)) радимо следеће:
if left(next) = nil then
left(next) = prev
lf(next) = 0
end_if
if prev ≠ nil and right(prev) = nil then
right(prev) = next
rf(prev) = 0
end_if
prev = next7. задатак
Поставка
У каквом бинарном стаблу интерна дужина пута постиже максимум за дати број чворова? Извести и објаснити израз за израчунавање максималне интерне дужине пута у бинарном стаблу са н чворова. Нацртати пример таквог стабла са 4 чвора и израчунати интерну дужину пута.
Решење
Интерна дужина пута постиже максимум у дегенерисаном бинарном стаблу у којем има један чвор по нивоу, на пример (за n = 4):
A
/
B
/
C
/
D
Интерна дужина пута је збир дужина путева од корена стабла до сваког интерног чвора, што је у овом случају . Можемо приметити да је до сваког интерног чвора путања за један краћа од нивоа на којем се налази и да има за један мање путева од броја чворова из чега добијамо да је интерна дужина пута за бинарно стабло са чворова једнака .
8. задатак
Поставка
На једној друштвеној мрежи постоји симетрична релација пријатељства између корисника и асиметрична релација праћења код које један корисник прати активности другог. Потребно је посматрану друштвену мрежу моделирати графом.
- Предложити одговарајући тип графа и детаљно описати његове особине.
- Предложити и образложити одговарајаћу меморијску репрезентацију графа, тако да се оптимизује одређивање укупног броја пратилаца неког корисника. Корисникове активности могу да прате и пријатељи и пратиоци.
- Написати псеудкод функције која за задатог корисника враћа укупан број пратилаца.
Решење
- У решењу се претпоставља да се у поставци задатка имплицира да су пријатељи уједно и пратиоци.
Ову мрежу је могуће моделирати усмереним нетежинским графом где чворови означавају кориснике а гране означавају релације праћења, где грана од чвора А до чвора Б означава да корисник А прати корисника Б. Оптимална репрезентација графа у овом случају јесте преко инверзне листе суседности, јер на тај начин мора проћи кроз тачно онолико пратилаца колики ће број бити враћен на крају, а ако се чува дужина инверзне листе суседности у заглављу онда је сложеност алгоритма константна.
FOLLOWERS(G, i)
followers = 0
p = IAL[i]
while' p ≠ nil do
followers = followers + 1
p = next(p)
end_while
return followers