Algoritmi i strukture podataka – I kolokvijum (NE ZABORAVITE DA OKRENETE STRANU!!!)
1. Vreme izvršavanja T(n) nekog algoritma zadovoljava za n>1 rekurentnu relaciju T(n)= 3*T([n/4]) + n. Odredite asimptotsko ponašanje (ma kojom metodom) ako T(1)=1 .
RESENJE:
Teorema: Asimpototsko ponašanje niza T(n), rešenja difrencne jednačine
T(n)=a T(n/b) + c nk, a, b, c, k >=0, b !=0 i zadato je T(1) dato je sa:
T(n)= O (n log b a ) za a > b k
T(n)= O (n k log n ) za a = b k
T(n)= O (n k ) za a < b k
c=1, k=1, b=4, a=3, 3 < 4 => T(n)=O(n)
2. Na dati niz 1,4,3,7,6,5,8,2 primeniti algoritam brzog sortiranja (quicksort). Rešenje prikazati stanjem niza posle svakog koraka algoritma. Dovoljno je u svakoj vrsti prikazati samo brojeve sa kojima se trenutno radi.
RESENJE:
1 4 3 7 6 5 8 2 pivot: 6
1 4 3 7 6 5 8 2 trampa: 7,2
1 4 3 2 6 5 8 7
1 4 3 2 5 6 8 7
1 4 3 2 5 6 8 7 pivot: 3, 8
1 2 3 4 5 6 7 8, trampa: 4,2 8,7
KRAJ
4. Konstruisati algoritam ubaci(Q,x) koji ubacuje element x u prioritetni red Q. Kolika je vremenska složenost algoritama ako se prioritetni red realizuje implicitno predstavljenim binarnim hipom? Smatrati da je u hipu ključ svakog cvora manji od ključeva sinova.
typedef struct pq_elem { /* element prioritetnog reda */
int key; /* ključ za postavljanje prioriteta */
void *val; /* vrednost elementa (bilo šta) */
} elemT;
typedef struct pq {
int kapacitet; /* kapacitet prioritetnog reda*/
int N; /* broj umetnutih elemenata */
elemT *elementi; /* niz elemenata reda */
} PQueue, *PQUEUE;
Ako želimo dodati element u prioritetni red možemo ga dodati na kraj niza. To je ekvivalentno dodavanju krajnjeg desnog lista u stablu. Ta operacija ima za
posledicu da se N uveća za jedan, ali i da možda stablo ne zadovoljava pravilo hipa. Da bi se zadovoljilo pravilo hipa koristi se postupak opisan u sledećem algoritmu:
Algoritam: Umetanje
1. Element iza krajnjeg elementa niza se tretira kao prazan (to je sledeći krajnji desni list stabla). Podrazumeva se da je kapacitet niza veći od broja elemenata u nizu.
2. Ako je ključ roditelja praznog čvora manji od ključa elementa x, tada se element x
upisuje u prazni čvor. Time je postupak završen.
3. Ako je ključ roditelja praznog čvora veći od ključa elementa x, tada se element roditelja
kopira u prazni čvor, a čvor u kojem je bio roditelj se uzima kao prazni čvor. Postupak
se ponavlja korakom 2.
/*
Funkcija insert() umeće element u red
*
Argumenti: pQ - red
*
x - element koji se umeće
*/
void
insert(PQUEUE pQ, elemT x)
{
int
i;
assert(pQ);
/*
proveri kapacitet reda i povećaj ga ako je N>=kapacitet*/
if
( pQ->N >= pQ->kapacitet-1 ) {
pQ->kapacitet
*= 2; /*udvostruci kapacitet hipa*/
pQ->elementi
= (elemT *)
realloc(pQ->elementi,sizeof(elemT)*pQ->kapacitet);
if(!pQ->elementi)
exit(1);
}
/*
umetni element x i povećaj N */
i
= pQ->N++;
while
(i) {
int
otac = (i-1)/2;
if
(x.key > pQ->elementi[otac].key) break; /*pravilo 2 algoritma
*/
pQ->elementi[i].key
= pQ->elementi[otac].key;
i
= otac;
}
pQ->elementi[i]
= x;
}
5.
Dat je usmeren graf G=(V,E), na slici tako da V={A, B, C, D, E, F,
G}. Za početni poziv DFS(A) (DFS-pretraga grafa u dubinu),
konstruisati odgovarajuce DFS stablo. Navedite grane stabla, kao i
direktne, povratne i poprečne grane. Pretpostavlja se da su
grane (v,w) koje izlaze iz čvora v uređene
leksikografski prema čvorovima w. OKRENITE!!!
Grane stabla su: AB, BF, BE, FC, FG, ED
Direktne: AD
POPRECNE: GC, FE
Povratne: DB
6. Zaokružite slovo ispred tačnog tvrđenja. Netačna tvrđenja obrazložiti (u zavisnosti od tvrđenja: primerom, tačnim tvrđenjem,...).
A Poredak posecivanja cvorova grafa BFS algoritmom je tipican primer FIFO (First In First Out) discipline pristupa.
B Matrica povezanosti kojom se predstavlja neusmereni graf simetrična je u odnosu na sporednu dijagonalu.
TACNO JE: GLAVNU DIJAGONALU
C Uklanjanje elementa sa steka obavlja se po FILO principu (First In Last Out).
D log n!= Ω(n!)
TACNO JE log n!= Ω(n log n), videti poglavlje o donjoj granici slozenosti sortiranja
E Usmereni graf ima ciklus ako i samo ako u odnosu na DFS stablo grafa nema povratnu granu
TACNO: moze da ima
F Donja granica složenosti algoritama za sortiranje zasnovanih na upoređivanju elemenata je Ω(n)
TACNO Ω(n log n)
G Heap sort u početnoj fazi generisanja hipa zapravo generiše kompletno binarno stablo pretrage.
TACNO: kompletno ili delimicno kompletno binarno stablo, hip
I Umetanje i uklanjanje elementa iz reda se obavlja sa istog pristupnog kraja, tj. vrha reda.
TACNO: skida se sa kraja reda
J Na osnovu izlaza iz PREORDER i POSTORDER algoritma obilaska binarnog stabla može se na jedinstven način nacrtati to stablo
TACNO: inorder i preorder, inorder i postorder
BODOVANJE 7 + 8 + 8 + 8 + 9 + 10