АСП1/К2 2017
1. задатак
Поставка
Написати у псеудокоду итеративну функцију која одређује ширину бинарног стабла на чији корен показује показивач роот. Ширина стабла се дефинише као највећа ширина свих његових нивоа. Функција треба да испише све чворове на нивоу највеће ширине и врати одређену ширину. Дозвољена је употреба готових линеарних структура података
Решење
BIN TREE WIDTH(root)
curr_width = max_width = 0
tail = head = GETNODE(root)
next(head) = GETNODE(nil)
head = next(head)
max_level = curr_level = tail
t = nil
while tail ≠ nil do
if value(tail) = nil then
if curr_width > max_width then
while max_level ≠ curr_level do
t = max_level
max_level = next(max_level)
FREENODE(t)
end_while
max_width = curr_width
end_if
curr_width = 0
if tail ≠ head then
curr_level = next(tail)
next(head) = GETNODE(nil)
head = next(head)
end_if
else
curr_width = curr_width + 1
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_while
while value(max_level) ≠ nil do
OUTPUT(symbol(value(max_level)))
t = max_level
max_level = next(max_level)
FREENODE(t)
end_while
while max_level ≠ nil do
t = max_level
max_level = next(max_level)
FREENODE(t)
end_while
return max_width
GETNODE(value) ALLOCATE(node) next(node) = nil value(node) = value return node
FREENODE(node) DEALLOCATE(node)
2. задатак
Поставка
Посматра се једно бинарно стабло.
- Објаснити шта су екстерни чворови стабла и за задато бинарно стабло одредити број екстерних чворова. Екстерне чворове доцртати на задатом стаблу.
- Извести и објаснити везу између броја екстерних чворова бинарног стабла и чворова стабла .
Решење
A
/ \
C D
/ \ / \
B ☐ E ☐
/ \ / \
☐ ☐ ☐ F
/ \
☐ ☐
- Екстерни чворови су имагинарни чворови на које показују незаузети показивачи интерних чворова стабла. У овом стаблу где је има их 7.
- По горњој дефиницији, број екстерних чворова једнак је броју незаузетих показивача интерних чворова. Број свих показивача је дупло већи од броја чворова, јер сваки чвор има два показивача у бинарном стаблу (). Број заузетих показивача једнак је броју грана јер једна грана заузима један показивач, а за број грана знамо да је за један мањи од броја чворова. Одатле добијамо:
3. задатак
Поставка
Применом ЛЗW алгоритма, приказати поступак кодирања поруке АНТАНАНАРИВЕ, за дати почетни садржај табеле симбола. Написати кодирану поруку и изглед табеле симбола након поступка кодирања
Решење
- Кодирана секвенца: 0 1 2 7 10 3 4 5 6
- Табела кодова:
| Симбол | Кôд |
|---|---|
| А | 0 |
| Н | 1 |
| Т | 2 |
| Р | 3 |
| I | 4 |
| V | 5 |
| Е | 6 |
| АН | 7 |
| НТ | 8 |
| ТА | 9 |
| АНА | 10 |
| АНАР | 11 |
| РИ | 12 |
| IV | 13 |
| ВЕ | 14 |
4. задатак
Поставка
Коришћењем динамичког Хуффман алгоритма декодирати следећу поруку 00001010010001101101 ако је познато да су симболима А, Б и C додељени кодови фиксне дужине 00, 01 и 10 респективно. За добијену секвенцу карактера предложити њихов другачији распоред такав да се при кодирању измењене секвенце добије што већа уштеда у меморији (краћи код). Избор образложити.
Решење
- Декодована порука: АББЦЦАА
- Динамичко Хуффман стабло:
7 / \ A 4 3 / \ 2 C / \ 2 NYT B 0 2
- Предложена секвенца: АААББЦЦ (кодирано са 00 1 1 001 01 0010 001, односно четири кода мање)
- Образложење: Очигледно је да слова А има највише у секвенци и да се оно треба кодирати са најмање битова. Уместо да редом убацујемо кодове и очекујемо да се "боре" за заузимање места које се кодира са најмање битова најлогичније је да их поставимо у позицију у којој ће бити кодирани са најлогичнијим бројем битова. У овом случају то је 1 бит за А, 2 бита за Б и 3 бита за C.
5. задатак
Поставка
Ако за неко бинарно стабло преордер обилазак даје поредак НМЦОЛАГФБДПРСХQ, а инордер обилазак ЦОАЛГМБФНПХСРQД, реконструисати задатог стабла.
Решење
N
/ \
M D
/ \ /
C F P
\ / \
O B R
\ / \
L S Q
/ \ /
A G H
6. задатак
Поставка
Дато је бинарно стабло на чији корен показује показивач роот. Треба пронаћи чвор који је к-ти по преордер поретку, али тако да се заправо обиђе што мање чворова.
- Дозвољено је увођење једног додатног поља у чвор стабла, поред постојећих поља лефт и ригхт, ради што ефикаснијег итеративног алгоритма. Укратко објаснити сврху тог поља и алгоритам за налажење к-тог чвора.
- Написати у псеудокоду функцију која враћа показивач на к-ти чвор по преордер поретку на што је могуће ефикаснији начин.
Решење
Уводимо поље којем нам говори колико се у левом подстаблу тог чвора налази чворова. На тај начин можемо да, кад дођемо до неког чвора, одлучимо да ли даље идемо у његово лево или десно подстабло у зависности од тога да ли је број чворова у левом подстаблу већи или мањи од тренутног броја тражених чворова. На почетку процесирања сваког чвора смањујемо тренутно тражени број чворова и враћамо тренутни чвор уколико је једнак 1.
PREORDER K NODE(root, k)
next = root
n = k
loop
n = n - 1
if n = 0 then
return next
end_if
if n ≤ left_size(next) then
next = left(next)
else
next = right(next)
n = n - left_size(next)
end_if
end_loop
7. задатак
Поставка
Дато је одговарајуће бинарно стабло добијено конверзијом стабла вишег реда:
- Предложити како у стабло уградити информацију која омогућава кретање уз стабло од листова ка корену.
- На основу горњег предлога написати функцију која за чвор са задатом адресом адр враћа његов ниво у стаблу.
Решење
Можемо да, налик повезаним стаблима, уведемо рф бит који ће бити постављен на 1 уколико десни показивач показује на брата тренутног чвора или постављен на 0 уколико показује на првог брата свог родитеља, и затим све неискоришћене десне показиваче (осим корена) повежемо на прву браћу својих родитеља. На тај начин сви чворови једног нивоа имаће приступ свим чворовима наредног нивоа.
NODE LEVEL(adr)
level = 1
next = adr
while right(next) ≠ nil do
if rf(next) = 0 then
level = level + 1
end_if
next = right(next)
end_while
return level
8. задатак
Поставка
На крају сваке књиге постоји листа референци на друге књиге.
- Предложити меморијску представу графа који представља референцирање књига тако да је олакшано налажење броја референци на неку књигу.
- На основу горњег предлога написати функцију која за задату књигу налази број референци на њу.
Решење
Граф који нам је потребан је нетежински усмерен граф у којем чворови представљају књиге а гране референце на књиге, где грана од А ка Б означава да књига А садржи референцу на књигу Б. Оптимална меморијска представа би била преко инверзне листе суседности, где је додатна оптимизација чување дужине те листе у њеном заглављу. Псеудокод испод не рачуна ту оптимизацију:
REF COUNT(k)
ref_number = 0
p = IAL[k]
while p ≠ nil do
ref_number = ref_number + 1
p = next(p)
end_while
return ref_number