АСП2/К1 2020 — разлика између измена
(Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_2021.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2020. godine''' održan je 3. novembra. == 1. zadatak == === Postavka === '''(10p)''' Posmatra se tabela celobrojnih ključeva data na slici. Prikazati izgled tabele u svakom koraku prilikom pretrage na skup ključeva {25, 40, 25, 40} metodom transpozicije kao i metodom prebacivanja na početak i u oba slučaja izračunati prosečan bro…) |
м (Замена начина истицања милокода.) |
||
(Нису приказане 3 међуизмене 2 корисника) | |||
Ред 2: | Ред 2: | ||
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_2021.pdf Zadaci na stranici predmeta.] | [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_2021.pdf Zadaci na stranici predmeta.] | ||
'''Prvi kolokvijum 2020. godine''' održan je 3. novembra. | '''Prvi kolokvijum 2020. godine''' održan je 3. novembra 2020. | ||
== 1. zadatak == | == 1. zadatak == | ||
Ред 200: | Ред 200: | ||
[[Датотека:ASP2 K1 2020 Zadatak 4a.svg|thumb|400px|center|Struktura indeksa]] | [[Датотека:ASP2 K1 2020 Zadatak 4a.svg|thumb|400px|center|Struktura indeksa]] | ||
# < | # {{Милокод|<nowiki> | ||
FIND KEY LIST(list, index, size, key) | FIND KEY LIST(list, index, size, key) | ||
int i=0; | int i=0; | ||
Ред 212: | Ред 212: | ||
end_while | end_while | ||
end_for | end_for | ||
</ | </nowiki>}} | ||
</div> | </div> | ||
Ред 222: | Ред 222: | ||
[[Датотека:ASP2 K1 2020 Zadatak 5.png|thumb|400px|center|Početno stanje]] | [[Датотека:ASP2 K1 2020 Zadatak 5.png|thumb|400px|center|Početno stanje]] | ||
=== Rešenje === | === Rešenje === | ||
U stablu se već nalazi ključ 33, tako da on ne treba da se ubacuje. | |||
<gallery> | |||
ASP2 K1 2020 Zadatak 5 korak 1.svg | Nakon umetanja ključa 30. | |||
ASP2 K1 2020 zadatak 5 korak 2.svg | Nakon brisanja ključa 29. | |||
ASP2 K1 2020 Zadatak 5 korak 3.svg | Nakon brisanja ključa 61. | |||
</gallery> | |||
== 6. zadatak == | == 6. zadatak == | ||
Ред 235: | Ред 237: | ||
=== Rešenje === | === Rešenje === | ||
U ovom rešenju su korišćene funkcije inicijalizacije, brisanja i dodavanja u red, kao i funkcija provere da li je red prazan, koje su podrazumevano znanje sa ASP1 i kao takve mogu da se koriste bez posebnog pseudokoda za te operacije. | U ovom rešenju su korišćene funkcije inicijalizacije, brisanja i dodavanja u red, kao i funkcija provere da li je red prazan, koje su podrazumevano znanje sa ASP1 i kao takve mogu da se koriste bez posebnog pseudokoda za te operacije. | ||
< | {{Милокод|<nowiki> | ||
PRINT ALL BST(root) | PRINT ALL BST(root) | ||
Q.insert(root) | Q.insert(root) | ||
Ред 245: | Ред 247: | ||
if(tr.right) Q.insert(tr.right) | if(tr.right) Q.insert(tr.right) | ||
end_while | end_while | ||
</ | </nowiki>}} | ||
< | {{Милокод|<nowiki> | ||
CHECK(root) | CHECK(root) | ||
Q.insert(root, -∞,+∞) | Q.insert(root, -∞,+∞) | ||
Ред 268: | Ред 270: | ||
root.bst=1 | root.bst=1 | ||
return | return | ||
</ | </nowiki>}} | ||
== 7. zadatak == | == 7. zadatak == | ||
Ред 275: | Ред 277: | ||
=== Rešenje === | === Rešenje === | ||
U rešenju se koristi binarno pretraživanje u tabeli nepoznate veličine. | U rešenju se koristi binarno pretraživanje u tabeli nepoznate veličine. | ||
< | {{Милокод|<nowiki> | ||
FIND FIRST POSITIVE(f) | FIND FIRST POSITIVE(f) | ||
int high=1; | int high=1; | ||
Ред 288: | Ред 290: | ||
else low=mid+1; | else low=mid+1; | ||
end_while | end_while | ||
</ | </nowiki>}} | ||
== 8. zadatak == | == 8. zadatak == |
Тренутна верзија на датум 13. септембар 2024. у 02:09
Prvi kolokvijum 2020. godine održan je 3. novembra 2020.
1. zadatak
Postavka
(10p) Posmatra se tabela celobrojnih ključeva data na slici. Prikazati izgled tabele u svakom koraku prilikom pretrage na skup ključeva {25, 40, 25, 40} metodom transpozicije kao i metodom prebacivanja na početak i u oba slučaja izračunati prosečan broj poređenja prilikom pretraživanja.
12 | 7 | 3 | 27 | 25 | 78 | 98 | 21 | 22 | 40 | 51 |
---|
Rešenje
Transpozicija:
12 | 7 | 3 | 25 | 27 | 78 | 98 | 21 | 22 | 40 | 51 |
---|
Broj poređenja u ovom koraku - 5
12 | 7 | 3 | 25 | 27 | 78 | 98 | 21 | 40 | 22 | 51 |
---|
Broj poređenja u ovom koraku - 10
12 | 7 | 25 | 3 | 27 | 78 | 98 | 21 | 40 | 22 | 51 |
---|
Broj poređenja u ovom koraku - 4
12 | 7 | 25 | 3 | 27 | 78 | 98 | 40 | 21 | 22 | 51 |
---|
Broj poređenja u ovom koraku - 9
Prosečan broj poređenja:
Prebacivanje na početak:
25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 40 | 51 |
---|
Broj poređenja u ovom koraku - 5
40 | 25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
---|
Broj poređenja u ovom koraku - 10
25 | 40 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
---|
Broj poređenja u ovom koraku - 2
40 | 25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
---|
Broj poređenja u ovom koraku - 2
Prosečan broj poređenja:
2. zadatak
Postavka
(10p) Ukratko objasniti i ilustrovati primerima slučajeve pronalaženja čvora prethodnika po inorder poretku za zadati čvor u stablu binarnog pretraživanja.
Rešenje
Ukoliko čvor ima levo podstablo, njegov prethodnik je najdešnji potomak njegovog levog sina, a ukoliko nema levo podstablo, njegov prethodnik je njegov najniži predak čiji je desni sin takođe njegov predak. U primeru ispod, prethodnik od 3 je 1, a prethodnik od 6 je 5.
3. zadatak
Postavka
(15p) U AVL stablo sa slike se redom umeću ključevi 44, 72, 19, 22, 21, 5 i 1, nakon čega se uklanjaju ključevi 23 i 39. Prikazati stanja stabla nakon svake promene.[1]
Rešenje
4. zadatak
Postavka
(15p) Neka je data velika, uređena jednostruko ulančana lista list koju treba pretražiti na zadati ključ key. Kao pomoćna struktura, raspoloživ je indeks index veličine size.
- (5p) Objasniti i nacrtati strukturu indeksa i način povezivanja sa listom koja se pretražuje.
- (10p) Napisati u pseudokodu implementaciju funkcije za sekvencijalnu pretragu liste list uz korišćenje indeksa index na ključ key.
Rešenje
- Struktura index predstavlja niz čvorova koji sadrže informaciono polje sa vrednošću pronađenih ključeva i polje-pokazivač na taj pronađen ključ. Struktura index se čuva uređenom.
- FIND KEY LIST(list, index, size, key)
int i=0; for(i<size) if(key<index[i].info) Node poc = index[i]; if(key>=index[i].info) break; while(poc!=nil) if(key==poc.info) return poc; if(key>poc.info) return nil; poc=poc.next end_while end_for
5. zadatak
Postavka
(10p) Neka se u dato samopodešavajuće stablo ubacuje ključ 30, nakon čega se brišu ključevi 29 i 61, i na kraju se ubacuje ključ 33. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju.
Rešenje
U stablu se već nalazi ključ 33, tako da on ne treba da se ubacuje.
6. zadatak
Postavka
(15p) Napisati u pseudokodu implementaciju funkcije koja u datom binarnom stablu na čiji koren ukazuje pokazivač root pronalazi i ispisuje adrese korenova svih podstabala koja zadovoljavaju osobine stabla binarnog pretraživanja. Dozvoljeno je uvoditi dodatna polja u čvor stabla koja mogu olakšati implementaciju funkcije.
Rešenje
U ovom rešenju su korišćene funkcije inicijalizacije, brisanja i dodavanja u red, kao i funkcija provere da li je red prazan, koje su podrazumevano znanje sa ASP1 i kao takve mogu da se koriste bez posebnog pseudokoda za te operacije.
PRINT ALL BST(root) Q.insert(root) while(!Q.empty()) tr = Q.delete CHECK(tr) if(tr.bst) print(tr) if(tr.left) Q.insert(tr.left) if(tr.right) Q.insert(tr.right) end_while
CHECK(root) Q.insert(root, -∞,+∞) while(!Q.empty()) {tr,min.max} = Q.delete if(tr.left) if(tr.left.info < min || tr.left.info > tr.info) root.bst = 0 return end_if Q.insert(tr.left,min,tr.info) end_if if(tr.right) if(tr.right.info < key || tr.right.info > tr.info) root.bst = 0 return end_if end_if end_while root.bst=1 return
7. zadatak
Postavka
(15p) Neka se posmatra jedna strogo monotono rastuća funkcija f(x). Na primer, ili . Korišćenjem strategije binarnog pretraživanja, napisati u pseudokodu iterativnu implementaciju funkcije koja pronalazi vrednost n za koju funkcija f(x) postaje pozitivna prvi put, ukoliko važi da je x ≥ 0. Kratko objasniti postupak.
Rešenje
U rešenju se koristi binarno pretraživanje u tabeli nepoznate veličine.
FIND FIRST POSITIVE(f) int high=1; while(f(high)<0) high *= 2; end_while int low = high/2; while(low<=high) mid = (high+low)/2; if(f(mid)>=0 && f(mid-1)<0) return mid; if(f(mid)>0) high = mid-1; else low=mid+1; end_while
8. zadatak
Postavka
(10p) Analiza performansi stabla binarnog pretraživanja.
- (5p) Formalno definisati i objasniti prosečan broj poređenja Sn prilikom uspešnog pretraživanja i prosečan broj poređenja Un prilikom neuspešnog pretraživanja u stablu binarnog pretraživanja koje je nastalo umetanjem n čvorova u proizvoljnom poretku.
- (5p) Izvesti i kratko objasniti vezu između Sn i Un koji su definisani pod a). Odgovor ilustrovati slikom.
Rešenje
- Sn možemo predstaviti kao , jer ima za 1 više poređenja nego čvorova, a Un možemo predstaviti kao .
Napomene
- ↑ Prepisivač ovog roka je zaboravio kako se postupno radi umetanje i brisanje, tako da su dostupna rešenja samo posle svih umetanja i posle svih brisanja (u prevodu nisam radio postupno)