Pravilnost zapiskov (baze podatkov)

Zanima me ali so naslednji testi pravilno rešeni, če lahko samo kdo na hitro preleti. Lepo bi prosil za pomoč tistega, ki se spozna. Hvala lepa.

TESTI:

I.del – A

1.)S postopkom bisekcije želimo najti zapis med 5-imi urejenimi zapisi. Največ kolikokrat bomo algoritem izvedli (vsaka ponovitev šteje ua novo izvedbo)?
- 2
2.) Kaj opisuje zagato?
- dead lock
3.) V novo razpršeno datoteko bi radi zapisali zapise z numeričnimi ključi z vrednostmi od 0 do 1000. V začetku načrtujemo do 30 zapisov. Katera od predlaganih razpršilnih funkcij je najbolj primerna?
- hash code=ključ mod 19
4.) Katera organizacija datotek vsebuje ključe in naslove zapisov?
- indeksna
5.) Katera organizacija datotek vsebuje naslove naslednikov v zapisu?
- povezana
6.) Kateri del organizacijskega sistema neposredno komunicira z BP?
- informacijski sistem
7.) Kdaj praviloma NE uporabimo rekurzivnega zapisa algoritma?
- ko je možna preprosta iterativna rešitev
8.) Kako imenujemo shemo, ki meji na zunanji svet?
- konceptualna shema
9.) Kaj najbolje opisuje avtorsko zaščito podatkov, kot funkcijo SUBPja?
- uporaba nivojev dostopa
10.) Kakšna je časovna kompleksnost (Tk) iskanja zapisa v razpršeni datoteki glede na število zapisov v datoteki (n)?
- Neodvisna od n
11.) Kakšna je časovna kompleksnost (Tk) iskanja (z bisekcijsko metodo) zapisa v sekvenčni datoteki glede na število zapisov v datoteki (n)?
- Logaritemsko odvisna od n
12.) Kakšna je časovna kompleksnost (Tk) iskanja zapisa v indeks-sekvenčni datoteki glede na število zapisov v datoteki (n)?
- Linearno odvisna od n
13.) Kaj je namen analize obstoječih podatkov v okviru podatkovnega rudarjenja (data mitinga)?
- ?
14.) Kaj od naštetega NE spada pod dinamično spremljanje deleovanja BP?
- število atributov
15.) V kako organizirano datoteko bi zapisali binarno drevo?
- razpršeno
16.) Kako sta povezana podatkovno skladišče (PS) in operativna baza podatkov (OBP)?
- PS je nadgradnja OBP
17.) Kaj je najmanjša enota podatkovnega tipa, ki lahko samostojno sodeluje v obdelavi?
- atribut
18.) Časovno gledano, kako so si sledili modeli podatkov v uporabi:
- Codasyl, potem relacijski model, potem objektni m.
19.) Kako imenujemo ključ, ki pripada samo enemu zapisu?
- enoznačni
20.) Za kakšno vrsto organizacije gre pri FAT (file alloc. table na disku), ki za posamezne datoteke vsebuje pozicije na disku, kjer se nahajajo podatki, ki datoteko sestavljajo?
- razpršena
21.) Za kakšno vrsto organizacije gre pri šolskem urniku, kot ga objavljajo v biltenu?
- indeks-sekvenčna
22.) Kaj ključ NI?
- Lahko je cel zapis
23.) Kaj je concurrent usage:
- sočasna raba
24.) SQL uporabljamo za:
- doseganje podatkov
25.) Kaj nam pove stopnja (degree) relacije?
- število stolpcev v tabeli
26.) Kaj kardinalnost NI?
- stopnja relacije
27.) Katera tehnologija v zgodovinskem razvoju je omogočila nastanek javnih baz podatkov (JBP)?
- komunikacija teh
28.) Ko uporabnik brska po BP, to vedno počne preko:
- SUBP
29.) Kateri atribut NE bi izbrali v tabeli avtomobilov neke avtošole za ključ?
- znamka avtomobila
30.) Kako lahko dostopamo do podatkov v objektnem modelu podatkov?
- s select stavkom v SQL-u, če poznamo imena tabel

II. del A

9.) Mehurčno sortiranje:
9.1. V čem so problemi sortiranja zapisov v datoteki?
- Mehurčno sortiranje zaradi svoje kvadratne časovne kompleksnosti pri veliki količini podatkov odpove in se zato ne uporablja.
9.2. Kako se izognemo sortiranju datotek, da vseeno pospešimo proces iskanja zapisa v datoteki?
-
9.3. Zakaj zapisov v razpršeni datoteki ne sortiramo mehurčno'
- Čas dosega podatkov je neodvisen od obsega podatkov. Prostorska kompleksnost pri tej organizaciji je zelo velika, se pravi, da te datoteke potrebujejo več prostora. Zakonitost, ki velja pri razpršeni organizaciji datoteke je, da moramo imeti v tabeli prazen prostor, vsaj 1/3 tabele mora biti prazne.
9.4. Predvidite časovno kompleksnost mehurčnega sortiranja 10-ih neurejenih zapisov.
- Algoritem z mehurčnim sortiranjem ima veliko časovno kompleksnost. Pri linearnem iskanju gledamo po vrsti, v povprečju iščemo polovico zapisov.
9.5. Opišite princip, kako mehurčno sortiramo zapise.
- Je razvrščanje ključev po rastočem oz. padajočem vrstnem redu.

13.) Povezane strukture:

13.1. Naštej 4 tipe povezanih struktur
- binarno drevo, drevo, seznam, graf
13.2. Kakšna je razlika med drevesom in binarnim drevesom?
- DREVO (tree): enemu podatku sledita dva itd.(ima poljubno naslednikov). Je povezan graf brez cikla, drevo s korenom iz katerega izhaja drevo.
-BINARNO DREVO: ima lahko največ dva naslednika. Koren drevesa ima dva potomca, vsako vozlišče ima zopet dva potomca. V vozlih se nahajajo zapisi. Vozel vsebuje:ključ, podatek levi in desni kazalec. Njegova urejenost: vse kar je levo je manjše, kar je desno pa večje od izhodiščnega števila.
13.3. Primerjaj časovno kompleksnost (Tk) iskanja in vstavljanja podatka v binarnem drevesu.
-Časovna kompleksnost iskanja v bin. drevesu je logaritemska (ker z vsakim iskanjem razpolovimo iskanje), kar velja samo, če je drevo uravnoteženo. Pri neuravnoteženem drevesu je boljša metoda bisekcije. Primer:
1. če je drevo prazno, X ni v drevesu
2. primerjaj X s korenom drevesa in:
- če velja X = koren, X je najden
- če velja X < koren, vstavi X v levo poddrevo
- če velja X > koren, vstavi X v desno poddrevo
13.4. Opišite postopek brisanja iz binarnega drevesa:
1.Če brišemo elemente moramo zagotoviti verjetnost, da so na levi manjši, na desni pa večji elementi. Primer:
- če X ni v drevesu , drevo ostane nespremenjeno
- če ima X največ enega naslednika, X preskočimo s prevezavo
- če ima X dva naslednika: v levem drevesu poiščemo največji element (skrajno desni)-ta element dvignemo namesto X.
13.5.Ali je za hitrost iskanja podatkov v binarnem drevesu pomembna uravnoteženost drevesa in kdaj je drevo uravnoteženo?
- V binarnem drevesu moramo zagotoviti ravnotežje levega in desnega poddrevesa, da je na obeh straneh enako število ključev. Časovna kompleksnost iskanja je logaritemska, medtem ko je zagotavljanje ravnotežja eksponencionalna.
19. Normalizacija:
- Je proces poenostavitve zapisov z razbijanjem ene relacije na več relacij. Vsak zapis mora po normalizaciji ostati neodvisen od drugega.
19.2. Kdaj pravimo, da je nek element osnoven?
- Ker ima normalizacija zelo pomembno vlogo predvsem pri sistemski analizi obravnavanja podatkov, se pravi kadar hočemo popraviti ali pa sestaviti nov informacijski sistem ali osnovati bazo podatkov.
19.3. Kako dobimo 1NF?
- Normalizacija ima tri oblike: 1. normalno formo, 2. NF in 3 NF. 1. in 2. NF zahtevajo vsi sistemi. Relacijo normaliziramo, da dobimo neformalno formo, ki odstrani vse podatkovne agregate, tako, da je ves element samostojen. Podatkovne elemente izpišemo vsakega v svojo vrsto, določimo in podčrtamo ključe (nesme biti dveh istih ključev), označimo ponavljajoče se skupine podatkovnih elementov.












III. del A.

12. Ocenite časovno kompleksnost naslednjega algoritma:
i = 0
Do While i < n
i = i + 2 REŠITEV: Tk =  . n ( proporcionalen je n, kompleksnost je linearna)
.........
Loop
(pri ....se n, i ne spreminjata; n je pozitivno celo število>0)

20. Napišite Visual Basic zapis za vodenje evidence izposoje knjig v knjižnici. Vsak si lahko izposodi največ 50 knjig. Zapis pretvorite v vsaj 2NF.
REŠITEV: Nismo še obravnavali VB!
Knjiga ( št knjige, avtor – priimek, ime, naslov, leto izdaje, izdajatelj)
Član (št. Člana, ime, priimek, naslov)
Sposoja ( št. knjige, št. člana, št. Izposoje, datum-izdaje, datum-vrnitve)