АСП1/Септембар 2020
- Овај рок није решен. Помозите SI Wiki тако што ћете га решити.
Ovaj članak je rekreacija septembarskog roka koji nije objavljen.
1. zadatak
Postavka
Transformisati izraz u infiksnom obliku (?) u ekvivalentni izraz u postfiksnoj formi. Tabelu prioriteta operatora dopuniti odgovarajućim vrednostima, pri čemu treba usvojiti standardne prioritete i grupisanje za operacije +,-,* i /. Transformaciju izraza prikazati po koracima. (Nedostaje izraz)
Rešenje
2. zadatak
Postavka
Navedite načine reprezentacije grafova i njihove prednosti i mane.
Rešenje
3. zadatak
Postavka
Napisati funkciju kojoj se prosleđuje koren stabla i broj k, a funkcija vraća čvorove u čijim podstablima se nalazi tačno k listova.
Rešenje
4. zadatak
Postavka
Izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti. Ilustratovati odgovor.
Rešenje
5. zadatak
Postavka
Dat je stek S[1:N] koji raste od viših ka nižim adresama. Pokazivač top[S] pokazuje na prvu slobodnu lokaciju. Koja od 3 naredne funkcije je ispravna funkcija POP(S)? (Nedostaju funkcije)
Rešenje
6. zadatak
Postavka
Huffman-ov algoritam: Dati su simboli i verovatnoća njihovog pojavljivanja. Kako su simboli kodirani nakon Huffman-ovog algoritma? Koja je prosečna dužina jednog koda?
Rešenje
7. zadatak
Postavka
Maša ima veliku biblioteku knjiga. Za neke je vise zainteresovana, a za neke manje. U školi ima obaveznu literaturu koju mora da pročita da bi mogla da diskutuje o lektiri na času. Modelovati Mašin način biranja knjige koje će čitati. Napisati funkciju dodavanja knjige u biblioteku. (Fale još 2 funkcije koje se traže)
Rešenje
8. zadatak
Postavka
Data je strogo donje trougaona matrica M[1:N,1:N] linearizovana po vrstama. Koliko maksimalno nenultih elemenata može da se nađe u matrici i obrazložiti odgovor? Izvesti formulu za opšti član matrice. Napisati funkciju dohvatanja elemenata iz matrice.
Rešenje
9. zadatak
Postavka
Data je matrična reprezentacija usmerenog, težinskog grafa. Uz pomoć algoritma za topološko sortiranje napisati funkciju koja proverava da li je graf cikličan.
Rešenje
10. zadatak
Postavka
Dijkstra-in algoritam: Dat je težinski neusmereni graf na slici. (Nedostaje slika). Uz pomoć Dijsktrinog algoritma naći najkraća rastojanja između početnog čvora M i svih ostalih čvorova.