Organizacija podatkov (20 %) (doc. Zoran Bosnić)

Pregled poskusa 1

Začeto dnečetrtek, 28. oktober 2010, 18:57
Dokončano dneponedeljek, 1. november 2010, 20:19
Porabljeni čas4 dni 2 ure
Točke20/20
Ocena10 od možne ocene 10 (100%)
Question 1
Točke: 1/1

Katere izmed naslednjih problemov lahko modeliramo in rešujemo z grafi?
1.) optimizacija cene komunikacijskih, energetskih in prometnih mrež,
2.) določevanje časovno-kritičnih delov velikih projektov,
3.) izračun maksimalnega pretoka,
4.) iskanje najkrajših poti

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenavse od naštetega18:57:43 dne 28/10/1011
2Zapri in ocenivse od naštetega20:19:37 dne 1/11/1011
Question 2
Točke: 1/1
V nekem podatkovnem tipu se elementi lahko podvajajo. Tip je lahko implementiran s poljem ali iskalnim drevesom. Do njegovih elementov dostopamo preko ključev, ki določajo element iz zaloge vrednosti. O katerem podatkovnem tipu govorimo?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaslovar (angl. dictionary)19:01:10 dne 28/10/1000
2Ocenaseznam (angl. list)19:01:19 dne 28/10/1000
3Ocenapreslikava (angl. mapping)19:01:46 dne 28/10/1011
4Ocenaslovar (angl. dictionary)19:03:20 dne 28/10/1001
5Zapri in ocenislovar (angl. dictionary)20:19:37 dne 1/11/1001
Question 3
Točke: 1/1
V prazno binarno iskalno drevo izvajamo dodajanje novih elementov s postopkom dodajanja v liste drevesa (ne dodajanje v koren). V naslednjem vrstnem redu dodamo elemente: 14, 6, 35, 18, 16, 2, 17. Kakšne višine je dobljeno drevo (pri tem štej, da je koren na višini 1)?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocena519:04:29 dne 28/10/1011
2Zapri in oceni520:19:37 dne 1/11/1011
Question 4
Točke: 1/1

Nad zaprto zgoščeno tabelo tabela velikosti m = 4 izvajamo vstavljanje elementov s ključi v naslednjem vrstnem redu: 8, 2, 7, 11.

Zgoščevalna funkcija je definirana kot:

h(x) = x mod m

V primeru sovpadanja izračunane vrednosti po prvi zgoščevalni funkciji pa izračunamo naslednji možni položaj elementa z zaporedjem funkcij:

hi+1(x) = (hi(x) + 1) mod m

Na katerem indeksu zgoščene tabele je ob koncu dodajanja shranjem element s ključem 11?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocena119:40:35 dne 1/11/1011
2Zapri in oceni120:19:37 dne 1/11/1011
Question 5
Točke: 1/1

Podatkovni tip Prioritetna vrsta (angl. priority queue) omogoča implementacijo vrste, ki ne deluje po sistemu FIFO, ampak dovoljuje, da elementi z višjo prioriteto "prehitijo" v vrsti elemente z nižjo. Na ta način omogoča direkten dostop do elementa z največjo priroriteto, implementiramo pa jo lahko na različne načine.

Katera od naslednjih implementacij abstraktnega podatkovnega tipa PRIORITETNA VRSTA omogoča najbolj učinkovito dodajanje novih elementov v smislu najmanjšega reda časovne zahtevnosti?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenakopica19:42:20 dne 1/11/1000
2OcenaAVL drevo19:42:27 dne 1/11/1000
3Ocenaoptimalno binarno iskalno drevo19:42:30 dne 1/11/1000
4Ocenaneurejeni seznam19:42:34 dne 1/11/1011
5Ocenakopica19:42:54 dne 1/11/1001
6Zapri in ocenikopica20:19:37 dne 1/11/1001
Question 6
Točke: 1/1

Katero od naslednjih zaporedij vozlišč predstavlja VMESNI (angl. inorder) obhod drevesa na sliki?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenab, a, e, c, f, g, d, h19:44:18 dne 1/11/1011
2Zapri in ocenib, a, e, c, f, g, d, h20:19:37 dne 1/11/1011
Question 7
Točke: 1/1
Vrsta je podatkovna struktura, ki deluje po principu FIFO (first-in-first-out). Če nad sprva prazno vrsto izvedemo operacije: dodamo elemente z vrednostmi od 1 do 100 (v tem zaporedju), nato odstranimo 29 elementov, velja naslednje:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenana izhodu vrste je element z vrednostjo 3019:44:47 dne 1/11/1011
2Zapri in ocenina izhodu vrste je element z vrednostjo 3020:19:37 dne 1/11/1011
Question 8
Točke: 1/1

Katera od naslednjih možnosti opisuje implementacijo abstraktnega podatkovnega tipa SEZNAM, ki jo odlikujejo naslednje lastnosti:
- zaradi načina implementacije lahko tako implementiran seznam hrani omejeno število elementov,
- urejeno dodajanje elementov (t.j. dodajanje novega elementa v seznam na točno določeno mesto tako, da se urejenost elementov - npr. naraščajoča - v seznamu ohranja) lahko izvedemo brez poprejšnjega zamikanja elementov (da naredimo prostor za nov element).

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaimplementacija s kazalci19:45:33 dne 1/11/1000
2Ocenaimplementacija z dvosmernim seznamom s kazalci19:45:36 dne 1/11/1000
3Ocenaimplementacija z indeksnimi kazalci19:45:40 dne 1/11/1011
4Ocenaimplementacija s kazalci19:46:07 dne 1/11/1001
5Zapri in oceniimplementacija s kazalci20:19:37 dne 1/11/1001
Question 9
Točke: 1/1
AVL drevesa hranijo v vozliščih poleg ključa elementa tudi vrednost ravnotežnega faktorja. V primeru, da znaša absolutna vrednost ravnotežnega faktorja nekega vozlišča 2, to pomeni:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenada se višina enega izmed poddreves za 2 razlikuje od višine drugega poddrevesa; ker takšno AVL drevo ni veljavno, ga moramo poravnati z rotacijami19:46:49 dne 1/11/1011
2Zapri in ocenida se višina enega izmed poddreves za 2 razlikuje od višine drugega poddrevesa; ker takšno AVL drevo ni veljavno, ga moramo poravnati z rotacijami20:19:37 dne 1/11/1011
Question 10
Točke: 1/1

Vrsta je podatkovni tip, ki deluje po principu FIFO (first-in-first-out), sklad pa podatkovni tip, ki deluje po princiou LIFO (last-in-first-out).

Denimo, da v nekem programskem jeziku obstaja že implementacija podatkovnega tipa vrsta, implementacija sklada pa ne. Odločimo se, da želimo simulirati sklad z uporabo vrste.

Najmanj koliko primerkov (instanc) vrste potrebujemo za simulacijo enega sklada?

(Predpostavi, da v vseh ponujenih odgovorih - podatkovnih strukturah uporabljamo elemente enakega tipa kot v originalni vrsti; razširitev elementov in uporaba dodatnih elementov ni dovoljena.)

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenadve19:48:59 dne 1/11/1011
2Zapri in ocenidve20:19:37 dne 1/11/1011
Question 11
Točke: 1/1

AVL drevesa imajo lastnost, da se višini levega in desnega poddrevesa vsakega notranjega vozlišča lahko razlikujeta največ za 1. Kolikšno je najmanjše število vozlišč (vključno s korenom in listi), ki ga ima lahko AVL drevo višine 5 (privzemi, da ima drevo z enim samim vozliščem višino enako 1)?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocena1519:55:19 dne 1/11/1000
2Ocena1219:56:20 dne 1/11/1011
3Zapri in oceni1220:19:37 dne 1/11/1011
Question 12
Točke: 1/1
V splošnem lahko drevo poljubne stopnje implementiramo tudi z dovolj veliko tabelo (poljem), v kateri so elementi shranjeni tako, da korenu drevesa rekurzivno sledijo najprej elementi najbolj levega poddrevesa, nato pa elementi ostalih zaporednih dreves vse do skrajno desnega. Denimo, da imamo s takšno tabelo implementirano trojiško drevo višine 4 (privzemi, da ima drevo z enim samim vozliščem višino enako 1). Na katerem indeksu takšne tabele je shranjen skrajno levi list skrajno desnega poddrevesa korena (indeksiranje tabele se začne z 0)?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocena3120:07:37 dne 1/11/1000
2Ocena2920:10:39 dne 1/11/1011
3Zapri in oceni2920:19:37 dne 1/11/1011
Question 13
Točke: 1/1

Katera od naslednjih lastnosti karakterizira podatkovno strukturo Množica (angl. Set), ki jo uporabljamo za hranjenje nabora podatkov?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenavrstni red elementov v njej ni pomemben20:10:57 dne 1/11/1011
2Zapri in ocenivrstni red elementov v njej ni pomemben20:19:37 dne 1/11/1011
Question 14
Točke: 1/1
Sklad je podatkovna struktura, ki deluje po principu LIFO (last-in-first-out). Če nad sprva praznim skladom izvedemo operacije: dodamo 100 elementov, dodamo element X, izbrišemo 50 elementov, velja naslednje:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaelementa X več ni v skladu20:11:24 dne 1/11/1011
2Zapri in ocenielementa X več ni v skladu20:19:37 dne 1/11/1011
Question 15
Točke: 1/1
Podatkovna struktura Prioritetna vrsta (angl. priority queue) omogoča implementacijo vrste, ki ne deluje po sistemu FIFO, ampak dovoljuje, da elementi z višjo prioriteto "prehitijo" v vrsti elemente z nižjo. Ta struktura omogoča direkten dostop do elementa z največjo priroriteto, implementiramo pa jo lahko na različne načine. Kateri od naslednjih načinov ni primeren za njeno implementacijo?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaneurejen seznam20:12:05 dne 1/11/1000
2Ocenabinarno iskalno drevo20:12:13 dne 1/11/1000
3Ocenakopica20:12:16 dne 1/11/1000
4Ocenavse od zgornjega je primerno20:12:22 dne 1/11/1011
5Ocenaneurejen seznam20:12:26 dne 1/11/1001
6Zapri in ocenineurejen seznam20:19:37 dne 1/11/1001
Question 16
Točke: 1/1

Z notacijo (levoPoddrevo, koren, desnoPoddrevo), kjer je prazno drevo označeno s podčrtajem (_), je podano naslednje binarno iskalno drevo:

((((_,H,_),D,_),B,(_,E,_)),A,((_,F,(_,I,_)),C,(_,G,_)))

Kateri od naslednjih elementov ima tretji največji ključ?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaI20:14:58 dne 1/11/1011
2Zapri in oceniI20:19:37 dne 1/11/1011
Question 17
Točke: 1/1
V dovolj veliki zgoščeni tabeli se odločimo hraniti informacije o vseh slovenskih vozilih. Če predpostavimo, da uporabljamo "dobro" razprševalno funkcijo, kateri izmed naslednjih podatkov je najbolj primeren kot njen argument?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaregistrska oznaka20:15:19 dne 1/11/1011
2Zapri in oceniregistrska oznaka20:19:37 dne 1/11/1011
Question 18
Točke: 1/1

Rdeče-črno drevo ustreza naslednjim pogojem:

i.) je delno poravnano binarno iskalno drevo,
ii.) vsako črno vozlišče ima lahko samo rdeča sinova,
iii.) za vsako vozlišče mora veljati, da vsaka pot od vozlišča do praznega poddrevesa vsebuje enako število črnih vozlišč.

Kaj od gornjega drži?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenai.), ii.) in iii.)20:15:42 dne 1/11/1000
2Ocenaii.) in iii.)20:15:45 dne 1/11/1000
3Ocenai.) in iii.)20:15:49 dne 1/11/1011
4Ocenaii.) in iii.)20:15:54 dne 1/11/1001
5Zapri in oceniii.) in iii.)20:19:37 dne 1/11/1001
Question 19
Točke: 1/1
Vrsta je podatkovna struktura, ki deluje po principu FIFO (first-in-first-out). S katero izmed naslednjih podatkovnih struktur je možno simulirati dodajanje in brisanje elementov, kot ga izvajamo pri uporabi vrste?
(Predpostavi, da v vseh ponujenih odgovorih - podatkovnih strukturah uporabljamo elemente enakega tipa kot v originalni vrsti; razširitev elementov in uporaba dodatnih elementov ni dovoljena.)
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaz dvema skladoma20:16:50 dne 1/11/1011
2Zapri in oceniz dvema skladoma20:19:37 dne 1/11/1011
Question 20
Točke: 1/1

Kakšna je najmanjša možna višina štiriškega drevesa, ki ima 220 vozlišč (privzemi, da ima drevo z enim samim vozliščem višino enako 1)?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocena520:18:16 dne 1/11/1011
2Zapri in oceni520:19:37 dne 1/11/1011