АСП2/К3 2018 - Историја измена

KockaBot: Замена начина истицања милокода.

2024-09-13T00:09:15Z

Замена начина истицања милокода.

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 35:		Ред 35:
	=== Rešenje ===		=== Rešenje ===
	Prilikom umetanja tražimo prvu poziciju na kojoj je prazno mesto, prvo jednom a zatim i drugom heš funkcijom. Ako se desi da se vratimo na početnu poziciju, to znači da je tabela puna i ključ se ne može umetnuti.		Prilikom umetanja tražimo prvu poziciju na kojoj je prazno mesto, prvo jednom a zatim i drugom heš funkcijom. Ako se desi da se vratimo na početnu poziciju, to znači da je tabela puna i ključ se ne može umetnuti.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	INSERT(table, K)		INSERT(table, K)
	adr1 = adr1_init = h1(K)		adr1 = adr1_init = h1(K)
Ред 54:		Ред 54:
	until (adr1 = adr1_init) or (adr2 = adr2_init)		until (adr1 = adr1_init) or (adr2 = adr2_init)
	ERROR(Tabela je puna)		ERROR(Tabela je puna)
	</~~syntaxhighlight~~>		</nowiki>}}
	Pretraga je slična umetanju, s tim što ako naiđemo na neprazno polje prvo proveravamo da li to polje sadrži traženi ključ i nastavljamo pretragu ako ne sadrži. Pretraga se takođe završava ako su obe pretrage došle do praznog polja.		Pretraga je slična umetanju, s tim što ako naiđemo na neprazno polje prvo proveravamo da li to polje sadrži traženi ključ i nastavljamo pretragu ako ne sadrži. Pretraga se takođe završava ako su obe pretrage došle do praznog polja.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	SEARCH(table, K)		SEARCH(table, K)
	adr1 = adr1_init = h1(K)		adr1 = adr1_init = h1(K)
Ред 73:		Ред 73:
	until (adr1 = adr1_init) or (adr2 = adr2_init) or ((table[adr1] = empty) and (table[adr2] = empty))		until (adr1 = adr1_init) or (adr2 = adr2_init) or ((table[adr1] = empty) and (table[adr2] = empty))
	return false		return false
	</~~syntaxhighlight~~>		</nowiki>}}

	== 3. zadatak ==		== 3. zadatak ==
Ред 121:		Ред 121:
	=== Rešenje ===		=== Rešenje ===
	Kod ovog algoritma jeste najveći problem to što <code>n-1</code> puta radi iteraciju kroz niz, kada je to potrebno raditi samo dok se ne desi da nije bilo nijedne zamene u unutrašnjoj petlji. Drugi problem jeste nepotreban prolazak od kraja do početka niza, kada je prolazak od početka do kraja potencijalno efikasniji zbog keš memorije. Takođe, nije potrebno prolaziti kroz sortirani deo prilikom zamene elemenata.		Kod ovog algoritma jeste najveći problem to što <code>n-1</code> puta radi iteraciju kroz niz, kada je to potrebno raditi samo dok se ne desi da nije bilo nijedne zamene u unutrašnjoj petlji. Drugi problem jeste nepotreban prolazak od kraja do početka niza, kada je prolazak od početka do kraja potencijalno efikasniji zbog keš memorije. Takođe, nije potrebno prolaziti kroz sortirani deo prilikom zamene elemenata.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	BUBBLE SORT REVISITED(arr, n)		BUBBLE SORT REVISITED(arr, n)
	pos = n		pos = n
Ред 135:		Ред 135:
	end_for		end_for
	until broj_zamena = 0		until broj_zamena = 0
	</~~syntaxhighlight~~>		</nowiki>}}

	== 5. zadatak ==		== 5. zadatak ==
Ред 233:		Ред 233:
	* Ulančana lista je jednostruko ulančana, pa naknadno moramo dohvatati elemente liste koje sadrže stablo sa minimalnim korenom nakon pozivanja <code>findMin</code>		* Ulančana lista je jednostruko ulančana, pa naknadno moramo dohvatati elemente liste koje sadrže stablo sa minimalnim korenom nakon pozivanja <code>findMin</code>
	* Ulančana lista u hipu sadrži polje ''next'' koje pokazuje do sledećeg čvora ulančane liste i polje ''value'' koje pokazuje na ''BinTree'' objekat, i sve operacije kao što su se koristile na ASP1 su podržane		* Ulančana lista u hipu sadrži polje ''next'' koje pokazuje do sledećeg čvora ulančane liste i polje ''value'' koje pokazuje na ''BinTree'' objekat, i sve operacije kao što su se koristile na ASP1 su podržane
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	REMOVE MIN KEY(binheap)		REMOVE MIN KEY(binheap)
	first_node = binheap.getFirst()		first_node = binheap.getFirst()
Ред 257:		Ред 257:
	FREETREE(min_tree)		FREETREE(min_tree)
	FREENODE(curr_node)		FREENODE(curr_node)
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	INSERT TREE(binheap, bintree)		INSERT TREE(binheap, bintree)
	curr = binheap.getFirst()		curr = binheap.getFirst()
Ред 281:		Ред 281:
	value(next(prev)) = bintree		value(next(prev)) = bintree
	next(next(prev)) = nil		next(next(prev)) = nil
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==

Etfsibg: /* Rešenje */

2022-01-22T21:19:01Z

Rešenje

← Старија измена		Верзија на датум 22. јануар 2022. у 23:19
Ред 123:		Ред 123:
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	BUBBLE SORT REVISITED(arr, n)		BUBBLE SORT REVISITED(arr, n)
	i = 1		pos = n
	repeat		repeat
			granica = pos
	broj_zamena = 0		broj_zamena = 0
	for j = 1 to n-i do		for i = 1 to granica - 1 do
	if arr[j] > arr[j+1] then		if arr[i] > arr[i+1] then
	arr[j] ↔ arr[j+1]		arr[i] ↔ arr[i+1]
			granica = i
	broj_zamena = broj_zamena + 1		broj_zamena = broj_zamena + 1
	end_if		end_if
	end_for		end_for
	~~i = i + 1~~
	until broj_zamena = 0		until broj_zamena = 0
	</syntaxhighlight>		</syntaxhighlight>

Etfsibg: /* Rešenje */

2022-01-22T20:28:53Z

Rešenje

← Старија измена		Верзија на датум 22. јануар 2022. у 22:28
Ред 91:		Ред 91:
	\|-		\|-
	! 5		! 5
	\| 84 \|\| 9 \|\| 42 \|\| 6 \|\| 46 \|\| 96 \|\| 84 \|\| 169 \|\| 158 \|\| 99 \|\| 495 \|\| 84 \|\| 223		\| 84 \|\| 9 \|\| 42 \|\| 6 \|\| 46 \|\| 96 \|\| 61 \|\| 169 \|\| 158 \|\| 99 \|\| 495 \|\| 84 \|\| 223
	\|-		\|-
	! 3		! 3

Etfsibg: /* Rešenje */

2022-01-22T19:14:04Z

Rešenje

← Старија измена		Верзија на датум 22. јануар 2022. у 21:14
Ред 44:		Ред 44:
	return		return
	else		else
	adr1 = adr1 + g(K)		adr1 = (adr1 + g(K)) mod n
	end_if		end_if
	if table[adr2] = empty then		if table[adr2] = empty then
Ред 50:		Ред 50:
	return		return
	else		else
	adr2 = adr2 + g(K)		adr2 = (adr2 + g(K)) mod n
	end_if		end_if
	until (adr1 = adr1_init) or (adr2 = adr2_init)		until (adr1 = adr1_init) or (adr2 = adr2_init)
Ред 64:		Ред 64:
	return true		return true
	else if table[adr1] ≠ empty then		else if table[adr1] ≠ empty then
	adr1 = adr1 + g(K)		adr1 = (adr1 + g(K)) mod n
	end_if		end_if
	if table[adr2] = K then		if table[adr2] = K then
	return true		return true
	else if table[adr2] ≠ empty then		else if table[adr2] ≠ empty then
	adr2 = adr2 + g(K)		adr2 = (adr2 + g(K)) mod n
	end_if		end_if
	until (adr1 = adr1_init) or (adr2 = adr2_init) or ((table[adr1] = empty) and (table[adr2] = empty))		until (adr1 = adr1_init) or (adr2 = adr2_init) or ((table[adr1] = empty) and (table[adr2] = empty))

KockaAdmiralac: Link do postavke

2021-06-27T13:55:57Z

Link do postavke

← Старија измена		Верзија на датум 27. јун 2021. у 15:55
Ред 1:		Ред 1:
	{{tocright}}		{{tocright}}
			[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K3_1718.pdf Postavka zadataka na stranici predmeta.]

	== 1. zadatak ==		== 1. zadatak ==

KockaAdmiralac: Ispravljen shellsort; ostale sitne ispravke

2021-01-19T12:58:51Z

Ispravljen shellsort; ostale sitne ispravke

← Старија измена		Верзија на датум 19. јануар 2021. у 14:58
Ред 94:		Ред 94:
	! 3		! 3
	\| 6 \|\| 9 \|\| 42 \|\| 61 \|\| 46 \|\| 96 \|\| 84 \|\| 169 \|\| 84 \|\| 99 \|\| 495 \|\| 158 \|\| 223		\| 6 \|\| 9 \|\| 42 \|\| 61 \|\| 46 \|\| 96 \|\| 84 \|\| 169 \|\| 84 \|\| 99 \|\| 495 \|\| 158 \|\| 223
			\|-
			! 3
			\| 6 \|\| 9 \|\| 42 \|\| 61 \|\| 46 \|\| 84 \|\| 84 \|\| 169 \|\| 96 \|\| 99 \|\| 495 \|\| 158 \|\| 223
	\|-		\|-
	! 2		! 2
	\| 6 \|\| 9 \|\| 42 \|\| 61 \|\| 46 \|\| 96 \|\| 84 \|\| 99 \|\| 84 \|\| 158 \|\| 223 \|\| 169 ~~\|\| 495~~		\| 6 \|\| 9 \|\| 42 \|\| 61 \|\| 46 \|\| 84 \|\| 84 \|\| 99 \|\| 96 \|\| 158 \|\| 223 \|\| 169 \|\| 495
	\|-
	~~! 1~~
	~~\| 6 \|\| 9 \|\| 42 \|\| 46 \|\| 61 \|\| 84 \|\| 96 \|\| 84 \|\| 99 \|\| 158 \|\| 169 \|\| 223~~ \|\| 495
	\|-		\|-
	! 1		! 1
Ред 125:		Ред 125:
	repeat		repeat
	broj_zamena = 0		broj_zamena = 0
	for i = 1 to n-i do		for j = 1 to n-i do
	if arr[i] > arr[i+1] then		if arr[j] > arr[j+1] then
	arr[i] ↔ arr[i+1]		arr[j] ↔ arr[j+1]
	broj_zamena = broj_zamena + 1		broj_zamena = broj_zamena + 1
	end_if		end_if
Ред 181:		Ред 181:
	\| 3 \|\| 2 \|\| 1		\| 3 \|\| 2 \|\| 1
	\|}		\|}
	* Prosečan broj neuspešnih pristupa: <math>~~P_nu~~ = 1 + \frac{5}{7} + \frac{5 \cdot 4}{7 \cdot 6} + \frac{5 \cdot 4 \cdot 3}{7 \cdot 6 \cdot 5} + \frac{5 \cdot 4 \cdot 3 \cdot 2}{7 \cdot 6 \cdot 5 \cdot 4} + \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3} =</math>		* Prosečan broj neuspešnih pristupa: <math>P_{nu} = 1 + \frac{5}{7} + \frac{5 \cdot 4}{7 \cdot 6} + \frac{5 \cdot 4 \cdot 3}{7 \cdot 6 \cdot 5} + \frac{5 \cdot 4 \cdot 3 \cdot 2}{7 \cdot 6 \cdot 5 \cdot 4} + \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3} =</math>
	*: <math>= 1 + \frac{5}{7} + \frac{10}{21} + \frac{2}{7} + \frac{1}{7} + \frac{1}{21} = \frac{8}{3} \approx 2.67</math>		*: <math>= 1 + \frac{5}{7} + \frac{10}{21} + \frac{2}{7} + \frac{1}{7} + \frac{1}{21} = \frac{8}{3} \approx 2.67</math>
	* Verovatnoća popunjavanja:		* Verovatnoća popunjavanja:
Ред 328:		Ред 328:
	* Ako je ulaz 0 zauzet: (5 + 6) % 8 = 3		* Ako je ulaz 0 zauzet: (5 + 6) % 8 = 3
	* itd.		* itd.
	U opštem slučaju neće doći do primarnog grupisanja jer je sekvenca ključeva u ispitnom nizu nasumična a ne ~~lineaarna~~, ali će doći do sekundarnog grupisanja jer ispitni niz zavisi samo od matične adrese i rednog broja pokušaja.		U opštem slučaju neće doći do primarnog grupisanja jer je sekvenca ključeva u ispitnom nizu nasumična a ne linearna, ali će doći do sekundarnog grupisanja jer ispitni niz zavisi samo od matične adrese i rednog broja pokušaja.

	== 8. zadatak ==		== 8. zadatak ==

KockaAdmiralac: Fali 8.

2020-12-29T22:30:10Z

Fali 8.

Нова страница

{{tocright}}

== 1. zadatak ==
=== Postavka ===
Prikazati izgled '''binarnog hipa''' nakon uklanjanja minimalnog ključa i nakon umetanja ključeva 9 i 30.
5
/ \
10 7
/ \ / \
47 32 12 31
/
54

=== Rešenje ===
Nakon uklanjanja minimalnog ključa:
7
/ \
10 12
/ \ / \
47 32 54 31
Nakon umetanja ključeva 9 i 30:
7
/ \
9 12
/ \ / \
10 32 54 31
/ \
47 30

== 2. zadatak ==
=== Postavka ===
Napisati iterativnu implementaciju sledećeg algoritma heširanja. Za heširanje se koriste dve heš funkcije, ''h1(K)'' i ''h2(K)'', dok se za razrešavanje kolizija koristi sekundarna heš funkcija ''g(k)''. Nad ključem ''K'' koji se ubacuje u tabelu se primenjuju i funkcija ''h1(K)'' i ''h2(K)'', a kao ulaz se koristi rezultat funkcije za koju se dobije manje kolizija. U slučaju jednakog broja kolizija, koristi se funkcija ''h1(K)''. Potrebno je realizovati operacije umetanja i pretrage.

=== Rešenje ===
Prilikom umetanja tražimo prvu poziciju na kojoj je prazno mesto, prvo jednom a zatim i drugom heš funkcijom. Ako se desi da se vratimo na početnu poziciju, to znači da je tabela puna i ključ se ne može umetnuti.
<syntaxhighlight lang="milo">
INSERT(table, K)
adr1 = adr1_init = h1(K)
adr2 = adr2_init = h2(K)
repeat
if table[adr1] = empty then
table[adr1] = K
return
else
adr1 = adr1 + g(K)
end_if
if table[adr2] = empty then
table[adr2] = K
return
else
adr2 = adr2 + g(K)
end_if
until (adr1 = adr1_init) or (adr2 = adr2_init)
ERROR(Tabela je puna)
</syntaxhighlight>
Pretraga je slična umetanju, s tim što ako naiđemo na neprazno polje prvo proveravamo da li to polje sadrži traženi ključ i nastavljamo pretragu ako ne sadrži. Pretraga se takođe završava ako su obe pretrage došle do praznog polja.
<syntaxhighlight lang="milo">
SEARCH(table, K)
adr1 = adr1_init = h1(K)
adr2 = adr2_init = h2(K)
repeat
if table[adr1] = K then
return true
else if table[adr1] ≠ empty then
adr1 = adr1 + g(K)
end_if
if table[adr2] = K then
return true
else if table[adr2] ≠ empty then
adr2 = adr2 + g(K)
end_if
until (adr1 = adr1_init) or (adr2 = adr2_init) or ((table[adr1] = empty) and (table[adr2] = empty))
return false
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Data je sekvenca ključeva: 169, 84, 99, 6, 61, 84, 9, 96, 158, 42, 495, 46, 223. Prikazati rad ''shell sort'' algoritma po koracima. Navesti korišćenu sekvencu inkremenata i obrazložiti izbor.

=== Rešenje ===
Inkrementi su izabrani kao u [[АСП2/К3 2020#6. zadatak|rešenju šestog zadatka sa trećeg kolokvijuma 2020. godine]].
{| class="wikitable"
! Inkrement !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12
|-
! Početak
| 169 || 84 || 99 || 6 || 61 || 84 || 9 || 96 || 158 || 42 || 495 || 46 || 223
|-
! 7
| 96 || 84 || 42 || 6 || 46 || 84 || 9 || 169 || 158 || 99 || 495 || 61 || 223
|-
! 5
| 84 || 9 || 42 || 6 || 46 || 96 || 84 || 169 || 158 || 99 || 495 || 84 || 223
|-
! 3
| 6 || 9 || 42 || 61 || 46 || 96 || 84 || 169 || 84 || 99 || 495 || 158 || 223
|-
! 2
| 6 || 9 || 42 || 61 || 46 || 96 || 84 || 99 || 84 || 158 || 223 || 169 || 495
|-
! 1
| 6 || 9 || 42 || 46 || 61 || 84 || 96 || 84 || 99 || 158 || 169 || 223 || 495
|-
! 1
| 6 || 9 || 42 || 46 || 61 || 84 || 84 || 96 || 99 || 158 || 169 || 223 || 495
|}

== 4. zadatak ==
=== Postavka ===
Priloženi pseudokod prikazuje jednu varijantu ''bubble sort'' algoritma za sortiranje podataka. Objasniti glavne nedostatke priloženog algoritma i napisati u pseudokodu alternativnu implementaciju ovog algoritma koja te nedostatke ispravlja.
<pre>
for i:=1 to n-1 do
for j:=n-1 downto 1 do
if arr[j]>arr[j+1] then
b:=arr[j]; arr[j]:=arr[j+1]; arr[j+1]:=b;
end_if
end_for
end_for
</pre>

=== Rešenje ===
Kod ovog algoritma jeste najveći problem to što <code>n-1</code> puta radi iteraciju kroz niz, kada je to potrebno raditi samo dok se ne desi da nije bilo nijedne zamene u unutrašnjoj petlji. Drugi problem jeste nepotreban prolazak od kraja do početka niza, kada je prolazak od početka do kraja potencijalno efikasniji zbog keš memorije. Takođe, nije potrebno prolaziti kroz sortirani deo prilikom zamene elemenata.
<syntaxhighlight lang="milo">
BUBBLE SORT REVISITED(arr, n)
i = 1
repeat
broj_zamena = 0
for i = 1 to n-i do
if arr[i] > arr[i+1] then
arr[i] ↔ arr[i+1]
broj_zamena = broj_zamena + 1
end_if
end_for
i = i + 1
until broj_zamena = 0
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Podaci se smeštaju u heš tabelu sa 7 ulaza primenom heš funkcije hp(K) = K mod 7. Za razrešavanje kolizija se koristi metoda dvostrukog heširanja sa sekundarnom heš funkcijom hs(K) = 4 + K mod 3. Odrediti prosečan broj pristupa prilikom neuspešnog traženja i verovatnoću popunjavanja praznih ulaza, pod pretpostavkom da su svi ključevi jednako verovatni.
{| class="wikitable"
|+ Tabela iz postavke zadatka
! 0
| 14
|-
! 1
|
|-
! 2
| 11
|-
! 3
| 24
|-
! 4
| 18
|-
! 5
|
|-
! 6
| 13
|}

=== Rešenje ===
{| class="wikitable"
|+ Ispitni nizovi
! 0 !! 1 !! 2
|-
| 0 || 0 || 0
|-
| 4 || 5 || 6
|-
| 1 || 3 || 5
|-
| 5 || 1 || 4
|-
| 2 || 6 || 3
|-
| 6 || 4 || 2
|-
| 3 || 2 || 1
|}
* Prosečan broj neuspešnih pristupa: <math>P_nu = 1 + \frac{5}{7} + \frac{5 \cdot 4}{7 \cdot 6} + \frac{5 \cdot 4 \cdot 3}{7 \cdot 6 \cdot 5} + \frac{5 \cdot 4 \cdot 3 \cdot 2}{7 \cdot 6 \cdot 5 \cdot 4} + \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3} =</math>
*: <math>= 1 + \frac{5}{7} + \frac{10}{21} + \frac{2}{7} + \frac{1}{7} + \frac{1}{21} = \frac{8}{3} \approx 2.67</math>
* Verovatnoća popunjavanja:
** 1: <math>\frac{1}{3} \left(\frac{6}{7} + \frac{2}{7} + \frac{4}{7}\right) = \frac{4}{7}</math>
** 5: <math>\frac{1}{3} \left(\frac{1}{7} + \frac{5}{7} + \frac{3}{7}\right) = \frac{3}{7}</math>

== 6. zadatak ==
=== Postavka ===
Napisati u pseudokodu funkciju za uklanjanje minimalnog ključa u binomnom hipu i njegovu naknadnu reorganizaciju. Nije potrebno sprovesti potencijalno spajanje stabala nakon uklanjanja čvora sa minimalnim ključem. Binomni hip predstavljen pomoću objekta klase BinHeap koja sadrži ulančanu listu objekata BinTree koji predstavljaju pojedinačna binomna stabla. Lista je uređena rastuće po stepenu stabla. Binomno stablo se sastoji od čvorova predstavljenih objektima klase BinNode. Funkcija kao argument prima objekat klase BinHeap. U nastavku je dat spisak metoda koje su na raspolaganju, njihove povratne vrednosti i klase objekata za koje ih treba pozvati.
{| class="wikitable"
! Metoda
! Povratna vrednost
! Objekat klase
|-
| ''getFirst''
| pokazivač na početak liste šume binomnih stabala
| ''BinHeap''
|-
| ''findMin''
| pokazivač na binomno stablo u čijem korenu je minimalni ključ
| ''BinHeap''
|-
| ''getOrder''
| red stabla
| ''BinTree''
|-
| ''setOrder''
| nema
| ''BinTree''
|-
| ''getRoot''
| pokazivač na koren binomnog stabla
| ''BinTree''
|-
| ''getNumOfChildren''
| broj potomaka čvora binomnog stabla
| ''BinNode''
|-
| ''getChildAtPos(index)''
| pokazivač na čvor koji je potomak objekta ''BinNode'' na poziciji index
| ''BinNode''
|}

=== Rešenje ===
Sledeće pretpostavke su usvojene pri implementaciji:
* <code>getFirst</code> vraća promenljivu referencu na lvrednost do početka ulančane liste, kako bismo mogli da ažuriramo taj početak
* <code>getChildAtPos</code> isto vraća promenljivu referencu na lvrednost. Ovo je kako bismo decu trenutnog čvora mogli da postavimo na nil, kako ne bi bila uništena prilikom dealokacije stabla (pretpostavljamo da postoji funkcija FREETREE koja to radi, slično FREENODE)
* Postoji funkcija GETTREE koja samo alocira stablo i kao koren postavlja svoj prvi argument
* Ulančana lista je jednostruko ulančana, pa naknadno moramo dohvatati elemente liste koje sadrže stablo sa minimalnim korenom nakon pozivanja <code>findMin</code>
* Ulančana lista u hipu sadrži polje ''next'' koje pokazuje do sledećeg čvora ulančane liste i polje ''value'' koje pokazuje na ''BinTree'' objekat, i sve operacije kao što su se koristile na ASP1 su podržane
<syntaxhighlight lang="milo">
REMOVE MIN KEY(binheap)
first_node = binheap.getFirst()
if first_node = nil then
return
end_if
min_tree = binheap.getMin()
prev_node = nil
curr_node = first_node
while value(curr_node) ≠ min_tree do
prev_node = curr_node
curr_node = next(curr_node)
end_while
next(prev_node) = next(curr_node)
root = min_tree.getRoot()
for i = 1 to root.getNumOfChildren() do
child = root.getChildAtPos(i)
tree = GETTREE(child)
tree.setOrder(child.getNumOfChildren())
INSERT_TREE(binheap, tree)
root.getChildAtPos(i) = nil
end_for
FREETREE(min_tree)
FREENODE(curr_node)
</syntaxhighlight>
<syntaxhighlight lang="milo">
INSERT TREE(binheap, bintree)
curr = binheap.getFirst()
prev = nil
while curr ≠ nil do
if value(curr).getOrder() ≥ bintree.getOrder() then
if prev = nil then
binheap.getFirst() = GETNODE
value(binheap.getFirst()) = bintree
next(binheap.getFirst()) = curr
else
next(prev) = GETNODE
value(next(prev)) = bintree
next(next(prev)) = curr
end_if
return
end_if
prev = curr
curr = next(curr)
end_while
next(prev) = GETNODE
value(next(prev)) = bintree
next(next(prev)) = nil
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Podaci se smeštaju u heš tabelu sa 8 ulaza primenom heš funkcije po metodu deljenja. Za razrešavanje kolizija se koristi metoda slučajnog pretraživanja (c = 3). Prikazati proces razrešavanja kolizije i generisati ispitne nizove za ključeve 21 i 18. Objasniti da li kod ovog metoda u opštem slučaju dolazi do primarnog i sekundarnog grupisanja i zašto.

=== Rešenje ===
Pošto se koristi metoda slučajnog pretraživanja, moramo generisati slučajni niz za generisanje ispitnog niza:
011 = 3
*2 110 = 6
*2 1100
-8 100
⊕3 111 = 7
*2 1110
-8 110
⊕3 101 = 5
*2 1010
-8 010
⊕3 001 = 1
*2 010 = 2
*2 100 = 4
*2 1000
-8 000
⊕3 011 ...
{| class="wikitable"
|+ Ispitni nizovi za 21 i 18
! 21 !! 18
|-
| 5 || 2
|-
| 0 || 5
|-
| 3 || 0
|-
| 4 || 1
|-
| 2 || 7
|-
| 6 || 3
|-
| 7 || 4
|-
| 1 || 6
|}
Proces razrešavanja kolizije:
* 21 % 8 = 5
* Ako je ulaz 5 zauzet: (5 + 3) % 8 = 0
* Ako je ulaz 0 zauzet: (5 + 6) % 8 = 3
* itd.
U opštem slučaju neće doći do primarnog grupisanja jer je sekvenca ključeva u ispitnom nizu nasumična a ne lineaarna, ali će doći do sekundarnog grupisanja jer ispitni niz zavisi samo od matične adrese i rednog broja pokušaja.

== 8. zadatak ==
=== Postavka ===
Precizno objasniti kako se dolazi do složenosti algoritama za sortiranje a) kvadratnom selekcijom b) stablom selekcije i c) spajanjem. U kojem od ovih algoritama se razlikuju najbolji, srednji i najgori slučaj složenosti.

=== Rešenje ===

[[Категорија:АСП2]]
[[Категорија:Рокови]]