АСП1/Јул 2018

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Задаци

1. задатак

Поставка

Одредити бинарно стабло чијим екстерним чворовима су придружене тежине: 3, 6, 3, 1, за које је тежинска екстерна дужина пута најмања и израчунати ту дужину.

Решење

  13
 /  \
6    7
    / \
   3   4
      / \
     3   1

Екстерна дужина пута:

2. задатак

Поставка

Дат је аритметички израз у инфиксној нотацији: 3+7+4*(2+1). Претворити дати израз у постфиксни израз, а затим приказати стање стека по корацима током израчунавања вредности добијеног постфиксног израза. Сматрати да показивач врха стека показује на последњу заузету локацију и обележити га на слици.

Решење

Постфиксни израз: 3 7 + 4 2 1 + * +

3 7 + 4 2 1 + * +
-- -- -- -- -- -- -- -- --
-- -- -- -- -- -- -- -- --
-- -- -- -- -- -- -- -- --
-- -- -- -- -- 1 -- -- --
-- -- -- -- 2 2 3 -- --
-- 7 -- 4 4 4 4 12 --
3 3 10 10 10 10 10 10 22

3. задатак

Поставка

Посматра се векторска имплементација комплетног или скоро комплетног стабла реда 3 у виду вектора V[1:н].

  1. Приказати стабло чија је векторска репрезентација дата на слици.
  2. Написати у псеудокоду функцију која налази пут од чвора са индексом к ка корену и функцију која налази све синове чвора са индексом к.
Слика уз део под а.
1 2 3 4 5 6 7 8 9 10 11 12 13

Решење

            1
       /    |    \
   2        3         4
 / | \    / | \    /  |  \
5  6  7  8  9 10  11  12  13

У псеудокоду испод претпоставља се да нам пут од чвора ка корену као и деца тренутног чвора требају враћени као уланчане листе.

NODE TO ROOT(V, n, k)
t = 0
path = nil
p = k
while p ≠ 0 do
    LIST_INSERT(path, v[p])
    t = p mod 3
    if t = 0 then
        p = p / 3
    else if t = 1 then
        p = (p - 1) / 3
    else
        p = (p + 1) / 3
    end_if
end_while
return path
CHILD NODES(V, n, k)
children = nil
if 3 * k - 1 ≤ n then
    LIST_INSERT(children, v[3 * k - 1])
end_if
if 3 * k ≤ n then
    LIST_INSERT(children, v[3 * k])
end_if
if 3 * k + 1 ≤ n then
    LIST_INSERT(children, v[3 * k + 1])
end_if
return children

4. задатак

Поставка

Нека је дата општа квадратна матрица А[л:у, л:у] која садржи елементе само испод главне дијагонале, укључујући и ту дијагоналу. Формално дефинисати и кратко објаснити адресну функцију за приступ произвољном елементу А[и, ј], уколико се матрица линеаризује по врстама.

Решење

  • је адреса почетног елемента матрице.
  • је број елемената у редовима изнад елемента којег тражимо. је број редова изнад тренутног реда и стога број елемената у реду изнад нашег, а пошто број елемената опада са бројем реда овај збир добијамо као Гаусов збир.
  • је број елемената лево од нашег тренутног елемента.

5. задатак

Поставка

Нека се посматра један скуп веб страница у оквиру локалног интранета једне компаније. Свака страница садржи одређени број хиперлинкова који воде ка другим страницама у оквиру интранета.

  1. Описати на који начин се овај скуп страница може моделовати графом. Коментарисати тип и усмереност графа.
  2. Написати у псеудокоду итеративну функцију која одређује просечан број кликова потребан да се са неке веб странице стигне до неке друге веб странице у оквиру компанијског интранета. Просек рачунати на нивоу свих могућих парова страница.

Решење

Овај скуп страница се може моделовати нетежинским усмереним графом где чворови представљају странице а грана од стране А до стране Б значи да постоји веза на страни А до стране Б.

AVG CLICKS NUM(G)
for i = 1 to n do
    for i = 1 to n do
        if (i, j) ∈ E then
            d[i, j] = 1
        else
            d[i, j] = ∞
        end_if
    end_for
end_for
for k = 1 to n do
    for i = 1 to n do
        for j = 1 to n do
            if d[i, k] + d[k, j] < d[i, j] then
                d[i, j] = d[i, k] + d[k, j]
            end_if
        end_for
    end_for
end_for
for i = 1 to n do
    for j = 1 to n do
        if i ≠ j then
            sum = sum + d[i, j]
        end_if
    end_for
end_for
return sum / (n * (n - 1))

6. задатак

Поставка

Граф из поставке задатка.

Применом алгоритма за одређивање критичних путева у графу одредити критичне путеве у графу са слике као и дозвољена кашњења свих активности у графу.

Решење

Критични путеви: АЕДЦМ и АЕДВМ.

Чвор ЕСТ
А 0
Б 6
C 10
D 5
Е 2
К 6
M 13
V 11
Активност I
А-Б 3
А-Е 0
Е-D 0
D-Б 1
D-Ц 0
Б-C 1
C-М 0
D-В 0
V-М 0
Е-V 2
Е-К 2
К-V 2

7. задатак

Поставка

Дата је двоструко уланчана листа. Имплементирати функцију РЕАРРАНГЕ_ЛИСТ која прослеђену листу преуређује тако да се сви елементи са непарних позиција у оригиналном поретку нађу пре свих елемената са парних позиција у оригиналном поретку.

Решење

LIST REMOVE(node)
next(prev(node)) = next(node)
prev(next(node)) = prev(node)
return node
LIST INSERT(before, node)
t = prev(before)
prev(before) = node
next(t) = node
prev(node) = t
next(node) = before
return node
REARRANGE LIST(head)
if head = nil then
    return
end_if
p = head
n = nil
loop
    for k = 1 to i + 1 do
        p = next(p)
        if p = nil then
            return
        end_if
    end_for
    n = LIST_REMOVE(p)
    for k = 1 to i do
        p = prev(p)
    end_for
    LIST_INSERT(p, n)
    p = n
    i = i + 1
end_loop

8. задатак

Поставка

Приказати поступак кодирања поруке АДБЕЦДААДБЕ применом динамичког Хуффман алгоритма.

Решење

Крајње Хуффман-ово стабло:

      11
     /   \
   5       6
  / \     / \
 B   3   D   A
 2  / \  3   3
   1   E
  / \  2
NYT  C
 0   1

Крајња порука: А 0Д 00Б 100Е 000Ц 00 00 01 10 00 011

9. задатак

Поставка

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

Решење

GETNODE(i, j)
ALLOCATE(node)
from(node) = i
to(node) = j
next(node) = nil
return node
GASOLINE TRAVEL(G, src, dst)
branches = nil
t = nil
for i = 1 to n do
    for j = 1 to n do
        if e[i, j] = 1 then
            if branches = nil then
                branches = GETNODE(i, j)
            else
                t = next(branches)
                next(branches) = GETNODE(i, j)
                next(next(branches)) = t
            end_if
        end_if
    end_for
end_for
S = {src}
loop
    t = branches
    min_branch = nil
    while t ≠ nil do
        if (from(t) ∈ S) and (to(t) ∈ (V - S) then
            if (min_branch = nil) or (w(from(t), to(t)) < w(from(min_branch), to(min_branch))) then
                min_branch = t
            end_if
        end_if
        t = next(t)
    end_while
    if to(min_branch) = dst then
        return last_min
    end_if
    S = S + {to(min_branch)}
end_loop

10. задатак

Поставка

Приликом обиласка неког графа може се добити стабло обиласка.

  1. Дефинисати ово стабло.
  2. Приликом обиласка усмереног графа по дубини добијена су почетна (т1) и завршна времена (т2) чворова као у приложеној табели. Реконструисати стабло обиласка и прецизно објаснити поступак реконструкције.
т1 т2
А 3 4
Б 5 10
C 11 12
D 14 15
Е 8 9
Ф 2 13
Г 1 16
Х 6 7

Решење

  1. Стабло обиласка је ациклични неусмерени нетежински граф чије гране означавају из ког је чвора посећен који чвор приликом обиласка графа, а чворови су исти као у графу који се обилази.
  2. Поступак иде тако што удемо предом кроз бројеве и чувамо један имагинарни показивач који је у постављам на корен. Ако означава почетно време неког чвора, на тренутни показивач додајемо дете са вредношћу тог чвора и пребацујемо показивач на то дете. Ако означава крајње време неког чвора, пребацујемо показивач на његовог родитеља (ако је показивач на корену, завршавамо).
     G
    / \
   F   D
 / | \
A  B  C
  / \
 H   E