АСП1/К2 2019
1. задатак
Поставка
Нека је скоро комплетно или комплетно бинарно стабло представљено секвенцијалном меморијском репрезентацијом (низом). На основу прослеђеног низа у коме су смештене целобројне вредности које представљају информациони садржај чворова, формирати еквивалентно бинарно стабло уланчане репрезентације.
Решење
FORM TREE(arr, n)
ALLOCATE(nodes[n])
j = 1
nodes[1] = GETNODE(arr[1])
for i = 1 to n do
nodes[i] = GETNODE(arr[i])
if j < n then
j = j + 1
left(nodes[i]) = GETNODE(arr[j])
end_if
if j < n then
j = j + 1
right(nodes[i]) = GETNODE(arr[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 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 10 110 0
- Крајње кодирано: 000 0001 00010 0 100011 0 1100100 0 10 110 0
- Крајње стабло:
11
/ \
A 6
5 / \
B 4
2 / \
R 2
2 / \
1 K
/ \ 1
NYT D
0 1
6. задатак
Поставка
Прецизно објаснити како се итеративни алгоритам за обилазак по инордер-у може модификовати тако да се задато стабло трансформише у повезано (тхреадед) стабло по истом обиласку.
Решење
7. задатак
Поставка
У каквом бинарном стаблу интерна дужина пута постиже максимум за дати број чворова? Извести и објаснити израз за израчунавање максималне интерне дужине пута у бинарном стаблу са н чворова. Нацртати пример таквог стабла са 4 чвора и израчунати интерну дужину пута.
Решење
8. задатак
Поставка
На једној друштвеној мрежи постоји симетрична релација пријатељства између корисника и асиметрична релација праћења код које један корисник прати активности другог. Потребно је посматрану друштвену мрежу моделирати графом.
- Предложити одговарајући тип графа и детаљно описати његове особине.
- Предложити и образложити одговарајаћу меморијску репрезентацију графа, тако да се оптимизује одређивање укупног броја пратилаца неког корисника. Корисникове активности могу да прате и пријатељи и пратиоци.
- Написати псеудкод функције која за задатог корисника враћа укупан број пратилаца.