АСП1/Август 2021

Овај чланак је рекреација августовског рока који није објављен.

1. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

Дата је ретка матрица која је приказана на слици. (Дата је матрица нпр. 5*6 са 5 или 6 рандом ненултих елемената).

1. Нацртати изглед делова меморије у којима се чува ова ретка матрица, ако се примењује Цомпрессед Спарсе Роw начин чувања.
2. Написати функцију у псеудокоду која на основу сачуване Цомпрессед Спарсе Роw репрезентације матрице M и унетог броја и штампа све ненулте елементе и-те врсте.

2. задатак

Поставка

Наведите начине репрезентације графова и њихове предности и мане.

Решење

Потребно је само написати и прокоментарисати табелу 7.1 са стране 161 из уџбеника.

3. задатак

Поставка

Задато је бинарно стабло С и дате су адресе два чвора x и y. Написати функцију у псеудокоду која проналази најнижег заједничког претка задата два чвора.

Решење

LOWEST_COMMON_ANCESTOR(S, x, y)
return FIND(S,x,y)
FIND(S, x, y)
if S == null
   return null
end_if
if S == x || S == y
   return S
end_if
left = FIND(S.left,x,y)
right = FIND(S.right,x,y)
if left ≠ null && right ≠ null
   return S
else if left ≠ null
   return left
else if right ≠ null
   return right
else
   return null
end_if

4. задатак

Поставка

Потпуно формално извести међусобну зависност интерне и екстерне дужине пута у бинарном стаблу и кратко образложити.

Решење

$PE = PI + 2n$, где је $n$ број чворова у стаблу извођење индукцијом, као у књизи/на предавању.

5. задатак

Поставка

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

Решење

Решење је крајње тривијално и овде је наведено једно које је бодовано максималним бројем поена. За оба се може користити једноструко уланчана листа (јер није битан редослед којим ће се операције извршавати јер ће се свакако све извршити на свим сликама), а уланчане листе су погодно за лако додавање и брисање елемената.

PROCESS_IMAGES(images, operations)
S = head(images)
O = head(operations)
while s ≠ NIL do
    while o ≠ NIL do
        data(S) = (operation(O))(data(S))
    end_while
end_while

6. задатак

Поставка

Хуффман-ов алгоритам: Дат је текст са 6 слова дужине 21 слово. Одредити изглед стабла добијеног статичким Хуффман-ом за овај текст и упоредити просечан број битова за чување овог текста, као и једног слова у случају да се чува подразумевано и на основу овог Хуффман стабла. Фреквенцију слова закључити из текста.

Решење

Најобичнији статички Хуффман за задатим фреквенцијама.

7. задатак

Поставка

Дат је град који је моделован усмереним графом, тако што су чворови локације у граду (пекара, апотека, библиотека итд), а тежине грана између чворова време у минутима које је потребно да се пешке дође од изворишне до одредишне локације. Дете жели да стигне од школе (чвор X) до куће (чвор Y) најбрже могуће. Међутим, постоји опасан део града (чвор З), који није безбедан за децу и који она треба да избегавају. Написати функцију у псеудокоду која на основу задатог графа Г (није дата репрезентација, решење треба да буде концептуално), задатих локација куће и школе, Y и X, и опасног дела града З, проналази најкраће време које је детету потребно од школе до куће.

Решење

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

8. задатак

Поставка

Дат је граф на слици (има неких 7-8 чворова). За дати граф урадити тополошко сортирање и приказати граф добијен тако.

Решење

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

9. задатак

Поставка

1. Детаљно описати поступак за проналажење јако повезаних компоненти у графу.
2. За граф са слике (неких 7-8 чворова) по корацима применити алгоритам за проналажење јако повезаних компоненти и резултујући граф.

Решење

Видети задатак из јулског рока 2020.

10. задатак

Поставка

Потребно је чувати неки скуп бројева који ће бити у опсегу између 1 и 100.

1. Упоредити секвенцијалну и уланчану репрезентацију скупа и упоредити сложеност операција додавања елемента, брисања елемента и провере припадности елемента скупу за ове две репрезентације.
2. Нека је дат скуп (нпр. 5, 14, 44, 45, 78, 98) приказати једну и другу репрезенатцију након операција (нпр. додавање 7, додавање 46, додавање 97, брисање 78).

Решење

Код секвенцијалне се алоцира вектор С[1:100] и уколико је елемент X у скупу, у поље С[X] се уписује 1, иначе 0. Код уланчане репрезентације је најефикасније чувати уланчану листу у растућем или опадајућем поретку. Додавање/брисање у секвенцијалној се ради у О(1) тако што се само провери или измени индекс у низу. Код уланчане репрезентације је потребно проћи кроз листу до локације на коју треба уметнути/обрисати елемент (по растућем или опадајућем поретку).