АСП1/Јун 2020
Први колоквијум
1. задатак
Поставка
Написати псеудокод за дубоко копирање листе на коју показује показивач хеад ако поред информационог садржаја сваки члан листе садржи показивач на следећи чвор и показивач на неки елемент листе.
Решење
DEEP COPY(head)
2. задатак
Поставка
Пребацити израз из постфиксне у инфиксну нотацију.
Решење
POST2IN(expr)
3. задатак
Поставка
Нацртати промену стања векторске имплементације приоритетног реда приликом уметања и брисања елемената.
Решење
4. задатак
Поставка
Извести адресну функцију за ретку матрицу где се ненулти елементи налазе у квадратима димензија к смештеним на главној дијагонали.
| - | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 |
| 2 | 3 | 4 | 5 | 0 | 0 | 0 | 0 |
| 3 | 0 | 6 | 7 | 8 | 0 | 0 | 0 |
| 4 | 0 | 0 | 9 | 10 | 11 | 0 | 0 |
| 5 | 0 | 0 | 0 | 12 | 13 | 14 | 0 |
| 6 | 0 | 0 | 0 | 0 | 15 | 16 | 17 |
| 7 | 0 | 0 | 0 | 0 | 0 | 18 | 19 |
Решење
Други колоквијум
1. задатак
Поставка
- Да ли се бинарно стабло може једнозначно реконструисати из преордер и постордер обиласка тог стабла?
- Дати све могуће реконструкције стабла чији је преордер обилазак (?) а постордер (?).
Решење
- Не може, јер ако неки чвор има само једно дете не може се одредити да ли је то лево или десно дете само из преордер и постордер обиласка тог стабла.
- (Биле су четири могуће реконструкције јер су два чвора имала само једно дете.)
2. задатак
Поставка
Морзеови кодови се састоје из тачки (.) и црта (-) и свако слово алфабета се кодира секвенцом тачки и црта. Ако се зна да један код може преклапати са почетком неког другог кода, осмислити структуру која би могла да се користи за декодирање Морзеових кодова и написати псеудокод за декодирање поруке кодиране Морзеовим кодовима ако се зна да се између слова налази бланко знак.
Решење
Структура погодна за декодирање Морзеових кодова јесте бинарно стабло где гране улево означавају да код на том месту садржи тачку а гране удесно да код на том месту садржи црту и у сваком чвору се чува у које слово се декодира код чије су гране праћене да би се стигло до тог чвора, или 0 ако се тај код не декодира ни у једно слово.
DECODE MORSE(msg, root)
i = 0
new_msg = ""
while msg[i] ≠ 0 do
p = root
while (msg[i] ≠ ' ') and (p ≠ nil) do
if msg[i] = '.' then
p = left(p)
else if msg[i] = '-' then
p = right(p)
else
ERROR(Invalid code)
end_if
i = i + 1
end_while
i = i + 1
if (p = nil) or (sign(p) = 0) then
ERROR(Invalid code)
end_while
new_msg = new_msg + sign(p)
end_while
return new_msg
3. задатак
Поставка
Кодирати секвенцу БИББИДИБОББИДИБОО по корацима.
Решење
Крајње кодирано: 0204153628033
| Слово | Код |
|---|---|
| Б | 0 |
| D | 1 |
| I | 2 |
| О | 3 |
| БИ | 4 |
| ИБ | 5 |
| ББ | 6 |
| БИД | 7 |
| DI | 8 |
| ИБО | 9 |
| ОБ | 10 |
| ББИ | 11 |
| ИД | 12 |
| ДИБ | 13 |
| БО | 14 |
| ОО | 15 |
| Унос | Стринг | Испис | Додаје се у табелу |
|---|---|---|---|
| Б | Б | ||
| I | БИ | 0 (Б) | БИ |
| Б | ИБ | 2 (I) | ИБ |
| Б | ББ | 0 (Б) | ББ |
| I | БИ | ||
| D | БИД | 4 (БИ) | БИД |
| I | DI | 1 (D) | DI |
| Б | ИБ | ||
| О | ИБО | 5 (ИБ) | ИБО |
| Б | ОБ | 3 (О) | ОБ |
| Б | ББ | ||
| I | ББИ | 6 (ББ) | ББИ |
| D | ИД | 2 (I) | ИД |
| I | DI | ||
| Б | ДИБ | 8 (DI) | ДИБ |
| О | БО | 0 (Б) | БО |
| О | ОО | 3 (О) | ОО |
| О | 3 (О) |
4. задатак
Поставка
- Дефинисати интерну дужину пута, екстерну дужину пута и екстерну тежинску дужину пута.
- Написати алгоритам који за дато стабло рачуна екстерну тежинску дужину пута. Сматрати да листови стабла садрже информације о тежини. Дозвољено је коришћење линеарних структура података.
Решење
- Интерна дужина пута је збир дужина путева од корена до сваког интерног чвора.
- Екстерна дужина пута је збир дужина путева од корена до сваког екстерног чвора.
- Екстерна тежинска дужина пута је збир производа дужина путева од корена до сваког екстерног чвора и тежине тих екстерних чворова.
За потребе овог алгоритма сматра се да су екстерни чворови изједначени са листовима.
EXTERNAL WEIGHTED PATH LENGTH(root)
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_levels)
INSERT(Q_nodes, root)
INSERT(Q_levels, 0)
node = nil
level = 0
pwe = 0
while not QUEUE_EMPTY(Q_nodes) do
node = DELETE(Q_nodes)
level = DELETE(Q_levels)
if (left(node) = nil) and (right(node) = nil) then
pwe = pwe + level * weight(node)
end_if
if left(node) ≠ nil then
INSERT(Q_nodes, left(node))
INSERT(Q_levels, level + 1)
end_if
if right(node) ≠ nil then
INSERT(Q_nodes, right(node))
INSERT(Q_levels, level + 1)
end_if
end_while
return pwe
Трећи колоквијум
1. задатак
Поставка
Дат је ацикличан граф представљен матрицом суседности чији су чворови нумерисани на насумичан начин. Написати псеудокод који враћа начин ренумерације чворова тако да матрица суседности буде доња троугаона.
Решење
RESEQUENCE(G)
topsort_length = 0
for i = 1 to n do
in_deg[i] = 0
for j = 1 to n do
if M[j, i] then
in_deg[i] = in_deg[i] + 1
end_if
end_for
if in_deg[i] = 0 then
topsort_length = topsort_length + 1
topsort[topsort_length] = i
end_if
end_for
for i = 1 to n do
node = topsort[i]
for j = 1 to n do
if M[node, j] then
in_deg[j] = in_deg[j] - 1
if in_deg[j] = 0 then
topsort_length = topsort_length + 1
topsort[topsort_length] = j
end_if
end_if
end_for
end_for
return topsort
2. задатак
Поставка
- (?)
- Написати поступак за Флојдов алгоритам на датом графу. (?)
- Написати најкраћи пут од чвора б до чвора д.
Решење
- (?)
- (?)
- бфацед
3. задатак
Поставка
Дат је проточни граф на слици (?). Нацртати резидуални граф од тог проточног графа и навести све путеве повећаног протока и написати њихов проток.
Решење
- СЦБТ (2)
- САЦБТ (2)
- СДЕЦБТ (2)
- СДАЦБТ (2)
4. задатак
Поставка
Описати на који начин се у неусмереном графу може детектовати циклус помоћу обиласка по ширини и дубини и написати итеративни алгоритам за детекцију циклуса у неусмереном графу помоћу обиласка по ширини. Дозвољено је користити линеарне структуре података.
Решење
Обиласком по ширини или дубини се у неусмереном графу може детектовати циклус тако што приликом обиласка детектујемо да посећујемо чвор који смо већ посетили, а да то није отац тренутног чвора у стаблу обиласка.
IS CYCLIC(G)
for i = 1 to n do
visited[i] = 0
end_for
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_parents)
INSERT(Q_nodes, 1)
INSERT(Q_parents, 0)
node = parent = 0
while not QUEUE_EMPTY(Q_nodes) do
node = DELETE(Q_nodes)
parent = DELETE(Q_parents)
for (node, i) ∈ E do
if i = parent then
continue
end_if
if visited[i] then
return true
end_if
INSERT(Q_nodes, i)
INSERT(Q_parents, node)
visited[i] = true
end_for
end_while
return false