Organizacija podatkov (20 %) (doc. Zoran Bosnić)
Pregled poskusa 1
Začeto dne | četrtek, 28. oktober 2010, 18:57 |
---|---|
Dokončano dne | ponedeljek, 1. november 2010, 20:19 |
Porabljeni čas | 4 dni 2 ure |
Točke | 20/20 |
Ocena | 10 od možne ocene 10 (100%) |
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
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | vse od naštetega | 18:57:43 dne 28/10/10 | 1 | 1 |
2 | Zapri in oceni | vse od naštetega | 20:19:37 dne 1/11/10 | 1 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | slovar (angl. dictionary) | 19:01:10 dne 28/10/10 | 0 | 0 |
2 | Ocena | seznam (angl. list) | 19:01:19 dne 28/10/10 | 0 | 0 |
3 | Ocena | preslikava (angl. mapping) | 19:01:46 dne 28/10/10 | 1 | 1 |
4 | Ocena | slovar (angl. dictionary) | 19:03:20 dne 28/10/10 | 0 | 1 |
5 | Zapri in oceni | slovar (angl. dictionary) | 20:19:37 dne 1/11/10 | 0 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 5 | 19:04:29 dne 28/10/10 | 1 | 1 |
2 | Zapri in oceni | 5 | 20:19:37 dne 1/11/10 | 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?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 1 | 19:40:35 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | 1 | 20:19:37 dne 1/11/10 | 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?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | kopica | 19:42:20 dne 1/11/10 | 0 | 0 |
2 | Ocena | AVL drevo | 19:42:27 dne 1/11/10 | 0 | 0 |
3 | Ocena | optimalno binarno iskalno drevo | 19:42:30 dne 1/11/10 | 0 | 0 |
4 | Ocena | neurejeni seznam | 19:42:34 dne 1/11/10 | 1 | 1 |
5 | Ocena | kopica | 19:42:54 dne 1/11/10 | 0 | 1 |
6 | Zapri in oceni | kopica | 20:19:37 dne 1/11/10 | 0 | 1 |
Katero od naslednjih zaporedij vozlišč predstavlja VMESNI (angl. inorder) obhod drevesa na sliki?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | b, a, e, c, f, g, d, h | 19:44:18 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | b, a, e, c, f, g, d, h | 20:19:37 dne 1/11/10 | 1 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | na izhodu vrste je element z vrednostjo 30 | 19:44:47 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | na izhodu vrste je element z vrednostjo 30 | 20:19:37 dne 1/11/10 | 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).
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | implementacija s kazalci | 19:45:33 dne 1/11/10 | 0 | 0 |
2 | Ocena | implementacija z dvosmernim seznamom s kazalci | 19:45:36 dne 1/11/10 | 0 | 0 |
3 | Ocena | implementacija z indeksnimi kazalci | 19:45:40 dne 1/11/10 | 1 | 1 |
4 | Ocena | implementacija s kazalci | 19:46:07 dne 1/11/10 | 0 | 1 |
5 | Zapri in oceni | implementacija s kazalci | 20:19:37 dne 1/11/10 | 0 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | da 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 rotacijami | 19:46:49 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | da 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 rotacijami | 20:19:37 dne 1/11/10 | 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.)
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | dve | 19:48:59 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | dve | 20:19:37 dne 1/11/10 | 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)?
Katera od naslednjih lastnosti karakterizira podatkovno strukturo Množica (angl. Set), ki jo uporabljamo za hranjenje nabora podatkov?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | vrstni red elementov v njej ni pomemben | 20:10:57 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | vrstni red elementov v njej ni pomemben | 20:19:37 dne 1/11/10 | 1 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | elementa X več ni v skladu | 20:11:24 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | elementa X več ni v skladu | 20:19:37 dne 1/11/10 | 1 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | neurejen seznam | 20:12:05 dne 1/11/10 | 0 | 0 |
2 | Ocena | binarno iskalno drevo | 20:12:13 dne 1/11/10 | 0 | 0 |
3 | Ocena | kopica | 20:12:16 dne 1/11/10 | 0 | 0 |
4 | Ocena | vse od zgornjega je primerno | 20:12:22 dne 1/11/10 | 1 | 1 |
5 | Ocena | neurejen seznam | 20:12:26 dne 1/11/10 | 0 | 1 |
6 | Zapri in oceni | neurejen seznam | 20:19:37 dne 1/11/10 | 0 | 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č?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | I | 20:14:58 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | I | 20:19:37 dne 1/11/10 | 1 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | registrska oznaka | 20:15:19 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | registrska oznaka | 20:19:37 dne 1/11/10 | 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?
(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.)
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | z dvema skladoma | 20:16:50 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | z dvema skladoma | 20:19:37 dne 1/11/10 | 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)?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 5 | 20:18:16 dne 1/11/10 | 1 | 1 |
2 | Zapri in oceni | 5 | 20:19:37 dne 1/11/10 | 1 | 1 |