АСП2/К3 2019

1. задатак

Поставка

Употребом методе хеширања имплементирати функцију ФИНД_НУМ_ОФ_ПАИРС која треба да пронађе укупан број парова целобројних вредности у задатом низу арр који у суми по модулу н дају вредност к која представља параметар функције. За реализацију ове функције треба користити методу одвојеног уланчавања.

Решење

Овде нема потребе користити било какво уланчавање јер је цоунтинг сорт довољан да изброји кључеве који дају неку вредност по модулу н а затим измножи избројано. На пример, за н = 7 и к = 1 на суму се редом додају:

$\frac{C[0] \cdot C[1]}{2}$
$\frac{C[1] \cdot C[0]}{2}$
$\frac{C[2] \cdot C[6]}{2}$
$\frac{C[3] \cdot C[5]}{2}$
$\frac{C[4] \cdot (C[4] - 1)}{2}$
$\frac{C[5] \cdot C[3]}{2}$
$\frac{C[6] \cdot C[2]}{2}$

FIND NUM OF PAIRS(arr, n, k)
for i = 0 to n-1 do
    C[i] = nil
end_for
for i = 1 to LENGTH(arr) do
    adr = arr[i] mod n
    if C[adr] = nil then
        C[adr] = GETNODE
        value(C[adr]) = arr[i]
        next(C[adr]) = nil
    else
        curr = next(C[adr])
        prev = C[adr]
        while curr ≠ nil do
            prev = curr
            curr = next(curr)
        end_while
        next(prev) = GETNODE
        value(next(prev)) = arr[i]
        next(next(prev)) = nil
    end_if
end_for
count = 0
for i = 0 to n-1 do
    node_count_1 = 0
    curr = C[i]
    while curr ≠ nil do
        node_count_1 = node_count_1 + 1
        curr = next(curr)
    end_while
    node_count_2 = 0
    j = (k - i) mod n
    curr = C[j]
    while curr ≠ nil do
        node_count_2 = node_count_2 + 1
        curr = next(curr)
    end_while
    if i = j then
        count = count + node_count_1 * (node_count_1 - 1) / 2
    else
        count = count + node_count_1 * node_count_2 / 2
    end_if
end_for
for i = 0 to n-1 do
    curr = C[i]
    while curr ≠ nil do
        tmp = curr
        curr = next(curr)
        FREENODE(tmp)
    end_while
end_for
return count

2. задатак

Поставка

Приказати изглед биномног хипа након сваке измене, уколико се умећу кључеви 19, 11, 25 и након тога обрише минимум.

Решење

Испод је дато коначно решење задатка, а кораци се могу симулирати у симулатору биномних хипова, редом уметањем кључева 14, 27, 12, 23, 15, 22, 5, 9 и 17, па затим извршавати задате операције.

АСП2 К3 2019 задатак 2 хип поставка.пнг

Поставка задатка
АСП2 К3 2019 задатак 2 хип решење.пнг

Коначни изгледа хипа

3. задатак

Поставка

Дата је секвенца кључева: 27, 25, 14, 34, 7, 1, 5, 193, 33, 41, 73, 124. Приказати рад радиx сорт алгоритма по корацима.

Решење

Први корак *радиx сорт* алгоритма
1	3	4	5	7
1	193	14	25	27
41	33	34	5	7
	73	124

Добијена секвенца после првог корака: 1, 41, 193, 33, 73, 14, 34, 124, 25, 5, 27, 7

Други корак *радиx сорт* алгоритма
0	1	2	3	4	7	9
1	14	124	33	41	73	193
5		25	34
7		27

Добијена секвенца после другог корака: 1, 5, 7, 14, 124, 25, 27, 33, 34, 41, 73, 193.

Трећи корак неће бити приказан јер ће у суштини само прве две колоне бити јако попуњене, али се на крају добија поредак: 1, 5, 7, 14, 25, 27, 33, 34, 41, 73, 124, 193.

4. задатак

Поставка

Подаци се смештају у хеш табелу са 10 улаза применом хеш функције х_п(К) = К мод 10. За разрешавање колизија се користи метода обједињеног уланчавања. Приказати попуњавање дате табеле након уметања сваког од следећих кључева: 37, 41, 18, 16, 12. Након свих уметања, одредити вероватноћу попуњавања празних улаза, под претпоставком да су сви кључеви једнако вероватни.

Табела из поставке задатка
0	1	2	3	4	5	6	7	8	9
	11							21	29
-1	8	-1	-1	-1	-1	-1	-1	-1	-1
								фрее

Решење

Табела након уметања 37
0	1	2	3	4	5	6	7	8	9
	11						37	21	29
-1	8	-1	-1	-1	-1	-1	-1	-1	-1
								фрее

Табела након уметања 41
0	1	2	3	4	5	6	7	8	9
	11					41	37	21	29
-1	8	-1	-1	-1	-1	-1	-1	6	-1
						фрее

Табела након уметања 18
0	1	2	3	4	5	6	7	8	9
	11				18	41	37	21	29
-1	8	-1	-1	-1	-1	5	-1	6	-1
					фрее

Табела након уметања 16
0	1	2	3	4	5	6	7	8	9
	11			16	18	41	37	21	29
-1	8	-1	-1	-1	4	5	-1	6	-1
				фрее

Табела након уметања 12
0	1	2	3	4	5	6	7	8	9
	11	12		16	18	41	37	21	29
-1	8	-1	-1	-1	4	5	-1	6	-1
				фрее

Вероватноћа попуњавања улаза 0 је $\frac{1}{10}$ , јер се он попуњава само уколико се умеће број конгруентан са 0 по модулу 10. Вероватноћа попуњавања улаза 3 је, стога, $\frac{9}{10}$ , јер се он попуњава за било који други модуо.

5. задатак

Поставка

Приложени псеудокод приказује алгоритам за уређивање шпила карата у једној карташкој игри. У игри се користи шпил од по 8 карата за сваки од 4 знака (укупно 32). Алгоритам треба да групише карте истог знака, при чему карте истог знака сортира према растућој вредности. Уочити и објаснити грешке или недостатке приложеног алгоритма и написати у псеудокоду исправну имплементацију у складу са захтевима. Поље вал представља вредност карте, а поље сигн њен знак.

for i = 2 to 32 do
  k = cards[i]
  j = i-1
  while(j>0 and cards[j].val>k.val) do
    cards[j+1] = cards[j]
    j = j-1
  end_while
  cards[j] = k
end_for
for i = 1 to 4 do
  c[i] = 0
end_for
for j = 1 to n do
  c[cards[j].sign] = c[cards[j].sign]+1
end_for
for i = 3 downto 1 do
  c[i] = c[i+1] - c[i]
end_for
for j = 1 to n do
  b[c[cards[j].sign]] = cards[j]
  c[cards[j].sign] = c[cards[j].sign]-1
end_for

Решење

Следеће грешке су уочене:

Низ cards почиње од 1 а на крају while петље се поставља cards[j] на вредност k, с тим што је један од услова петље j > 0. Овде се мора преправити на cards[j + 1].
Цоунтинг сорт имплементација за сортирање по знаку не ради.

SORT(cards)
for i = 2 to 32 do
    k = cards[i]
    j = i - 1
    while (j > 0) and (val(cards[j]) > val(k)) do
        cards[j + 1] = cards[j]
        j = j - 1
    end_while
    cards[j + 1] = k
end_for
for i = 1 to 4 do
    c[i] = 0
end_for
for j = 1 to n do
    c[sign(cards[j])] = c[sign(cards[j])] + 1
end_for
for i = 2 to 4 do
    c[i] = c[i-1] + c[i]
end_for
for j = n downto 1 do
    b[c[sign(cards[j])]] = cards[j]
    c[sign(cards[j])] = c[sign(cards[j])] - 1
end_for

6. задатак

Поставка

Користећи идеју qуицк сорт алгоритма, написати у псеудокоду функцију која враћа к-ти најмањи елемент у задатом низу целих бројева арр. Приликом избора пивот-а, користити медијану од три погодно изабране вредности.

Решење

QUICK SELECT(arr, k)
min = FIND(arr, 1, n, k)
return min

FIND(a, low, high, k)
j = PARTITION(a, low, high)
i = low + k - 1
if(i = j) then
  return a[i]
end_if
if(j > i)
  return FIND(a, low, j - 1, k)
else
  return FIND(a, j + 1, high, k)
end_if

PARTITION(a, down, up)
i = down
j = up
pivot = a[median(a[i], i, a[j], j, a[(i + j) / 2], (i + j) / 2)]
while(i < j) do
  while(a[i] <= pivot) and (i < j) do
    i = i + 1
  end_while
  while(a[j] > pivot) do
    j = j - 1
  end_while
  if(i < j) then
    a[i] <-> a[j]
  end_if
end_while
a[down] = a[j]
a[j] = pivot
return j

median(a, pos_a, b, pos_b, c, pos_c)
if(a > b) xor (a > c)
  return pos_a
else if(b < a) xor (b < c)
  return pos_b
else
  return pos_c
end_if

7. задатак

Поставка

Подаци се смештају у хеш табелу са 9 улаза применом хеш функције хп(К)=К мод 9. За разрешавање колизија се користи метода линеарног претраживања са кораком 2. Дефинисати појам примарног и секундарног груписања, а затим на примеру делимично попуњене табеле са слике, илустровати један сценарио уметања код којег се дешава примарно груписање и један сценарио уметања код којег се дешава секундарно груписање.

Табела из поставке задатка
0	27
1
2	11
3
4
5	23
6
7
8	8

Решење

Секундарно груписање је када хеш функција за два различита кључа враћа исту матичну адресу, па су им и испитни низови једнаки. Када уметнемо кључ 18, добијамо секундарно груписање:

18 % 9 = 0 (овде се десило секундарно груписање, јер кључеви 27 и 18 имају исту матичну адресу 0)
- (0 + 2) % 9 = 2 (овде се десило примарно груписање, јер се испитни низ по модулу 0 и испитни низ по модулу 2 овде преклапају)
- (2 + 2) % 9 = 4

Табела након уметања кључа 18
0	27
1
2	11
3
4	18
5	23
6
7
8	8

Примарно груписање је када се два испитна низа од различитих матичних адреса преклопе. Та појава се такође може илустровати на примеру уметања кључа 20:

20 % 9 = 2 (овде се десило секундарно груписање, јер кључеви 11 и 20 имају исту матичну адресу 2)
- (2 + 2) % 9 = 4 (овде се десило примарно груписање, јер се испитни низови по модулу 2 и по модулу 0 поново преклапају)
- (4 + 2) % 9 = 6

Табела након уметања кључа 20
0	27
1
2	11
3
4	18
5	23
6	20
7
8	8

8. задатак

Поставка

Нека се код спољашњег хеширања користи хеш табела са 4 бакета, који имају капацитет б = 3. За хеш функцију се користи метод дељења К мод 4, а за разрешавање колизије линеарно претраживање. Нека се при брисању користи метод селективног померања (аналогно као код унутрашњег хеширања). У табелу треба уметнути кључеве 60, 18, 23, 50, 47, 34, 82, 14, 67 и 38, а затим брисати кључеве 50, 47, 23 и 34. Приказати изглед табеле након сваког разрешења колизије при уметању, као након сваког брисања.

Решење

АСП2/К3 2019

Садржај

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

7. задатак

Поставка

Решење

8. задатак

Поставка

Решење

Мени за навигацију

АСП2/К3 2019

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

7. задатак

Поставка

Решење

8. задатак

Поставка

Решење

Мени за навигацију

Претрага