[SVE PITALICE DO SAD]
Svrha sufiksnih veza je…
Uvodenje vremenskih optimizacija u prolasku kroz sufiksna stabla
U B-stablu reda 8 imamo cvor u podljevu s dva(2) kljuca. Blizanci cvora redom imaju tri(3) i pet(5) kljuceva. Koliko kljuceva ostaje u cvoru blizancu nakon minimalne redistribucije na cvor u podljevu?
4
U inicijalno praznu strukturu trie su upisane sijedece rijeci (bez navodnika): “Jarun”, “Caspian”, “Popopopopopo”, “Bundek”, “Huron”, “Baikal”, i “Jarunian”. Koliko djece ima korijenski cvor?
5
Koji je najmanji teoretski faktor ravnoteze BF u bilo kojem cvoru RB stabla T, visine h > 1?
-h / 2
U B-stablu reda 8 imamo cvor u podljevu s dva(2) kljuca. Blizanci cvora redom imaju tri(3) i pet(5) kljuceva. Koliko kljuceva ima novi cvor koji nastaje spajanjem (merge) cvora u podljevu i jednog od navedenih blizanaca?
6
Ukkonenov algoritam izgradnje sufiksnog stabla temelji se na…
Izgradnji implicitnih sufiksnih stabala za svaki pojedini prefiks znakovnog niza
U inicijalno praznu strukturu (sufiksni) trie su upisane sijedece rijeci (bez navodnika): “Jarun”, “Caspian”, “Popopopopopo”, “Bundek”, “Huron”, “Baikal”, i “Jarunian”. Koliko listovnih cvorova ima doticni trie?
7
Konacni oblik prefiksnog stabla…
Ne ovisi o redoslijedu upisa
U inicijalno praznu strukturu trie su upisane sijedece rijeci (bez navodnika): “Jarun”, “Caspian”, “Popopopopopo”, “Bundek”, “Huron”, “Baikal”, i “Jarunian”. Kolika je dubina trie stabla (brojeci unutarnje cvorove i listove)?
13
Koja od sljedecih tvrdnji je istinita za svako RB stablo T, gdje je n broj unutarnjih cvorova tog stabla, a h visina tog stabla?
h / le 2log_2(n+1)
Koliki je maksimalni broj koraka u pretrazivanju B stabla reda m i visine h s maksimalnom popunjenoscu u najgorem slucaju?
(m-1)logm(mh)
Zaokruzi sve istinite tvranje:
- B stablo jedinstveno je odredjeno korijenom, cvorovima i granama koje oznacavaju prijelaze
- Korijen B stabla ima onoliko djece koliko je razlicitih elemenata u ulaznome nizu
Prosireno sufiksno polje sastoji se od sufiksnog polja i…
Polja LCP, ISA i BWT
Kolika je slozenost operacija brisanja vrijednosti iz RB stabla?
O(log(n))
Koliko vrijednosti je spremljeno u maksimalno popunjenom B-stablu reda 5, visine 3?
124
U inicijalno praznu strukturu trie su upisane sijedece rijeci (bez navodnika): “Jarun”. "Caspian*, “Popopopopopo”, “Bundek", “Huron”, “Baikal”, i “Jarunian”. Koliki je stupanj unutarjeg cvora (koliko znakova sadrzi)?
18
Sufiksna stabla su…
Memorijski znacajno zahtjevnija od sufiksnog polja
Koliko vrijednosti je spremljeno u minimalno popunjenom B-stablu reda 5, visine 3?
17
Kolika je slozenost operacija upisa vrijednosti u RB stablo?
O(log(n))
Oznacite tvrdnje koje su istinite. Za strukturu podataka sufiksno stablo vrijedi:
- Korijen sufiksnog stabla ima onoliko djece koliko ima razlicitih znakova u ulaznom znakovnom nizu
- Sufiksno stablo je jedinstveno odredeno korijenom stabla, skupom cvorova i bridovima koji predstavljaju prijelaze
Za strukturu podataka Patricia stabla vrijedi:
Od prefiksnih stabala imaju manju prostornu slozenost
Oznacite sve korake postupka transformacije sufiksnog stabla u implicitno sufiksno stablo:
- Uklanjanje grana koje sadrze samo prazan niz
- Sazimanje unutarnjih cvorova koji su imali samo jedno dijete
- Brisanje oznaka za kraj niza $
