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

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

2024-09-13T00:09:13Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 43:		Ред 43:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	CALC(root)		CALC(root)
	if root = nil then		if root = nil then
Ред 50:		Ред 50:
	min, max = CALC_R(root)		min, max = CALC_R(root)
	return max - min		return max - min
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	CALC R(root)		CALC R(root)
	min = +∞		min = +∞
Ред 72:		Ред 72:
	end_for		end_for
	return max, min		return max, min
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 79:		Ред 79:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	B-DELETE-NO-BORROW(root, m, node, key)		B-DELETE-NO-BORROW(root, m, node, key)
	child_index = 0		child_index = 0
Ред 122:		Ред 122:
	end_if		end_if
	num(parent) = num(parent) - 1		num(parent) = num(parent) - 1
	</~~syntaxhighlight~~>		</nowiki>}}

	== 5. zadatak ==		== 5. zadatak ==
Ред 207:		Ред 207:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	COUNT KEYS(root, format)		COUNT KEYS(root, format)
	len = STRING_LENGTH(format)		len = STRING_LENGTH(format)
Ред 232:		Ред 232:
	end_if		end_if
	return count		return count
	</~~syntaxhighlight~~>		</nowiki>}}

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

KockaAdmiralac: PNG u SVG

2022-02-13T21:21:58Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:21
Ред 10:		Ред 10:

	=== Rešenje ===		=== Rešenje ===
	[[Датотека:ASP2 K2 2018 zadatak 1 stablo.~~png~~\|thumb\|Ekvivalentno crveno-crno stablo u rešenju 1. zadatka.]]		[[Датотека:ASP2 K2 2018 zadatak 1 stablo.svg\|thumb\|Ekvivalentno crveno-crno stablo u rešenju 1. zadatka.]]
	Ključ 17 dolazi između ključeva 15 i 20. Pošto je taj čvor pun, crni ključ 15 ide u roditeljski čvor, ključ 1 dolazi u sredinu i postaje crn, ključ 20 se odvaja u desni čvor i postaje crn a ključ 17 završava kao crveni ključ levo od ključa 20.		Ključ 17 dolazi između ključeva 15 i 20. Pošto je taj čvor pun, crni ključ 15 ide u roditeljski čvor, ključ 1 dolazi u sredinu i postaje crn, ključ 20 se odvaja u desni čvor i postaje crn a ključ 17 završava kao crveni ključ levo od ključa 20.
	[15\|23\|45]		[15\|23\|45]

KockaAdmiralac: Ne može B+ list ovog stabla da ima 1 ključ

2021-12-10T20:39:39Z

Ne može B+ list ovog stabla da ima 1 ključ

← Старија измена		Верзија на датум 10. децембар 2021. у 22:39
Ред 33:		Ред 33:
	[1\|2]->[3\|4]->[5\|6]		[1\|2]->[3\|4]->[5\|6]
	2 je prosečan broj pristupa i pri uspešnoj i pri neuspešnoj pretrazi.		2 je prosečan broj pristupa i pri uspešnoj i pri neuspešnoj pretrazi.
	(3\|6\| )		(3\|5\| )
	/ \| \		/ \| \
	[1\|2\|3]->[4\|5\|6]->[7\| \| ]		[1\|2\|3]->[4\|5\| ]->[6\|7\| ]
	Pretpostavljajući da se ovde radi o broju ključeva u listovima (pošto se ključevi iz unutrašnjih čvorova dupliciraju u listovima), prosečan broj pristupa je ponovo 2. Sve uspešne pretrage, kao i neuspešne, moraju završiti u listovima jer se samo u listovima nalaze pokazivači ka traženim strukturama, a visina ovako napravljenog stabla je 1.		Pretpostavljajući da se ovde radi o broju ključeva u listovima (pošto se ključevi iz unutrašnjih čvorova dupliciraju u listovima), prosečan broj pristupa je ponovo 2. Sve uspešne pretrage, kao i neuspešne, moraju završiti u listovima jer se samo u listovima nalaze pokazivači ka traženim strukturama, a visina ovako napravljenog stabla je 1.

Etfsibg: /* Rešenje */

2021-12-07T13:22:34Z

Rešenje

← Старија измена		Верзија на датум 7. децембар 2021. у 15:22
Ред 103:		Ред 103:
	right_node = pointers(parent)[child_index+1]		right_node = pointers(parent)[child_index+1]
	offset = 0		offset = 0
	for i = 1 to num(node) ~~then~~		for i = 1 to num(node) do
	if keys(node)[i] = key then		if keys(node)[i] = key then
	offset = 1		offset = 1

Fedja: ubacuje se 25 a ne 20 u stablo

2021-01-27T17:22:52Z

ubacuje se 25 a ne 20 u stablo

← Старија измена		Верзија на датум 27. јануар 2021. у 19:22
Ред 15:		Ред 15:
	/ \| \		/ \| \
	[ \| 1\| ] [17\|20\| ] [28\|36\| ] [ \|72\| ]		[ \| 1\| ] [17\|20\| ] [28\|36\| ] [ \|72\| ]
	Ključ 20 dolazi levo od ključa 28.		Ključ 25 dolazi levo od ključa 28.
	[15\|23\|45]		[15\|23\|45]
	/ \| \| \		/ \| \| \
	[ \| 1\| ] [17\|20\| ] [20\|28\|36] [ \|72\| ]		[ \| 1\| ] [17\|20\| ] [25\|28\|36] [ \|72\| ]

	== 2. zadatak ==		== 2. zadatak ==

KockaAdmiralac: Usklađivanje pisma i ispravke COUNT KEYS

2021-01-18T14:23:42Z

Usklađivanje pisma i ispravke COUNT KEYS

← Старија измена		Верзија на датум 18. јануар 2021. у 16:23
Ред 181:		Ред 181:
	/ / \| \ \		/ / \| \ \
	[ 1\| 2\| ] [ 4\| 5\| ] [ 7\| 8\| ] [10\|11\| ] [13\|14\| ]		[ 1\| 2\| ] [ 4\| 5\| ] [ 7\| 8\| ] [10\|11\| ] [13\|14\| ]
	~~При брисању кључа~~ 4, ~~због немогућности позајмице~~, ~~спајање три чвора у два~~.		Pri brisanju ključa 4, zbog nemogućnosti pozajmice, spajanje tri čvora u dva.
	[ 5\| 9\| 12 \|]		[ 5\| 9\| 12 \|]
	/ / \| \		/ / \| \
	[ 1\| 2\| 3 ] [ 6\| 7\| 8 ] [ 10\|11\| ] [13\|14\| ]		[ 1\| 2\| 3 ] [ 6\| 7\| 8 ] [ 10\|11\| ] [13\|14\| ]
	~~При брисању кључа~~ 11 ~~могућа је позајмица~~, ~~али од левог брата~~.		Pri brisanju ključa 11 moguća je pozajmica, ali od levog brata.
	[ 5\| 8\| 12 \|]		[ 5\| 8\| 12 \|]
	/ / \| \		/ / \| \
	[ 1\| 2\| 3 ] [ 6\| 7\|] [ 9 \|10\| ] [13\|14\| ]		[ 1\| 2\| 3 ] [ 6\| 7\|] [ 9 \|10\| ] [13\|14\| ]
	~~При брисању кључа~~ 9 ~~могућа је позајмица али од брата са удаљеношћу два~~.		Pri brisanju ključa 9 moguća je pozajmica ali od brata sa udaljenošću dva.
	[ 3\| 7\| 12 \|]		[ 3\| 7\| 12 \|]
	/ / \| \		/ / \| \
Ред 211:		Ред 211:
	len = STRING_LENGTH(format)		len = STRING_LENGTH(format)
	if len = 0 then		if len = 0 then
	return 0		if key(node) = EOK then
			return 1
			else
			return 0
			end_if
	end_if		end_if
	count = 0		count = 0
Ред 219:		Ред 223:
	if (key(node) = format[1]) or (format[1] = '.') then		if (key(node) = format[1]) or (format[1] = '.') then
	count = count + COUNT_KEYS(node, format)		count = count + COUNT_KEYS(node, format)
	~~else~~
	~~count = count + COUNT_KEYS(root, format + 2)~~
	end_if		end_if
	else if (key(node) = format[1]) or (format[1] = '.') then		else if (key(node) = format[1]) or (format[1] = '.') then
Ред 226:		Ред 228:
	end_if		end_if
	end_for		end_for
			if (len > 1) and (format[2] = '*') then
			count = count + COUNT_KEYS(root, format + 2)
			end_if
	return count		return count
	</syntaxhighlight>		</syntaxhighlight>
Ред 247:		Ред 252:
	<div class="abc-list">		<div class="abc-list">
	# Minimalna savršena heš funkcija je heš funkcija koja preslikava ''n'' ključeva u ''n'' ulaza tabele bez kolizije.		# Minimalna savršena heš funkcija je heš funkcija koja preslikava ''n'' ključeva u ''n'' ulaza tabele bez kolizije.
	# Jedna moguća savršena heš funkcija je <math>h(K) = \left\lfloor\frac{K}{2}\right\rfloor mod 5</math>. Kad sortiramo ključeve, dobijamo redosled 23, 28, 54, 57. Možemo primetiti da su oni svi različiti po modulu 10, ali pošto tabela ima 5 ulaza možemo prvo podeliti ključeve sa dva pa uzeti vrednost po modulu 5. Tabela nakon primene ove heš funkcije je data ispod.		# Jedna moguća savršena heš funkcija je <math>h(K) = \left\lfloor\frac{K}{2}\right\rfloor \mod 5</math>. Kad sortiramo ključeve, dobijamo redosled 23, 28, 54, 57. Možemo primetiti da su oni svi različiti po modulu 10, ali pošto tabela ima 5 ulaza možemo prvo podeliti ključeve sa dva pa uzeti vrednost po modulu 5. Tabela nakon primene ove heš funkcije je data ispod.
	</div>		</div>
	{\| class="wikitable"		{\| class="wikitable"

Ivan Pešić: 7. Задатак k->n у последњој формули јер има n - 1 елемената

2021-01-03T22:07:55Z

7. Задатак k->n у последњој формули јер има n - 1 елемената

← Старија измена		Верзија на датум 4. јануар 2021. у 00:07
Ред 234:		Ред 234:

	=== Rešenje ===		=== Rešenje ===
	Nakon ubacivanja ključa ''nk'' dobiće se degenerisano stablo udesno, tj. jedino najdesniji pokazivači u svakom unutrašnjem čvoru će pokazivati na sledeći list, i većina ključeva će biti popunjena, tako da će visina stabla biti <math>\left\lceil\frac{n}{m - 1}\right\rceil</math> a u listu će ostati <math>(m - 1) - (n \bmod (m - 1))</math> slobodnih mesta. Nakon ubacivanja svih ključeva stablo će u listovima krenuti da raste ulevo iz listova, tako da će visina porasti na ukupno: <math>h = \left\lceil\frac{n}{m - 1}\right\rceil + \left\lceil\frac{k - 1 - (m - 1) + (n \bmod (m - 1))}{m - 1}\right\rceil</math>.		Nakon ubacivanja ključa ''nk'' dobiće se degenerisano stablo udesno, tj. jedino najdesniji pokazivači u svakom unutrašnjem čvoru će pokazivati na sledeći list, i većina ključeva će biti popunjena, tako da će visina stabla biti <math>\left\lceil\frac{n}{m - 1}\right\rceil</math> a u listu će ostati <math>(m - 1) - (n \bmod (m - 1))</math> slobodnih mesta. Nakon ubacivanja svih ključeva stablo će u listovima krenuti da raste ulevo iz listova, tako da će visina porasti na ukupno: <math>h = \left\lceil\frac{n}{m - 1}\right\rceil + \left\lceil\frac{n - 1 - (m - 1) + (n \bmod (m - 1))}{m - 1}\right\rceil</math>.

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

KockaAdmiralac: Znam da je ovo obrazloženje loše

2020-12-14T00:06:22Z

Znam da je ovo obrazloženje loše

← Старија измена		Верзија на датум 14. децембар 2020. у 02:06
Ред 245:		Ред 245:

	=== Rešenje ===		=== Rešenje ===
			<div class="abc-list">
			# Minimalna savršena heš funkcija je heš funkcija koja preslikava ''n'' ključeva u ''n'' ulaza tabele bez kolizije.
			# Jedna moguća savršena heš funkcija je <math>h(K) = \left\lfloor\frac{K}{2}\right\rfloor mod 5</math>. Kad sortiramo ključeve, dobijamo redosled 23, 28, 54, 57. Možemo primetiti da su oni svi različiti po modulu 10, ali pošto tabela ima 5 ulaza možemo prvo podeliti ključeve sa dva pa uzeti vrednost po modulu 5. Tabela nakon primene ove heš funkcije je data ispod.
			</div>
			{\| class="wikitable"
			\|+ Tabela nakon primene heš funkcije
			! 0 !! 1 !! 2 !! 3 !! 4
			\|-
			\| 91 \|\| 23 \|\| 54 \|\| 57 \|\| 28
			\|}

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

IvnSvc: Није било урађено брисање 4,11 и 9 после додавања 1-14.

2020-12-10T20:28:33Z

Није било урађено брисање 4,11 и 9 после додавања 1-14.

@@ Ред 181: / Ред 181: @@
              /         /    |    \        \
   [ 1| 2|  ] [ 4| 5|  ] [ 7| 8|  ] [10|11|  ] [13|14|  ]
 == 6. zadatak ==

KockaAdmiralac: Isto kao za prošli rok

2020-11-21T21:40:23Z

Isto kao za prošli rok

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

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K2_1819.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
U 2-3-4 stablo sa slike ubaciti ključeve 17 i 25 i prikazati ekvivalentno crveno-crno stablo.
[ |23|45]
/ | \
[ 1|15|20] [28|36| ] [ |72| ]

=== Rešenje ===
[[Датотека:ASP2 K2 2018 zadatak 1 stablo.png|thumb|Ekvivalentno crveno-crno stablo u rešenju 1. zadatka.]]
Ključ 17 dolazi između ključeva 15 i 20. Pošto je taj čvor pun, crni ključ 15 ide u roditeljski čvor, ključ 1 dolazi u sredinu i postaje crn, ključ 20 se odvaja u desni čvor i postaje crn a ključ 17 završava kao crveni ključ levo od ključa 20.
[15|23|45]
/ | \
[ | 1| ] [17|20| ] [28|36| ] [ |72| ]
Ključ 20 dolazi levo od ključa 28.
[15|23|45]
/ | | \
[ | 1| ] [17|20| ] [20|28|36] [ |72| ]

== 2. zadatak ==
=== Postavka ===
B+-stabla
<div class="abc-list">
# Prikazati maksimalno popunjeno B+-stablo reda ''m'' = 3 i visine ''h'' = 1. Odrediti za ovo stablo prosečan broj pristupa prilikom uspešne i neuspešne pretrage.
# Posmatra se B+-stablo reda 4 koje sadrži 7 ključeva. Odrediti za ovo stablo srednji broj pristupa prilikom uspešne i neuspešne pretrage i obrazložiti odgovor.
</div>

=== Rešenje ===
(2|4)
/ | \
[1|2]->[3|4]->[5|6]
2 je prosečan broj pristupa i pri uspešnoj i pri neuspešnoj pretrazi.
(3|6| )
/ | \
[1|2|3]->[4|5|6]->[7| | ]
Pretpostavljajući da se ovde radi o broju ključeva u listovima (pošto se ključevi iz unutrašnjih čvorova dupliciraju u listovima), prosečan broj pristupa je ponovo 2. Sve uspešne pretrage, kao i neuspešne, moraju završiti u listovima jer se samo u listovima nalaze pokazivači ka traženim strukturama, a visina ovako napravljenog stabla je 1.

== 3. zadatak ==
=== Postavka ===
Posmatra se ''trie'' stablo čiji su ključevi znakovni nizovi koji sadrže cifre u brojnom sistemu sa osnovom 10. Napisati u pseudokodu funkciju koja za dato stablo na čiji koren pokazuje pokazivač ''root'' računa razliku najvećeg i najmanjeg tako predstavljenog broja.

=== Rešenje ===
<syntaxhighlight lang="milo">
CALC(root)
if root = nil then
return 0
end_if
min, max = CALC_R(root)
return max - min
</syntaxhighlight>
<syntaxhighlight lang="milo">
CALC R(root)
min = +∞
max = -∞
for i = 0 to 9 do
field = fields(root)[i]
if field ≠ nil then
if is_leaf(field) then
f_max = f_min = value(field)
else
f_max, f_min = CALC_R(field)
end_if
if f_max > max then
max = f_max
end_if
if f_min < min then
min = f_min
end_if
end_if
end_for
return max, min
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Posmatra se B stablo reda m u kojem su svi listovi minimalno popunjeni, a njihovi roditelji su popunjeni iznad minimuma. Iz takvog stabla se briše ključ key iz lista sa adresom node. Napisati iterativnu funkciju u pseudokodu za datu situaciju brisanja. Smatrati da u čvoru postoji pokazivač na roditelja i podatak o broju ključeva smeštenih u njemu.

=== Rešenje ===
<syntaxhighlight lang="milo">
B-DELETE-NO-BORROW(root, m, node, key)
child_index = 0
parent = parent(node)
for i = 0 to num(parent) do
if pointers(parent)[i] = node then
child_index = i
break
end_if
end_for
if child_index = num(parent) then
left_node = pointers(parent)[child_index-1]
num(left_node) = num(left_node) + 1
keys(left_node)[num(left_node)] = keys(parent)[child_index]
for i = 1 to num(node) do
if keys(node)[i] ≠ key then
num(left_node) = num(left_node) + 1
keys(left_node)[num(left_node)] = keys(node)[i]
end_if
end_for
FREENODE(node)
else
right_node = pointers(parent)[child_index+1]
offset = 0
for i = 1 to num(node) then
if keys(node)[i] = key then
offset = 1
else
keys(node)[i-offset] = keys(node)[i]
end_if
end_for
keys(node)[num(node)] = keys(parent)[child_index+1]
for i = 1 to num(right_node) do
num(node) = num(node) + 1
keys(node)[num(node)] = keys(right_node)[i]
end_for
for i = child_index to num(parent)-1 do
keys(parent)[i+1] = keys(parent)[i+2]
pointers(parent)[i] = pointers(parent)[i+1]
end_for
FREENODE(right_node)
end_if
num(parent) = num(parent) - 1
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
U B* stablo reda 4 se umeću ključevi od 1 do 14. Nakon toga se redom brišu ključevi 4, 11 i 9. Nacrtati izgled stabla nakon svake izmene.

=== Rešenje ===
* Red stabla: <math>m = 4</math>
* Minimalni broj ključeva u ne-korenskom čvoru: <math>\left\lceil\frac{2m - 1}{3}\right\rceil - 1 = 2</math>
* Maksimalni broj ključeva u korenu: <math>2 \left\lfloor\frac{2m - 2}{3}\right\rfloor = 4</math>
* Raspodela ključeva pri prelomu: 2-2-2
Umećemo ključ 1 u prazno stablo.
[ 1| | | ]
Umećemo ključ 2.
[ 1| 2| | ]
Umećemo ključ 3.
[ 1| 2| 3| ]
Umećemo ključ 4.
[ 1| 2| 3| 4]
Pri umetanju ključa 5 dolazi do prelamanja čvora, tako da ključevi 1 i 2 idu u levi a 4 i 5 u desni čvor.
[ 3| | | ]
| |
[ 1| 2| ] [ 4| 5| ]
Umećemo ključ 6.
[ 3| | | ]
| |
[ 1| 2| ] [ 4| 5| 6]
Pri umetanju ključa 7 desni čvor se prepunjuje, pa se dešava prelivanje u levi čvor. Ključ 3 iz roditeljskog čvora silazi u levi a ključ 4 iz desnog ide u roditeljski.
[ 4| | | ]
| |
[ 1| 2| 3] [ 5| 6| 7]
Pri umetanju ključa 8 desni čvor se ponovo prepunjuje, pa se dešava prelamanje. Ključevi 1 i 2 ostaju u levom čvoru, ključ 3 ide u roditeljski čvor, 4 i 5 dolaze u novi, srednji čvor, 6 ide u roditeljski čvor a 7 i 8 ostaju u desnom čvoru.
[ 3| 6| | ]
/ | \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| ]
Umećemo ključ 9.
[ 3| 6| | ]
/ | \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| 9]
Pri umetanju ključa 10 dešava se prelivanje iz desnog u srednji čvor.
[ 3| 7| | ]
/ | \
[ 1| 2| ] [ 4| 5| 6] [ 8| 9|10]
Pri umetanju ključa 11 dešava se prelamanje.
[ 3| 6| 9| ]
/ | \ \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| ] [10|11| ]
Umećemo ključ 12.
[ 3| 6| 9| ]
/ | \ \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| ] [10|11|12]
Pri umetanju ključa 13 dešava se prelivanje.
[ 3| 6|10| ]
/ | \ \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| 9] [11|12|13]
Pri umetanju ključa 14 dešava se prelamanje.
[ 3| 6| 9|12]
/ / | \ \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| ] [10|11| ] [13|14| ]

== 6. zadatak ==
=== Postavka ===
Dato je digitalno stablo formirano od nekog skupa ključeva tipa znakovnih nizova. Implementirati funkciju COUNT_KEYS koja pronalazi broj ključeva u stablu koji odgovaraju zadatom formatu znakovnog niza. Pokazivač na koren stabla i zadati format su prosleđeni kao parametri funkcije. Format znakovnog niza pored cifara i slova može sadržati i simbole koji imaju specijano značenje. Specijalni simboli su tačka (.) koja menja bilo koji znak niza i zvezda (*) koja predstavlja ponavljanje nekog znaka niza 0 ili više puta. Smatrati da se zvezda odnosi na prvi znak koji joj prethodi.

Primer:

skup ključeva u stablu: abccc4a, ab3a, aacda

format: abc*.a

rezultat: 2

=== Rešenje ===
<syntaxhighlight lang="milo">
COUNT KEYS(root, format)
len = STRING_LENGTH(format)
if len = 0 then
return 0
end_if
count = 0
for i = 1 to num(root) do
node = pointers(root)[i]
if (len > 1) and (format[2] = '*') then
if (key(node) = format[1]) or (format[1] = '.') then
count = count + COUNT_KEYS(node, format)
else
count = count + COUNT_KEYS(root, format + 2)
end_if
else if (key(node) = format[1]) or (format[1] = '.') then
count = count + COUNT_KEYS(node, format + 1)
end_if
end_for
return count
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Neka se u ''top-down'' stablo ''m''-arnog pretraživanja redom ubacuju ključevi ''k'', 2''k'', 3''k'', …, ''nk'', ''nk'' – 1, ''nk'' – 2, ''nk'' – 3, …, ''n''(''k'' – 1) +1. Nacrtati izgled stabla i odrediti visinu. Pretpostaviti da su ''n'' i ''k'' mnogo veći od ''m''.

=== Rešenje ===
Nakon ubacivanja ključa ''nk'' dobiće se degenerisano stablo udesno, tj. jedino najdesniji pokazivači u svakom unutrašnjem čvoru će pokazivati na sledeći list, i većina ključeva će biti popunjena, tako da će visina stabla biti <math>\left\lceil\frac{n}{m - 1}\right\rceil</math> a u listu će ostati <math>(m - 1) - (n \bmod (m - 1))</math> slobodnih mesta. Nakon ubacivanja svih ključeva stablo će u listovima krenuti da raste ulevo iz listova, tako da će visina porasti na ukupno: <math>h = \left\lceil\frac{n}{m - 1}\right\rceil + \left\lceil\frac{k - 1 - (m - 1) + (n \bmod (m - 1))}{m - 1}\right\rceil</math>.

== 8. zadatak ==
=== Postavka ===
Heširanje.
<div class="abc-list">
# Šta je minimalna savršena heš funkcija?
# Za ključeve 54, 91, 57, 23 i 28 naći što jednostavniju minimalnu savršenu heš funkciju i ispisati je. Obrazložiti odgovor i nacrtati heš tabelu sa umetnutim ključevima.
</div>

=== Rešenje ===

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