ASP1/Jul 2020
Prvi kolokvijum
1. zadatak
Postavka
Data je retka kvadratna matrica dimenzije 5. Navesti dva načina da se prikaže pomoću ulančanih lista.
Rešenje
2. zadatak
Postavka
Napisati pseudokod za osnovne operacije sa stekom implementiranog pomoću ulančanih lista sa zaglavljem, tako da se u konstantnoj složenosti može dobiti maksimalni element. Dozvoljeno je koristiti još jednu listu.
Rešenje
3. zadatak
Postavka
Prebaciti infiksni izraz A*(B-C)*(A-D!!)+F/G+K u postfiksni i popuniti tabelu ispod.
| Operator | Ulazni prioritet | Stek prioritet | Rang |
|---|---|---|---|
| +, - | ? | ? | ? |
| *, / | ? | ? | ? |
| ! | ? | ? | ? |
| ( | ? | ? | ? |
| ) | ? | ? | ? |
Rešenje
4. zadatak
Postavka
Implementirati operacije za dodavanje elemenata na početak i kraj reda implementiranog preko kružnog vektora.
Rešenje
INSERT-BEFORE(Q, value)
INSERT-AFTER(Q, value)
Drugi kolokvijum
1. zadatak
Postavka
- Precizno definisati povezana stabla. Koja nova polja se moraju uvesti u normalno stablo kako bi postalo povezano?
- Napisati pseudokod funkcije koja prima čvor i izbacuje ga iz stabla povezanog po inorder-u ako je poznato da taj čvor nema levog sina.
Rešenje
2. zadatak
Postavka
Napisati pseudokod funkcije koja za svaki čvor u stablu proverava da li je suma vrednosti svih potomaka tog čvora jednaka vrednosti tog čvora za svaki čvor koji ima potomke.
Rešenje
3. zadatak
Postavka
Dinamički Hafman. (?) Uporediti dužinu karaktera sa dinamičkim Hafmanom i bez njega. (??)
Rešenje
4. zadatak
Postavka
- Objasniti postupak konverzije m-arnog stabla u binarno stablo.
- Na sledećem primeru m-arnog stabla prikazati postupak konverzije po koracima. (?)
Rešenje
Treći kolokvijum
1. zadatak
Postavka
Napisati funkciju koja iz datog grafa u matričnoj reprezentaciji i niza čvorova pronalazi sve čvorove grafa nedostižne iz čvorova u datom nizu.
Rešenje
GC(G, n, vars, nvars)
2. zadatak
Postavka
Definisati jako povezane komponente. Prikazati postupak njihovog nalaženja na sledećem grafu i nacrtati redukovani graf.
Rešenje
3. zadatak
Postavka
Naći obuhvatno stablo datog grafa (?) Primovim algoritmom. Da li je obuhvatno stablo jedinstveno? Ako nije, objasniti u kojem koraku se može formirati drugačije obuhvatno stablo.
Rešenje
4. zadatak
Postavka
- Definisati ekscentričnost čvora i središte grafa.
- Napisati pseudokod funkcije koja vraća niz ekscentričnosti svakog čvora grafa iz date matrice najkraćih puteva.
- Napisati pseudokod funkcije koja nalazi središte grafa iz niza iz prethodne tačke.