АСП1/Август 2021
- Овај рок није решен. Помозите SI Wiki тако што ћете га решити.
Ovaj članak je rekreacija avgustovskog roka koji nije objavljen.
1. zadatak
Postavka
Data je retka matrica koja je prikazana na slici. (Data je matrica npr. 5*6 sa 5 ili 6 random nenultih elemenata). a) Nacrtati izgled delova memorije u kojima se čuva ova retka matrica, ako se primenjuje Compressed Sparse Row način čuvanja. b) Napisati funkciju u pseudokodu koja na osnovu sačuvane Compressed Sparse Row reprezentacije matrice M i unetog broja i štampa sve nenulte elemente i-te vrste.
Rešenje
2. zadatak
Postavka
Navedite načine reprezentacije grafova i njihove prednosti i mane.
Rešenje
potrebno je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika
3. zadatak
Postavka
Zadato je binarno stablo S i date su adrese dva čvora x i y. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.
Rešenje
4. zadatak
Postavka
Potpuno formalno izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti.
Rešenje
PE = PI + 2n, gde je n broj čvorova u stablu izvođenje indukcijom, kao u knjizi/na predavanju
5. zadatak
Postavka
Potrebno je realizovati aplikaciju za obradu slika. Korisniku je potrebno da za uneti set slika i unet set operacija omogućiti da se sve operacije izvrše nad svim unetim slikama. Navesti koje strukture je pogodno koristiti za čuvanje seta slika i seta operacija i objasniti zašto. Napisati fuknciju u pesudokodu koja obrađuje uneti set slika unetim setom operacija, u skladu sa odabranim strukturama podataka.
Rešenje
//Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.
OBRADI_SLIKE(slike, operacije)
s = slike.head;
o = operacije.head;
while (s != NULL)
while (o != NULL)
s.info = o.operacija(s.info);6. zadatak
Postavka
Huffman-ov algoritam: Dat јe tekst sa 6 slova dužine 21 slovo. Odrediti izgled stabla dobijenog statičkim Huffman-om za ovaj tekst i uporediti prosečan broj bitova za čuvanje ovog teksta, kao i jednog slova u slučaju da se čuva podrazumevano i na osnovu ovog Huffman stabla. Frekvenciju slova zaključiti iz teksta.
Rešenje
Najobičniji statički Huffman za zadatim frekvencijama.
7. zadatak
Postavka
Dat je grad koji je mnodelovan usmerenim grafom, tako što su čvorovi lokacije u gradu (pekara, apoteka, biblioteka itd), a težine grana između čvorova vreme u minutima koje je potrebno da se peške dođe od izvorišne do odredišne lokacije. Dete želi da stigne od škole (čvor X) do kuće (čvor Y) najbrže moguće. Međutim, postoji opasan deo grada (čvor Z), koji nije bezbedan za decu i koji ona treba da izbegavaju. Napisati funkciju u pseudokodu koja na osnovu zadatog grafa G (nije data reprezentacija, nego treba apstraktno da se piše), zadatih lokacija kuće i škole, Y i X, i opasnog dela grada Z, pronalazi najkraće vreme koje je detetu potrebno od škole do kuće.
Rešenje
Zadatak se rešava implementacijom Dijkstrinog algortima, tako što kada se u uzimanju čvorova redom po težinskoj udaljenosti od početnog dođe do "opasnog" čvora z, za njega se upise tezina beskonačno i ta petlja preskoči sa continue. Na kraju se samo proveri dostižnost ciljnog čvora.
8. zadatak
Postavka
Dat je graf na slici (ima nekih 7-8 čvorova). Za dati graf uraditi topološko sortiranje i prikazati graf dobijen tako.
Rešenje
9. zadatak
Postavka
a) Detaljno opisati postupak za pronalaženje jako povezanih komponenti u grafu. b) Za graf sa slike (nekih 7-8 čvorova) po koracima primeniti algoritam za pronalaženje jako povezanih komponenti i rezultujući graf.
Rešenje
10. zadatak
Postavka
Potrebno je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100. a) Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uprediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosi elementa skupu za ove dve reprezentacije. b) Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).
Rešenje
Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element X u skupu, u polje S[X] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).