N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
MI
pont(45) :
Csak felv´eteli vizsga:
csak z´ar´ovizsga:
k¨oz¨os vizsga:
K¨ oz¨ os alapk´ epz´ eses z´ ar´ ovizsga – mesterk´ epz´ es felv´ eteli vizsga M´ ern¨ ok informatikus szak BME Villamosm´ ern¨ oki ´ es Informatikai Kar 2012. janu´ ar 3. A dolgozat minden lapj´ ara, a kerettel jel¨ olt r´eszre ´ırja fel nev´et, valamint felv´eteli azonos´ıt´oj´at, z´ar´ovizsga eset´en Neptun-k´ odj´ at! A fenti t´ abl´ azat megfelel˝ o kock´ aj´ aban jel¨ olje X-szel, hogy csak felv´eteli vizsg´at, csak z´ar´ovizsg´at, vagy k¨oz¨os felv´eteli ´es z´ ar´ ovizsg´ at k´ıv´ an tenni! A feladatok megold´ as´ ahoz csak pap´ır, ´ır´ oszer, zsebsz´amol´og´ep haszn´alata megengedett, egy´eb seg´edeszk¨ oz ´es a kommunik´ aci´ o tiltott. A megold´ asra ford´ıthat´ o id˝ o: 120 perc. A feladatok ut´an azok pontsz´am´at is felt¨ untett¨ uk. A megold´ asokat a feladatlapra ´ırja r´ a, illetve ott jel¨olje. Teszt jelleg˝ u k´erd´esek eset´en elegend˝o a kiv´alasztott v´ alasz bet˝ ujel´enek bekarik´ az´ asa. Kieg´esz´ıtend˝ o k´erd´esek eset´en, k´erj¨ uk, adjon vil´agos, egy´ertelm˝ u v´alaszt. Ha egy v´ alaszon jav´ıtani k´ıv´ an, teszt jelleg˝ u k´erd´esek eset´en ´ırja le az u ´j bet˝ ujelet, egy´ebk´ent jav´ıt´asa legyen egy´ertelm˝ u. A feladatlapra ´ırt inform´ aci´ ok k¨ oz¨ ul csak az eredm´enyeket vessz¨ uk figyelembe. Az ´attekinthetetlen v´alaszokat nem ´ert´ekelj¨ uk. A vizsga v´egezt´evel mindenk´eppen be kell adnia dolgozat´at. K´erj¨ uk, hogy a dolgozathoz m´as lapokat ne mell´ekeljen. Felh´ıvjuk figyelm´et, hogy illeg´ alis seg´edeszk¨ oz felhaszn´al´asa eset´en a fel¨ ugyel˝o kolleg´ak a vizsg´ab´ol kiz´arj´ak, ennek k¨ ovetkezt´eben felv´eteli vizsg´ aja, illetve z´ ar´ ovizsg´ aja sikertelen lesz, amelynek let´etel´et csak a k¨ovetkez˝o felv´eteli, illetve z´ ar´ ovizsga-id˝ oszakban k´ıs´erelheti meg u ´jb´ ol.
Szakir´ anyv´ alaszt´ as (Csak felv´eteli vizsga eset´en kell kit¨olteni) K´erem, az al´ abbi t´ abl´ azatban jel¨ olje meg, mely szakir´anyon k´ıv´anja tanulm´anyait folytatni. A t´abl´azatban a szakir´ any neve mellett sz´ ammal jel¨ olje a sorrendet: 1-es sz´am az els˝o helyen kiv´alasztott szakir´anyhoz, 2-es a m´ asodik helyen kiv´ alasztotthoz tartozik stb. Nem kell az ¨ osszes szakir´any mell´e sz´amot ´ırni, de legal´abb egy szakir´anyt jel¨ olj¨ on meg. Egy sorsz´ am csak egyszer szerepeljen. szakir´ any neve
gondoz´o tansz´ek
Alkalmazott informatika szakir´any Auton´ om ir´ any´ıt´ o rendszerek ´es robotok szakir´any H´ al´ ozatok ´es szolg´ altat´ asok szakir´any H´ırk¨ ozl˝ o rendszerek biztons´aga szakir´any Intelligens rendszerek szakir´any M´ediainformatika szakir´any Rendszerfejleszt´es szakir´any Sz´ am´ıt´ aselm´elet szakir´any Szolg´ altat´ asbiztos rendszertervez´es szakir´any
AAIT IIT TMIT HIT MIT TMIT IIT SZIT MIT
1
sorrend
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
2012. janu´ ar 3.
2
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Algoritmuselm´elet
2012. janu´ ar 3.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AL
pont(15) :
1. Legyen f1 (n) = (10n)! + 3nlog2 n
´es f2 (n) = 500(n + 10)n
(i) f1 = O(f2 ) ? (ii) f2 = O(f1 ) ? pont(1): 2. Egy kezdetben u ¨res M = 11 m´eret˝ u hash-t´ abl´aba a h(x) = x (mod M ) hash-f¨ uggv´eny seg´ıts´eg´evel kvadratikus pr´ ob´ aval besz´ urtunk 6 elemet. Ha az al´ abbi t´abla mutatja az eredm´enyt (´es t¨orl´es nem t¨ort´ent), akkor melyik lehetett az utols´ onak besz´ urt elem? 0
1 23
2 3
3 14
4 4
5
6 6
7
8
9 2
10
pont(1): 3. Egy n + 1 cs´ ucs´ u ker´ek (n ≥ 3) egy olyan ir´ any´ıtatlan Gn gr´af, amely egy n cs´ ucs´ u k¨orb˝ol ´es egy (n + 1)-edik v cs´ ucsb´ ol ´ all, ahol v-b˝ ol a k¨ or mind az n cs´ ucs´ahoz vezet egy ´el. H´ any (egyszer˝ u) 2 ´elb˝ ol ´ all´ ou ´t tal´ alhat´ o a Gn gr´afban?
pont(1): 4. Az adott gr´ afban A
a) sorolja fel egy minim´ alis fesz´ıt˝ ofa ´eleit abban a sorrendben, ahogy az A pontb´ol ind´ıtott Prim-algoritmus egy lehets´eges fut´ asa kiv´ alasztja ˝ oket! b) h´ any k¨ ul¨ onb¨ oz˝ o minim´ alis s´ uly´ u fesz´ıt˝ofa van?
B
4 4
1
2 4
3
6 F
E 3
5 G
2 5
D
C
3
H
5 8
8 I
pont(2):
3
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Algoritmuselm´elet
2012. janu´ ar 3.
5. Egy aut´ op´ alya-h´ al´ ozatot egy G = (V, E) ir´any´ıtatlan gr´af ´ır le, a gr´af cs´ ucsai a csom´opontok. Minden k´et szomsz´edos csom´ opontra adott, hogy mennyi az u ´td´ıj azon a szakaszon. Tudjuk, hogy egy adott A csom´opontn´ al ´erj¨ uk el a h´ al´ ozatot ´es hogy a n´ alunk lev˝ o p´enz¨osszeg P forint. Meg akarjuk hat´arozni az ¨osszes olyan B pontot, amelyik az A pontb´ ol ennyi p´enz´ert el´erhet˝ o. Melyik ismert algoritmust milyen bemeneten ´es hogyan lehet haszn´alni a feladat hat´ekony megold´as´ara?
pont(2): 6. Adott egy U = {u1 , u2 , . . . , un } alaphalmaz ´es ennek n´eh´any 2 elem˝ u r´eszalmaza, H1 , H2 , . . . , Hk ⊆ U . Olyan f : U −→ {0, 1} f¨ uggv´enyt keres¨ unk, melyre teljes¨ ul, hogy ha f (x) = f (y) ´es x 6= y, akkor nincs olyan 1 ≤ i ≤ k, amire {x, y} = Hi . Melyik ismet feladattal ekvivalens ez a probl´ema?
pont(2): 7. Tegy¨ uk fel, hogy P 6= NP. Tekints¨ uk a k¨ ovetkez˝o A ´es B probl´em´at: A : Adott egy G ir´ any´ıtatlan gr´ af ´es egy k pozit´ıv eg´esz sz´am. K´erd´es, hogy van-e G-ben legal´ abb k pont´ u teljes r´eszgr´af. B:
Adott egy G ir´ any´ıtatlan gr´ af ´es egy pozit´ıv eg´esz sz´am. K´erd´es, hogy van-e a G gr´ afban legal´abb k ´el˝ u (egyszer˝ u) u ´t.
Van-e polinomi´ alis visszavezet´es (Karp-redukci´o) (i) A-r´ ol B-re? (ii) B-r˝ ol A-ra? V´ alasz´ at r¨ oviden indokolja is! pont(3): 8. M´ atrix´ aval adott a G = (V, E) ir´ any´ıtott gr´ af, melyben nincs ir´any´ıtott k¨or. Minden v ∈ V cs´ ucshoz adott egy cv > 0 ´ert´ek is. A gr´ afban egy u ´t ´ert´eke legyen a hozz´atartoz´o cs´ ucsok ´ert´ekeinek szorzata. V´azoljon egy O(|V |2 ) l´ep´est haszn´ al´ o algoritmust, amely meghat´ arozza a G-beli utak ´ert´ek´enek maximum´at!
pont(3):
4
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2012. janu´ ar 3.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
H
pont(7,5) :
1. Mi a felt´etele annak, hogy a r´etegezett protokollarchitekt´ ura valamely r´eteg´eben a megval´os´ıt´ast megv´altoztassuk? a) A szomsz´ed r´etegek hozz´ aj´ arul´ asa sz¨ uks´eges. b) Csak a felette l´ev˝ o r´eteg –, amelynek szolg´altat´ast ny´ ujt, – hozz´aj´arul´as´ara van sz¨ uks´eg. c) Csak az alatta l´ev˝ o r´eteg –, amelynek szolg´altat´ast ny´ ujt, – hozz´aj´arul´as´ara van sz¨ uks´eg. d) Csak a mellette l´ev˝ o r´eteg –, amelynek szolg´altat´ast ny´ ujt, – hozz´aj´arul´as´ara van sz¨ uks´eg. e) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem j´ o. pont(1): 2. Eg´esz´ıtse ki az al´ abbi ´ all´ıt´ ast: ,,Ha egy Ethernet h´ al´ ozatban u ¨tk¨ oz´es t¨ ort´ent, akkor az ad´o egy . . . . . . . . . . . . -t bocs´at ki, hogy minden ´ allom´ as biztosan ´erz´ekelje az u ¨tk¨oz´est. Ezek ut´an az ´allom´as u ´jra megk´ıs´erli az ad´ast a backoff strat´egia alkalmaz´ as´ aval.” pont(1): 3. Nevezze meg (magyarul vagy angolul) azt a jellemz˝oen sokportos eszk¨ozt, amely a fizikai jeleket azok ´ertelmez´ese n´elk¨ ul tov´ abb´ıtja, ´es ez´ altal t¨ obb g´ep, illetve h´al´ozat ¨osszek¨ot´es´et is lehet˝ov´e teszi!
pont(1): 4. Milyen inform´ aci´ ot juttatnak el a csom´ opontok ´es kiknek a link-state (¨osszek¨ot´es-´allapot) routing m´odszer eset´en? a) A csom´ opontok elmondj´ ak a h´ al´ ozatr´ ol alkotott elk´epzel´eseiket mindenkinek. b) A csom´ opontok elmondj´ ak a szomsz´edaiknak a vel¨ uk kapcsolatos tapasztalataikat. c) A csom´ opontok elmondj´ ak a h´ al´ ozatr´ ol alkotott elk´epzel´eseiket szomsz´edaiknak. d) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. pont(1): 5. Mi´ert kell az IPv4 fejr´esz Header Checksum mez˝oj´enek a tartalm´at minden tov´abb´ıt´asi l´ep´esben u ´jrasz´amolni? a) Egy´ altal´ an nem kell, s˝ ot az hib´ at okozhat. b) Csup´ an biztons´ agi okb´ ol, hogy friss´ıts¨ uk a biteket. c) Mert a fejr´eszben esetleg megv´ altoztatunk valamit a tov´abb´ıt´as sor´an. d) Mert menetk¨ ozben a csomag adatr´esze s´er¨ ulhetett. pont(1):
5
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2012. janu´ ar 3.
6. Eg´esz´ıtse ki az al´ abbi ´ all´ıt´ ast: ,,A TCP protokoll torl´ od´ asvez´erl´esi mechanizmus´aban azt a technik´at, amely a torl´od´asvez´erl´esi ablakot minden id˝ oben meg´erkezett nyugta eset´en a dupl´aj´ara n¨oveli, . . . . . . . . . . . . nak nevezz¨ uk.” pont(1): 7. H´ any bit lenne r´ezvezet´eken (ahol a jelterjed´esi sebess´eg 2 · 108 m/s) CSMA/CD eset´en a minim´alis keretm´eret, ha tervez´eskor 1000 m-es maxim´ alis k´ abelhosszt enged¨ unk meg, 20 Mbit/s adatsebess´eg˝ u h´al´ozaton?
pont(1,5):
6
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2012. janu´ ar 3.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
O
pont(7,5) :
1. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik igaz az id˝ ooszt´asos (time-sharing) rendszerekre? a) Az id˝ ooszt´ asos rendszereket a k¨ otegelt (batch) feldolgoz´as tulajdons´againak jav´ıt´as´ara dolgozt´ak ki. b) Az id˝ ooszt´ asos rendszerek alacsony v´ alaszid˝ot garant´alnak. c) Az id˝ ooszt´ asos rendszerek lehet˝ ov´e teszik, hogy a CPU-t megosszuk a felhaszn´al´ok k¨oz¨ott. d) Az id˝ ooszt´ asos rendszerek az id˝ ot egyenl˝ oen osztj´ak meg a feladatok k¨oz¨ott. pont(1): 2. A rendszerh´ıv´ asok tekintet´eben melyik ´ all´ıt´ as hamis? a) A rendszerh´ıv´ as megszak´ıtja a feladat v´egrehajt´as´at, ´es az oper´aci´os rendszer egy meghat´arozott bel´ep´esi pontj´ ara ker¨ ul a´t a vez´erl´es. b) A rendszerh´ıv´ as lehet szinkron vagy aszinkron m´odon v´egrehajtva. c) A modern oper´ aci´ os rendszerekben t¨ obbnyire a CPU v´edelmi szint is megv´altozik a rendszerh´ıv´as sor´ an, pl. a CPU kernel/root m´ odba ker¨ ul a h´ıv´ as teljes´ıt´ese k¨ozben. d) A rendszerh´ıv´ assal t¨ ort´en˝ o vez´erl´es´ atad´ as ut´an a vez´erl´es mindig visszaker¨ ul a rendszerh´ıv´ast h´ıv´o programra a rendszerh´ıv´ as ut´ ani utas´ıt´ asra. pont(1): 3. Az egyszer˝ uu ¨temez´esi algoritmusokra vonatkoz´o ´all´ıt´asok k¨oz¨ ul melyik hamis? a) A FIFO u ¨temez˝ oben el˝ ofordulhat a konvojhat´as jelens´ege. b) Az SJF (Shortest Job First) u ¨temez˝ o preempt´ıv. c) Az RR (Round Robin) u ¨temez˝ o fair. d) Az SRTF (Shortest Remaining Time First) u ¨temez˝o legnagyobb probl´em´aja, hogy felt´etelezi a feladatok j¨ ov˝ obeli CPU l¨ oket´enek az el˝ ozetes ismeret´et. pont(1): 4. Az u ¨temez´es id˝ ot´ avjaival kapcsolatban melyik ´all´ıt´as igaz az al´abbiak k¨oz¨ ul? a) A hossz´ u t´ av´ uu ¨temez˝ o tipikusan k¨ otegelt (batch) feldolgoz´ast v´egz˝o rendszerekben van jelen. b) A k¨ oz´ept´ av´ u u ¨temez˝ o a CPU ´es I/O l¨ oket alapj´an k¨ ul¨onb¨oz˝o v´arakoz´asi sorokba rendezi a fut´asra k´esz feladatokat. c) A hossz´ u t´ av´ uu ¨temez˝ o c´elja az, hogy h´ att´ert´arra ´ırja azokat a folyamatokat, amelyek nem hajthat´ok v´egre hat´ekonyan a rendelkez´esre ´ all´ o mem´ ori´ aban. d) A CPU u ¨temez´es sor´ an az esem´enyre v´ ar´o feladatok k¨oz¨ ul v´alasztunk fut´asra k´esz feladatokat. pont(1):
7
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2012. janu´ ar 3.
5. Az al´ abbiak k¨ oz¨ ul melyik nem sz¨ uks´eges felt´etele a holtpont (deadlock) kialakul´as´anak? a) Az er˝ oforr´ as-foglal´ asi gr´ afban hurok/k¨ or van. b) Legyenek olyan er˝ oforr´ asok a rendszerben, amiket a feladatok csak kiz´ar´olagosan haszn´alhatnak. c) Legyen olyan folyamat, amelyik lefoglalva tart er˝oforr´asokat, mik¨ozben m´as er˝oforr´asokra v´arakozik. d) Minden folyamat addig birtokolja az er˝ oforr´asokat, am´ıg azokat saj´at maga fel nem szabad´ıtja. pont(1): 6. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik hamis a lapszervez´essel kapcsolatban? a) A lapszervez´est alkalmaz´ o rendszerekben a c´ımtranszform´aci´ot hardver v´egzi, az oper´aci´os rendszer feladata ennek a hardvernek a megfelel˝ o felprogramoz´asa. b) A lapt´ abl´ aban az ´erv´enyess´eg bitj´enek (valid bit) IGAZ ´ert´eke azt jelenti, hogy a laphoz rendelt¨ unk fizikai mem´ oriakeretet. c) Ha egy HAMIS ´ert´ek˝ u ´erv´enyess´eg bittel rendelkez˝o lapra hivatkozunk, akkor a programunk hib´aval meg´ all. d) Lapszervez´es eset´en a fizikai mem´ ori´ aban nincs k¨ uls˝o t¨ordel˝od´es. pont(1): 7. A f´ ajlok kezel´es´evel kapcsolatban megfogalmazott ´all´ıt´asok k¨oz¨ ul melyik igaz? a) A f´ ajlok l´ ancolt list´ as t´ arol´ asa eset´en a f´ajl tetsz˝oleges r´esz´enek k¨ozvetlen el´er´ese lehets´eges, ´es a m˝ uvelet komplexit´ asa nem f¨ ugg a f´ ajl m´eret´et˝ ol. b) Az indexelt t´ arol´ as egyik h´ atr´ anya, hogy a kis f´ajlok (egy blokkn´al kisebb) t´arol´as´ara is sz¨ uks´eges egy indexblokk allok´ al´ asa, vagyis kis f´ ajlok t´ arol´ asa eset´en pazarl´oan b´anik a t´arral. c) A bels˝ o t¨ ordel˝ od´es a permanens t´ aron minden esetben 0 (z´er´o) f´ajlok kezel´ese sor´an. d) Az indexelt t´ arol´ as sor´ an haszn´ alt, a f´ ajlhoz tartoz´o blokkokat megad´o t´abl´azat egy blokkot foglal el. pont(1): 8. Az al´ abbi k´et a´ll´ıt´ as k¨ oz¨ ul melyik igaz a sz´ alakra? a) A sz´ alaknak saj´ at logikai processzoruk van. b) K´et tetsz˝ oleges sz´ al k¨ oz¨ ott k¨ oz¨ os mem´ ori´ an kereszt¨ ul lehet kommunik´alni. pont(0,5):
8
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2012. janu´ ar 3.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
S1
pont(5) :
1. Az al´ abbi UML2 diagram alapj´ an – a kulcs felhaszn´al´as´aval – jellemezze az ´all´ıt´ast! A
B
+foo( )
+bar(a: A)
C
A B C D E
– – – – –
D
-inf
-rparam
+foo( )
+bar(a: A)
mindk´et tagmondat igaz ´es a k¨ovetkeztet´es is helyes mindk´et tagmondat igaz, de a k¨ovetkeztet´es hamis csak az els˝ o tagmondat igaz csak a m´ asodik tagmondat igaz egyik tagmondat sem igaz
(+ + +) (+ + –) (+ –) (– +) (– –)
D oszt´ aly´ u objektum bar(a: A) met´ odusa nem h´ıvhatja meg egy C foo( ) met´odus´at, mert az asszoci´aci´ o ir´ anya C-b˝ ol D-be mutat. pont(1): 2. A szoftverfejleszt´es ,,spir´ alis modellj´e”-nek az 1. szektor´aban mi a megoldand´o feladat? a) kock´ azatok becsl´ese b) tervez´es c) c´elok kijel¨ ol´ese d) projekt defini´ al´ asa e) fejleszt´es ´es valid´ al´ as f ) specifik´ al´ as pont(1): 3. A szoftverfejleszt´es melyik f´ azis´ anak c´elja ,,a rendszer f˝ o komponenseinek azonos´ıt´ asa ´es a k¨oz¨ott¨ uk fenn´all´o egy¨ uttm˝ uk¨od´es defini´al´asa”?
pont(1):
9
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2012. janu´ ar 3.
4. Egy u ¨gyf´el a telefont´ arsas´ agn´ al m´ odos´ıthat egy meglev˝o szolg´altat´asi szerz˝od´est, vagy u ´j k´esz¨ ul´eket v´as´ arolhat. Mindk´et funkci´ o ig´enybev´etel´ehez igazolnia (azonos´ıtania) kell mag´at. Rajzoljon UML2 use-case (haszn´ alati eset) diagramot!
pont(1): 5. Adott az al´ abbi UML2 oszt´ alydiagram. Ha mi k´esz´ıtj¨ uk a B oszt´alyt, akkor a k´et f¨ ugg˝os´eg (dependency) k¨ oz¨ ul (1 vagy 2) melyik a kedvez˝ otlenebb sz´ amunkra ´es mi´ert ?
pont(1):
10
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnik´ak
2012. janu´ ar 3.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
S2
pont(5) :
1. Adja meg k´et-h´ arom pontban, miben ´es hogyan seg´ıtenek a tervez´esi mint´ak a szoftvertervez´es sor´an! Figyelem: Ne a tervez´esi minta defin´ıci´ oj´ at adja meg!
pont(1): 2. Milyen ´ altal´ anos probl´em´ at old meg a Singleton (Egyke) tervez´esi minta?
pont(1): 3. Mutasson egy C++, Java vagy C# k´ odr´eszletet a Singleton tervez´esi minta implement´al´as´ara, ´es mutasson p´eld´ at a mint´ anak megfelel˝ o oszt´ aly haszn´ alat´ara!
pont(1):
11
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnik´ak
2012. janu´ ar 3.
4. Jellemezze az el˝ oz˝ o pontban megadott megold´ast, adja meg a megold´as kulcsgondolatait!
pont(1): 5. Adja meg r¨ oviden a webalkalmaz´ asokra vonatkoz´oan a kliensoldali szkript fogalm´at! Milyen jelleg˝ u m˝ uveleteket v´egezhet?
pont(1):
12
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Adatb´azisok
2012. janu´ ar 3.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AD
pont(5) :
1. H´ anyadik norm´ alform´ aj´ u az R(A, B, C, D, E, F ) atomi attrib´ utumokb´ol ´all´o rel´aci´os s´ema az F = {A → B, B → C, C → A, D → E, E → F, F → D} f¨ ugg´eshalmaz eset´en? pont(1): 2. Igaz-e, hogy ha minden attrib´ utum szuperkulcst´ol f¨ ugg, akkor a s´ema BCNF? pont(1): 3. Egy harangj´ at´ek-vez´erl˝ o adatb´ azis´ anak rel´ aci´os s´em´aja: DALLAM(dalc´ım, dallamsor sz´ama, u ¨tem sorsz´ ama, hangjegy sorsz´ ama, hangmagass´ ag, ritmus´ert´ek), ahol az els˝o 4 attrib´ utum ¨osszess´ege egy ¨osszetett kulcs. Rel´ aci´ oalgebrai kifejez´essel adjuk meg a harangnak a lej´atszand´o hangokat (hangmagass´ag ´es ritmus´ert´ek p´ arokat), de a harangj´ at´ek a v´ art dallam helyett ¨ osszevissza hangsort sz´olaltat meg. Mi lehet a baj?
pont(1): 4. Minimaliz´ alja az F = {D → DF, C → AB, CD → EAF, A → BA} f¨ ugg´eshalmazt!
pont(1): 5. Egy 2 000 000 rekordb´ ol ´ all´ o´ allom´ anyt szeretn´enk ,,v¨odr¨os hash” szervez´essel t´arolni. A rekordhossz 200 byte, egy blokk kapacit´ asa (a fejr´eszt nem sz´ am´ıtva) 2000 byte. A kulcsok 25 byte-osak, egy mutat´ohoz 8 byte kell. A rekordok kiolvas´ as´ ara legfeljebb 4 blokkel´er´esi id˝ot enged´elyezve sz´am´ıtsa ki, hogy legal´abb h´any byte-os lesz a hash-t´ abla! (T´etelezze fel, hogy a v¨ od¨orkatal´ogus keres´eskor mem´ori´aban tarthat´o, ´es a hash-f¨ uggv´eny egyenletesen osztja el a kulcsokat.)
pont(1):
13
