Font size
WorksheetsSPA Banja
Total questions: 58
Worksheet time: 37mins
Stablo za binarno pretrazivanje ima ukupno M cvorova, a visinu K. Vreme potrebno za pronalazenje nekog cvora u stablu je proporcionalno sa:
M*K
K
M
M + K
Jedna od osnovnih karakteristike matrice susedstva kao nacina implementacije:
slozena za manipulaciju
prostorna kompleksnost O(n)
Efikasno koriscenje memorije
za pamcenje elemenata
Sekundarna kolizija se javlja kada:
se sudare kljucevi koji imaju razlicite h(k)
razliciti kljucevi imaju iste adrese (sekundarna kolizija)
kada se koristi metod olancavanja
sve navedeno
Ako je visina kompletnog binarnog stabla 7, koliko ima cvorova to stablo?
(a)
Koje je tvrdjenje tacno za B stablo reda 22?
ni jedan cvor ne moze imati manje od 22/2 kljuceva
cvorovi na svim nivoima ne moraju da imaju isti broj kljuceva
AVL stablo je visine 3. Koji je najveci broj cvorova koje moze da ima?
(a)
Sta ne vazi za AVL stablo?
(a)
Ako BST stablo ima n elemenata i visinu H, od cega ce zavisiti vreme prolaska kroz stablo?
(a)
Ako binarno stablo ima n elemenata i visinu H, od cega ce zavisiti vreme prolaska kroz stablo?
(a)
Efikasnost hashing algoritma je?
(a)
Kada se javlja sekundarna kolizija?
(a)
Primarna kolizija je?
(a)
Dato je skoro kompletno binarno stablo, implementirano preko niza. Ako je cvor sacuvan u nizu na poziciji 7, na kojoj poziciji u nizu se nalazi levo dete njegovog roditelja:
3
4
7
8
Neka binarno stablo trazenja ima ukupno N cvorova, a visinu H. Vreme potrebno za pronalazenje nekog cvora u stablu je proporcionalan sa:
N
N*H
N+H
H
Koje od sledecih tvrdjenja NIJE tacno:
Sekundarna kolizija se javlja kada se sudare kljucevi koji imaju iste h(k)
Problem kolizije se javlja kod ubacivanja i pretrazivanja zapisa
Otvoreno adresiranje moze da generise primarnu koliziju
Problem kolizije se resava uvodjenjem posebne zone za zapise koji dobiju istu adresu
Efikasnost najgoreg i prosecnog slucaja pretrazivanja u BST stablu je:
O(n), O(log n)
O(n), O(n)
O(log n), O(n)
O(log n), O(log n)
Dato je kompletno binarno stablo sa n elemenata. Visina tog stabla je?
n
n/2
(int)(log n) + 1
2^n – 1
Dato je skoro kompletno binarno stablo, implementirano preko niza. Ako je cvor sacuvan u nizu na poziciji sa indeksom 5, na kojoj poziciji u nizu se nalazi desno dete njegovog roditelja?
16
2
6
15
Ako binarno stablo nije skoro kompletno, koje izmene je potrebno napraviti na strukturi da bi se lakse pristupilo cvorovima u stablu u nizu?
Nije potrebna nikakva promena. Pristupa se sa 2i i 2i + 1 (ako je cvor i)
Koristiti istovremeno jos jedan niz u kome ce se cuvati stablo
Svaki cvor treba da cuva podatke o postojanju njegove “dece”
Napraviti odvojenu tabelu u kojoj ce se cuvati lokacija “dece”
6
9
8
Neki drugi broj
Ako je pozicija elementa niza 10, na kojoj poziciji ce se nalaziti desno dete njegovog roditelja?
4
5
9
10
Ako je indeks cvora 5, koliki ce biti indeks desnog deteta njegovog roditelja?
7
4
6
5
Koje tvrdjenje za B stablo je tacno?
svi cvorovi sadrze isti broj kljuceva
svi listovi su na istoj dubini
svi cvorovi koji nisu list imaju isti broj dece
svi kljucevi u cvoru su veci ili jednaki kljucevima u desnom detetu
Infix i prefix prolaz kroz stablo, a bilo je i da se zaokruzi sta NE predstavlja kretanje kroz graf po dubini:
(a)
Ako taj cvor ima desno dete, gde ce biti sacuvana njegova vrednost?
niz[i+1]
niz[i+2}
niz[2*i+1] (levo dete)
niz[2*i+2] (desno dete)
Koji je minimalan broj cvorova u skoro kompletnom binarnom stablu cija je visina jednaka 4
16
15
7
8
Sta je nivo cvora?
(a)
KOje tvrđenje je tačno?
Stablo je striktno binarno ali nije kompletno
Stablo nije ni kompletno ni striktno binarn
Stablo je i striktno binarno i kompletno
Stablo je kompletno ali nije striktno binarno
Dva stabla su slicna ako:
imaju istu strukturu
imaju identican informacioni sadrzaj
nista od ponudjenog
imaju istu visinu
Sta od ponudjenih opcija predstavlja nedostatak implementacije niza pomocu stabla:
Teska je za implementaciju
Tesko je doci do “dece” od nekog cvora
Potrebno je unapred znati najveci moguci broj cvorova
Tesko je pronaci “roditelja” od nekog cvora
Koji od prolaza NIJE prolaz po dubini kroz graf:
ABEFGIHCD
ADEGIFHCB
ACEGIFHDB
ABEFIGHCD
Data je metoda:
void quiz(int i) {
if (i >= 1) {
quiz(i/2);
System.out.print(“*”);
quiz(i/2);
}
}
Koliko zvezdica ce se ispisati ako pozovemo metodu quiz(5)?
14
7
Neki drugi broj
10
Prostorna kompleksnost matrice susedstva
(a)
Koje tvrdjenje je tacno za B stablo?
svi cvorovi sadrze isti broj kljuceva
koren moze imati najmanje 1 kljuc za stablo reda 16
listovi ne moraju da budu na istoj dubini
svi cvorovi koji nisu listovi imaju isti broj dece
Koje tvrdjenje je tacno za B stablo?
svi cvorovi sadrze isti broj kljuceva
koren moze imati najmanje 1 kljuc za stablo reda 16
listovi ne moraju da budu na istoj dubini
svi cvorovi koji nisu listovi imaju isti broj dece
Koliko zvezdica štampa
(a)
Sta ispisuje:
test(int n){
if (n>0)
test(n-2);
}
syso(n+” “);
za n=4
(a)
Koje tvrdjenje NIJE tacno za B stablo?
Svi clanovi ne moraju da sadrze isti broj kljuceva
Svi clanovi koji nisu listovi moraju da imaju isti broj dece
Moze da postoji cvor sa 1 kljucem za stablo reda 22
Svi listovi su na istoj dubini
Sta se ispisuje
(a)
Pocetno B* stablo ciji cvorovi primaju maksimalno 2 kljuca prikazano na sledecoj slici:
Kako izgleda stablo nakon izbacivanja sledeceg niza kljuceva 35, 50?
Koji od ponudjenih odgovora predstavlja dobru osobinu hash funkcije?
brzo se racuna
nema uniformnu raspodelu
nijedan od ponudjenih odgovora
ima tacku nagomilavanja
Vremenska kompleksnost iterativnog prefiksnog prolaza kroz binarno stablo je:
O(1)
O(log n)
O(n log n)
O(n)
Vremenska kompleksnost iterativnog prefiksnog prolaza kroz BST stablo je:
O(log n)
O(n)
O(1)
O(n log n)
Ako je broj cvorova u BST stablu n, koja je maksimalna moguca visina tog stabla?
(log n) + 1
n
n62
n+n
Data je metoda:
void quiz(int i) {
if (i >= 1) {
quiz(i/2);
System.out.print(i);
quiz(i/2);
}
}
Sta ce se ispisati ako pozovemo metodu quiz(5)?
1215121
1125211
5211211
5221111
ACEFGHBD
ADEFHGBC
ABFGEHCD
ABCDEFGH
U pocetno prazno AVL stablo se ubacuje sledeci niz brojeva: 50, 25, 30, 10, 60, 70. Koje od navedenih AVL stabala se donija nakon ovih ubacivanja?
Koji od ponudjenih odgovora, predstavlja pseudokod za izracunavanje broja elemenata u stablu?
find_size(root_node -> left_node) + find_size(root_node->right_node)
find_size(root_node -> left_node) + 1 + find_size(root_node->right_node)
find_size(root_node -> right_node) - 1
find_size(root_node -> left_node) + 1
Red stabla predstavlja:
(a)
ABDEFC
ACBEDF
ACBEDFA
ACBDFE
Koje tvrdjenje je tacno za B stablo?
svi cvorovi sadrze isti broj kljuceva
koren moze imati najmanje 1 kljuc za stablo reda 16
listovi ne moraju da budu na istoj dubini
svi cvorovi koji nisu listovi imaju isti broj dece
Sta, od ponudjenih opcija, predstavlja nedostatak implementacije niza pomocu stabla?
Teska je za implementaciju
Potrebno je unapred znati najveci moguci broj cvorova stabla
Tesko je doci do “dece” od nekog cvora
Tesko je pronaci “roditelja” od nekog cvora
Bice koriscena sledeca notacija:
A <: B znaci da je A podtip od B
A -> B predstavlja tip funkcije koja kao ulaz prima vrednost tipa A, a kao izlaz vraca vrednost tipa B
Pretpostavimo da imamo sledece tipove:
Windows 10 <: Operativni Sistem <: Softver Koji od ponudjenih odgovora NE predstavlja podtip funkcije Operativni Siste -> Operativni sistem?
Operativni Sistem -> Windows 10
Softver -> Operativni sistem
Softver -> Windows 10
Operativni Sistem -> Softver
Ako je broj cvorova u BST stablu n, koja je maksimalna moguca visina tog stabla?
(log n) + 1
n
n^2
n+n
U pocetno prazno B* stablo ciji cvorovi primaju maksimalno 2 kljuca ubacuju se sledeci niz kljuceva: 80, 30, 250, 330, 60, 70, 300. Koje od sledecih stabala se dobija ubacivanjem datog niza kljuceva?
Posmatrajmo stablo BST:
Ako izbacimo koren, iz desnog podstabla koji ce element doci na njegovo mesto:
28
35
32
26
20
26
12
22
U pocetno prazno AVL stablo se ubacuje sledeci niz brojeva: 10, 15, 30, -6, -3, 13, 6. Koje od navedenih AVL stabala se dobija nakon ovih ubacivanja?
