N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
MI
´ MEGOLDAS
Csak felv´eteli vizsga:
csak z´ar´ovizsga:
pont(45) :
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 2013. m´ ajus 28. ´ MEGOLDASOK 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
Algoritmuselm´elet
2013. m´ajus 28.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AL
´ MEGOLDAS
pont(15) :
1. Az f (n) ´es g(n) f¨ uggv´enyekr˝ ol tudjuk, hogy f (n) = O(n2 ) ´es g(n) = O(n2 ). K¨ovetkezik-e ebb˝ol, hogy van olyan c > 0 konstans, mellyel minden n-re teljes¨ ul, hogy f (n) = c · g(n)
igen — nem
|f (n)| < c · |g(n)|
igen — nem
|f (n)| > c · |g(n)|
igen — nem pont(1):
2. Egy 7 cs´ ucs´ u bin´ aris fa preorder bej´ ar´ asakor a cs´ ucsok sorrendje: A, B, C, D, E, F , G, inorder bej´ar´askor pedig: B, E, D, F , C, G, A. Rajzolja fel, hogyan n´ezhet ki a fa! Megold´ as: A B C D E
G F pont(1):
3. Az 1, 2, . . ., n sz´ amozott pontokon a G gr´ af egy olyan csillag, melynek k¨oz´eppontja az n cs´ ucs, az 1, 2, . . ., n − 1 cs´ ucsok pedig a v´egpontjai (n > 2). H´ any (nem u ¨res) r´eszfa tal´alhat´o G-ben? Megold´ as: 2n−1 + n − 1 (A k¨ oz´eppontot tartalmaz´ ok megfelelnek a v´egpontok r´eszhalmazainak; a k¨ oz´eppont n´elk¨ ul csak 1 pont´ u f´ ak vannak.)
pont(2): 4. Az al´ abbi hash-t´ abl´ an a h(x) = x (mod 11) hash-f¨ uggv´eny seg´ıts´eg´evel line´aris pr´ob´aval hajtsa v´egre a ´ ¨ OL(20), ¨ ¨ OL(7) ¨ BESZUR(3), TOR TOR m˝ uveleteket ´es jel¨olje a v´altoz´asokat! Ezek ut´an a t´abl´azat melyik mez˝ oj´eben ´er v´eget a KERES(25) m˝ uvelet? 0 3
1 23
2 2
3 14
4 4
5 16
8-ban (a l´atott ´ert´ekek: 14–2–23–3–21–x–.)
6
7 x
8
9 x
10 21 pont(2):
5. Egy nagyobb t´ arsas´ agnak aut´ obuszos kir´ andul´ast szervez¨ unk. Olyan beoszt´ast akarunk k´esz´ıteni, hogy ha X ´es Y bar´ atok, akkor ˝ ok biztos egy buszra ker¨ uljenek. Ehhez egyforma m´eret˝ u (n szem´elyes) buszok ´ allnak rendelkez´es¨ unkre, amelyekkel tudjuk, hogy a feladat megoldhat´o. Melyik ismert feladattal ´ırhat´ o le a probl´ema, ha az a c´elunk, hogy min´el kevesebb buszt haszn´aljunk? (Nem kell a beoszt´ ast elk´esz´ıteni, csak a feladatot kell megnevezni!) Megold´ as: L´ adapakol´ as (A buszok a l´ad´ak, a bar´ats´agok o¨sszef¨ugg˝o komponensei a t´argyak, m´eret¨uk: l´etsz´am/n.) pont(2):
3
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Algoritmuselm´elet
2013. m´ajus 28.
6. Egy u ´th´ al´ ozatot egy ir´ any´ıtatlan gr´ affal adtunk meg, melyben a cs´ ucsok a v´arosok, az ´elek a k¨ozt¨ uk men˝ o utak. A v´ arosok egy r´esz´en´el a v´ arosba bel´ep´eskor dug´od´ıjat kell fizetni, minden cs´ ucshoz adott, hogy ott mennyit. (Tegy¨ uk fel, hogy az utaknak nincs d´ıja.) Azt szeretn´enk meghat´arozni, hogy az A v´arosb´ol hogyan lehet u ´gy eljutni a B v´ arosba, hogy min´el kevesebbet fizess¨ unk. Milyen ismert algoritmust, milyen bemeneten futtatva lehet hat´ekonyan megoldani a probl´em´at? Megold´ as: A gr´ afb´ ol csin´ aljunk egy ir´ any´ıtott gr´afot, amiben minden ´el s´ ulya 0. Minden cs´ ucsot h´ uzzunk sz´et k´et pontt´ a, az ´ıgy keletkez˝ o ´el s´ ulya legyen a v´arosi dug´od´ıj. Ezen a gr´afon Dijkstra algoritmusa megoldja a k´erd´est. pont(2): 7. Az al´ abbi A, B, C probl´em´ ak eset´en melyik a´ll´ıt´as igaz ´es melyik nem? A : Adott egy G gr´ af, valamint adott egy k > 0 eg´esz sz´am. K´erd´es, hogy van-e G-ben legal´ abb k ´el˝ uu ´t. B : Adott egy G gr´ af, valamint adott egy k > 0 eg´esz sz´am. K´erd´es, hogy van-e G-ben legfeljebb k ´el˝ uu ´t. C : Adott egy G gr´ af. K´erd´es, hogy van-e G-ben pontosan 2013 ´elb˝ol ´all´o u ´t. a) Ha A polinomi´ alisan visszavezethet˝ o (Karp-reduk´alhat´o) C-re, akkor P = NP.
igaz — hamis
b) Ha P 6= NP, akkor A nem vezethet˝o vissza polinomi´alisan (nem Karpreduk´ alhat´ o) B-re.
igaz — hamis
c) Ha A polinomi´ alisan visszavezethet˝ o (Karp-reduk´alhat´o) C-re, akkor A polinomi´ alisan visszavezethet˝ o (Karp-reduk´ alhat´o) B-re.
igaz — hamis pont(2):
8. Javasoljon olyan adatszerkezetet k¨ onyvt´ ari k¨olcs¨onz´esek nyilv´antart´as´ahoz, amely az al´abbi n´egy m˝ uvelet mindegyik´et, n k¨ olcs¨ onz˝ o szem´ely eset´en O(log n) id˝oben megval´os´ıtja: KERES(k¨ olcs¨ onz˝ o): a szem´ely azonos´ıt´ oja alapj´an megadja az illet˝o ´altal kik¨olcs¨onz¨ott k¨onyvek azonos´ıt´ oit. Egy szem´elyn´el egyszerre legfeljebb 8 k¨ onyv lehet. ´ KINEL(k¨ onyv): a k¨ onyv azonos´ıt´ oja alapj´ an megadja a k¨olcs¨onz˝o szem´ely azonos´ıt´oj´at (ha ki van k¨olcs¨ on¨ ozve). ´ UJ(k¨ olcs¨ onz˝ o,k¨ onyv): egy u ´j k¨ olcs¨ onz´est beilleszt az adatszerkezetbe. VISSZAAD(k¨ olcs¨ onz˝ o,k¨ onyv): t¨ orli az erre a szem´elyre ´es k¨onyvre vonatkoz´o bejegyz´est. R¨ oviden v´ azolja, hogy a javasolt adatszerkezet mi´ert m˝ uk¨odik az el˝o´ırt O(log n) id˝oben. Megold´ as: K´et kiegyens´ ulyozott keres˝ of´ at (vagy 2-3 f´at) tartunk. Egyik a k¨olcs¨onz˝o azonos´ıt´oja szerint van rendezve (a cs´ ucsban t´ arolva a legfeljebb 8 kik¨olcs¨onz¨ott k¨onyv), a m´asik f´aban a k¨onyvek azonos´ıt´oja szerint van a rendez´es, egy mutat´ oval minden cs´ ucsban az els˝o fa megfelel˝o elem´ere is. ´ keres´es a m´asodik f´aban. Az UJ ´ ´es VISSZAAD egy besz´ KERES: keres´es az els˝ o f´ aban, KINEL: ur´as, illetve t¨ orl´es a m´ asodik f´ aban. Az els˝ o f´ aban, ha ez az els˝o, utols´o k¨onyve az illet˝onek, akkor egy cs´ ucs besz´ ur´ asa, t¨ orl´ese, egy´ebk´ent a megfelel˝ o cs´ ucsn´ al lev˝ o lista m´odos´ıt´asa. Az els˝ o fa n cs´ ucs´ u, O(log n) idej˝ uek a m˝ uveletei. Mivel n szem´ely eset´en legfeljebb 8n k¨onyv lehet kik¨olcs¨ on¨ ozve, a m´ asodik f´ aban a m˝ uveletek O(log(8n)) = O(log n) idej˝ uek.
pont(3):
4
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2013. m´ajus 28.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
H
´ MEGOLDAS
pont(7,5) :
Figyelem! Ha egy feladatn´ al t¨ obb helyes v´ alasz van, minden helyeset be kell jel¨ olni! 1. Mi a neve annak a sokportos eszk¨ oznek, amely jellemz˝oen azonos szabv´any´ u h´al´ozatokat vagy g´epeket k¨ ot ¨ ossze a m´ asodik r´etegben, s a kereteket igyekszik csak a sz¨ uks´eges ir´anyba tov´abb´ıtani! a) Router (´ utv´ alaszt´ o). b) Repeater (ism´etl˝ o). c) Gateway (´ atj´ ar´ o). d) Switch (kapcsol´ o). e) A fentiek k¨ oz¨ ul egyik sem a helyes elnevez´es. Megold´ as: d)
pont(1):
2. Milyen szerepet j´ atszanak az auton´ om rendszerek (AS) az Internet u ´tvonal-ir´any´ıt´as´aban? a) Megnehez´ıtik az egys´eges (konzisztens) k´ep kialak´ıt´as´at a h´al´ozatr´ol, mert belsej¨ ukben szabadon d¨ onthetnek az alkalmazott routing protokollr´ ol. b) Lehet˝ ov´e teszik a routerek sz´ am´ ara, hogy felhaszn´al´oi v´egpontok nagysz´am´ u csoportjait csak egy-egy bejegyz´esk´ent kezelj´ek az u ´tvonalt´ abl´ aikban. c) Megnehez´ıtik a gerincrouterek dolg´ at, hogy helyesen ´allap´ıts´ak meg a v´egpontok fel´e vezet˝o legalkalmasabb utat. d) Lehet˝ ov´e teszik a routing feladatok hierarchikus megoszt´as´at a vil´agm´eret˝ u h´al´ozatban. e) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. Megold´ as: b), d)
pont(1):
3. Mit jelent tartalm´ aban a Classless Inter-Domain Routing? a) Oszt´ alyn´elk¨ uli tartom´ anyk¨ ozi u ´tv´ alaszt´ ast. b) Az A, B ´es C oszt´ aly´ u c´ımek merev NetID/HostID-re val´o oszt´as´anak a megsz¨ untet´es´et. c) AS-ek (auton´ om rendszerek) k¨ oz¨ otti u ´tv´ alaszt´asi m´odszert. d) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. Megold´ as: b)
pont(1):
4. 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. Megold´ as: e)
pont(1):
5
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2013. m´ajus 28.
5. Milyen szolg´ altat´ as(oka)t nem ny´ ujt az UDP protokoll? a) Sorrendhelyes ´ atvitel b) Portkezel´es c) Torl´ od´ asvez´erl´es d) Hibav´ed˝ o k´ odol´ as a teljes UDP PDU-ra. e) A fentiek k¨ oz¨ ul az UDP mindegyik szolg´ altat´ast ny´ ujtja. Megold´ as: a), c)
pont(1):
6. Mely tev´ekenys´eg(ek) jellemzi(k) a CSMA/CD-protokollt? a) Az ´ allom´ as figyeli a csatorn´ at (,,viv˝ ot”). b) Ha az ´ allom´ as nem ´erz´ekel ad´ ast a csatorn´an, elkezdi k¨ uldeni a keretet. c) Ha kett˝ o vagy t¨ obb ´ allom´ as ad u ¨tk¨ oz´est okozva, mindegyik abbahagyja az ad´ast. ¨ oz´es ut´ d) Utk¨ an valamekkora (v´eletlen) k´esleltet´est k¨ovet˝oen az ´allom´as u ´jb´ol megk´ıs´erli az ad´ast. e) A t¨ obbi v´ alasz egyike sem helyes. Megold´ as: a), b), c), d)
pont(1):
7. Eg´esz´ıtse ki az al´ abbi mondatot: 1
,,A n´evfelold´ as az Interneten a h´ al´ ozati csom´opont neve ´es annak . . ^ . . . . c´ıme k¨oz¨ott teremt egy´ertelm˝ u kapcsolatot. Ennek megval´ os´ıt´as´at egy hierarchikus n´ev- ´es c´ımrendszer kialak´ıt´as´aval 2
a . .^ . . . . v´egzi. Ebben a hierarchikus rendszerben elvileg el˝osz¨or a rootnak megy a n´evfelold´asi 3
k´er´es, az tov´ abb´ıtja a k´er´est az aktu´ alis tartom´anyba az azt kezel˝o . . ^ . . . . -nek. A terhel´es cs¨okkent4
het˝ o p´eld´ aul szerver-replik´ aci´ oval vagy . . ^ . . . . -el´essel. Ezen ut´obbi elj´ar´as azt jelenti, hogy ha a v´egpont vagy u ¨gyn¨ oke felold egy nevet, akkor ennek az eredm´enye t´arol´asra ker¨ ul az ism´etelt k´er´esek kiszolg´ al´ as´ anak felgyors´ıt´ asa v´egett.” A hi´ anyz´ o elnevez´esek – Megold´ as: 1: IP 2: DNS 3: name server (n´evszerver) 4: cache pont(1,5):
6
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2013. m´ajus 28.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
O
´ MEGOLDAS
pont(7,5) :
Figyelem! Minden feladatn´ al csak egy helyes v´ alasz van! 1. Az al´ abbi meg´ allap´ıt´ asok k¨ oz¨ ul melyik hamis az id˝ooszt´asos (time-sharing) rendszerekre? a) Az id˝ ooszt´ asos rendszerek k¨ otegelt (batch) feladatok futtat´as´ara is k´epesek. b) Az id˝ ooszt´ asos rendszerek mindig priorit´ asosak. c) Az id˝ ooszt´ asos rendszerek kifejleszt´es´enek f˝o c´elja az volt, hogy on-line hozz´af´er´est biztos´ıtsanak a felhaszn´ al´ oknak a sz´ am´ıt´ og´epek szolg´ altat´ asaihoz. d) A rendszer v´ alaszideje fontos tulajdons´ aga az id˝ooszt´asos rendszereknek. Megold´ as: b)
pont(1):
2. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik igaz az oper´aci´os rendszerek bels˝o szerkezet´evel kapcsolatban? a) Az oper´ aci´ os rendszerek tipikusan a 7 r´eteg˝ u ISO/OSI modell szerint ´ep¨ ulnek fel. b) Az oper´ aci´ os rendszer hardverf¨ ugg˝ o r´eszei a HAL-ban (Hardware Abstraction Layer) vannak megval´ os´ıtva. c) Az oper´ aci´ os rendszer magj´ anak (kernel) f˝o feladata t¨obbek k¨oz¨ott a taszkkezel´es ´es a mem´oriakezel´es megval´ os´ıt´ asa. d) Az oper´ aci´ os rendszer ´es a rajta fut´ o alkalmaz´asok f¨ uggv´enyh´ıv´asokkal kommunik´alnak egym´assal. Megold´ as: c)
pont(1):
3. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik hamis a sz´ alra (thread)? a) A sz´ alnak saj´ at verme (stack) van. b) A sz´ al mag´ aban szekvenci´ alis k´ odot hajt v´egre. c) Egy oper´ aci´ os rendszerben l´ev˝ o k´et tetsz˝ oleges sz´al k¨oz¨ott lehets´eges a kommunik´aci´o k¨oz¨os mem´oria alkalmaz´ as´ aval. d) A sz´ alak alkalmaz´ asa lehet˝ ov´e teszi egy folyamat sz´am´ara, hogy az kihaszn´aljon t¨obb rendelkez´esre ´ all´ o v´egrehajt´ oegys´eget (sk´ al´ azhat´ os´ ag). Megold´ as: c)
pont(1):
4. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik hamis folyamatokra (process)? a) A folyamat v´egrehajt´ as alatt ´ all´ o program. b) Az oper´ aci´ os rendszeren bel¨ ul a folyamatok sz¨ ul˝o-gyermek viszonyban vannak. c) A sz¨ ul˝ o folyamat mindig kor´ abban ´ all le (termin´al´odik), mint a gyermek folyamat. d) A folyamatok elind´ıt´ asa ´es le´ all´ıt´ asa er˝ oforr´as-ig´enyes. Megold´ as: c)
pont(1):
7
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2013. m´ajus 28.
5. Az al´ abbi, holtponttal (deadlock) kapcsolatos ´all´ıt´asok k¨oz¨ ul melyik igaz? a) A holtpontban l´ev˝ o feladatok mindegyike fut´asra k´esz ´allapotban (READY) van, de nem kap CPU-t, mert az ´ alland´ oan foglalt. b) A holtpont kialakul´ as´ anak sz¨ uks´eges felt´etele az, hogy a feladatok szemaforokat haszn´aljanak a k¨ olcs¨ on¨ os kiz´ ar´ as megval´ os´ıt´ as´ ara. c) A holtpont megel˝ oz´ese sor´ an a rendszer minden er˝oforr´asig´eny kiel´eg´ıt´ese el˝ott m´erlegeli, hogy a rendszer biztons´ agos ´ allapotban marad-e. d) A holtpont megel˝ ozhet˝ o, ha ez er˝ oforr´ asokat sorsz´amozzuk, ´es azokat az azok´ert verseng˝o folyamatok csak a sorsz´ amuk sorrendj´eben foglalj´ ak le. Megold´ as: d)
pont(1):
6. Az al´ abbi, a lapszervez´essel kapcsolatos k´erd´esek k¨oz¨ ul melyik hamis? a) A lapszervez´es sor´ an a fizikai mem´ ori´ at azonos m´eret˝ u fizikai mem´oriakeretekre osztjuk. b) A lapt´ abl´ at is a fizikai mem´ ori´ aban t´ aroljuk t¨obbnyire. c) A lapszervez´es eset´en nincs bels˝ o t¨ ordel˝ od´es. d) Az ´erv´enyess´eg (valid) bit a lapt´ abl´ aban azt jelzi, hogy az adott laphoz rendeltek-e fizikai mem´oria keretet. Megold´ as: c)
pont(1):
7. Az al´ abbi, az a´llom´ anyok permanens t´ aron t¨ort´en˝o t´arol´as´aval kapcsolatos ´all´ıt´asok k¨oz¨ ul melyik igaz? a) A permanens t´ aron a fizikai inform´ aci´ ot´ arol´as egys´ege a f´ajl. b) A l´ ancolt list´ as t´ arol´ as t´ amogatja az egy f´ajlon bel¨ uli inform´aci´o gyors k¨ozvetlen el´er´es´et. c) Az indexelt t´ arol´ as eset´en a f´ ajl egy r´esz´enek t´arol´as´ara szolg´al´o blokk t´arol´okapacit´as´anak egy r´esz´et a f´ ajl k¨ ovetkez˝ o r´eszeit tartalmaz´ o blokk azonos´ıt´ as´ara haszn´aljuk (indexelj¨ uk). d) Az indexelt t´ arol´ as eset´en az egy f´ ajlhoz tartoz´o index blokkok sz´am´at nem tudjuk el˝ore, ´ıgy biztos´ıtani kell egy f´ ajlhoz tartoz´ o index blokkok sz´ am´ anak n¨ovel´es´et ´es cs¨okkent´es´et. Megold´ as: d)
pont(1):
8. Az al´ abbi k´et a´ll´ıt´ as k¨ oz¨ ul melyik igaz? a) A legr´egebbi lap (FIFO) algoritmus lapcsere strat´egia alkalmaz´asa sor´an a fizikai mem´oriakeretek sz´ am´ anak n¨ ovel´ese n¨ ovekv˝ o laphiba gyakoris´ agot eredm´enyez (B´el´ady-anom´alia). b) A legr´egebben nem haszn´ alt (LRU) lapcsere strat´egia k¨ozel´ıti meg legjobban a optim´alis algoritmus, de a megval´ os´ıt´ asa neh´ez, ez´ert annak csak k¨ ozel´ıt´eseit szokt´ak a gyakorlatban alkalmazni. Megold´ as: a)
pont(0,5):
8
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2013. m´ajus 28.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
S1
´ MEGOLDAS
pont(5) :
1. Az al´ abbi UML2 diagram alapj´ an – a kulcs felhaszn´al´as´aval – jellemezze az ´all´ıt´ast!
A B C D E
– – – – –
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 megh´ıvhatja egy C foo( ) met´odus´at, mert D ¨or¨okli az A-ra ir´ any´ıtott asszoci´ aci´ ot B-t˝ ol. Megold´ as: C
pont(1):
2. Nevezzen meg egy dinamikus verifik´ aci´ os technik´at! Megold´ as: tesztel´es pont(1): 3. A szoftverfejleszt´es melyik f´ azis´ anak c´elja ,,a k¨ovetelm´enyeket kiel´eg´ıt˝o rendszer magas absztrakci´os szint˝ u form´ alis le´ır´ asa”? Megold´ as: specifik´ aci´ o pont(1):
9
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2013. m´ajus 28.
4. Izidor ´ır egy szerelemes SMS-t, amit elk¨ uld Emerenci´anak. Emerencia az SMS-t azonnal n´egyszer elolvassa. Rajzoljon UML2 kommunik´ aci´ os diagramot! Megold´ as:
pont(1): 5. Defini´ alja UML2-ben az al´ abbi felsorol´ ast (enumer´aci´o)! Franciak´ artya = [treff | k´ar´o | k˝or | pikk] Megold´ as:
pont(1):
10
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnik´ak
2013. m´ajus 28.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
S2
´ MEGOLDAS
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! Megold´ as: – N¨ ovelik a rendszer karbantarthat´ os´ ag´ at, m´odos´ıthat´os´ag´at; – n¨ ovelik az egyes r´eszek u ´jrafelhaszn´ alhat´ os´ag´at; – seg´ıtenek megtal´ alni a nem magukt´ ol ´ertet˝od˝o oszt´alyokat. pont(1): 2. Milyen k´et ´ altal´ anos probl´em´ at old meg a Singleton (Egyke) tervez´esi minta? Megold´ as: Kik´enyszer´ıti, hogy egy adott oszt´alyb´ol csak egyetlen objektumot lehessen l´etrehozni, ´es ehhez glob´ alis hozz´ af´er´est biztos´ıt.
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! Megold´ as: Egyszer˝ u C++ nyelv˝ u megold´ as: class Singleton { public: static Singleton* Instance() { if (_instance == 0) { _instance = new Singleton; } return _instance; } void Print() { … } protected: Singleton() {;} private: static Singleton* _instance; }; Singleton* Singleton::_instance = NULL;
P´elda haszn´ alatra: int main() { Singleton::Instance()->Print(); … }
pont(1):
11
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnik´ak
2013. m´ajus 28.
4. Jellemezze az el˝ oz˝ o pontban megadott megold´ast, adja meg a megold´as kulcsgondolatait! Megold´ as: A Singleton oszt´ aly az instance statikus tagv´altoz´oban t´arolja az egyetlen p´eld´anyra mutat´o pointert. Ennek kezdeti ´ert´eke NULL. Az egyetlen p´eld´ anyhoz hozz´af´erni az Instance statikus tagf¨ uggv´ennyel lehet. Els˝ o h´ıv´ askor ez l´etrehozza az u ´j objektumot, ´es elt´arolja az instance tagban. A k´es˝obbi h´ıv´asok sor´an m´ ar ezzel t´er vissza. Az oszt´ aly konstruktora v´edett (protected), ´ıgy garant´alt az, hogy k´ıv¨ ulr˝ol, az Instance tagf¨ uggv´eny megker¨ ul´es´evel ne lehessen tov´ abbi p´eld´ anyokat l´etrehozni. Az egyetlen p´eld´anyhoz a glob´alis hozz´af´er´est az Instance statikus tagf¨ uggv´eny biztos´ıtja.
pont(1): 5. Mutasson p´eld´ at ASP.NET inline script alkalmaz´as´ara! A HTML r´eszeket is adja meg! Megold´ as: P´elda 5 faktori´ alis´ anak kisz´ am´ıt´ as´ara ´es az aktu´alis szerverid˝o ki´ır´as´ara: <%@ Page Language="C#" %>
pont(1):
12
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
2013. m´ajus 28.
Adatb´azisok
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AD
´ MEGOLDAS
pont(5) :
1. Mit garant´ alhat a rel´ aci´ os s´em´ ak normaliz´ al´ ason alapul´o s´ematervez´esi m´odszere? a) Az adatb´ azis konzisztenci´ aj´ at.
b) Egyes adatb´azis-m˝ uveletek v´alaszidej´et.
c) Rekurzi´ omentes adatb´ azis-lek´erdez´eseket.
d) A rel´aci´ok redundanciamentess´eg´et.
e) A fizikai adatb´ azis egyszer˝ u karbantarthat´os´ag´at. Megold´ as: b)
pont(1):
2. Melyik rel´ aci´ os s´emafelbont´ asnak nincs gyakorlati jelent˝os´ege? a) F¨ ugg˝ os´eg˝ orz˝ o, vesztes´egmentes, r´eszs´em´ ak nem BCNF-ek. b) F¨ ugg˝ os´eg˝ orz˝ o, nem vesztes´egmentes, r´eszs´em´ak BCNF-ek. c) Nem f¨ ugg˝ os´eg˝ orz˝ o, vesztes´egmentes, r´eszs´em´ak BCNF-ek. Megold´ as: b)
pont(1):
3. Egy adatb´ azisban 16 milli´ o rekord k¨ oz¨ ott kell a keres´est t´amogatni a rekord egyedis´eget biztos´ıt´o kulcs´ert´eke alapj´ an. Mekkora legyen legal´ abb a v¨ odr¨ os hash v¨od¨orkatal´ogus´anak m´erete (byte-ban), ha a keres´eshez rendelkez´esre ´ all´ o id˝ o 1 msec? A rekordok 250 byte-osak, egy blokk nett´o m´erete 4000 byte, minden kulcs 30 byte, a mutat´ ok 4 byte-osak, az ´ atlagos blokkel´er´esi id˝o 1 msec. A v¨od¨orkatal´ogus bef´er a mem´ori´aba, a hash-f¨ uggv´eny egyenletesen sz´ or. Megold´ as: 4 milli´ o byte
pont(1):
4. Vizsg´ alja meg a t´ abl´ azatos teszttel az R(ABCDEF ) s´ema R1(ABC), R2(CDE), R3(ABF D), R4(EAD) felbont´ as´ at az F = {AB → CDE, B → F A, CD → BE, E → AD, EF → A} f¨ ugg´eshalmaz mellett! Megold´ as: vesztes´egmentes
pont(1):
5. Egy rel´ aci´ os adatb´ azis tervez´es´ehez mintaadatokat kaptunk az egyik t´abl´ab´ol, ld. al´abb. A k¨ ul¨onb¨oz˝ o k´ odok garant´ altan k¨ ul¨ onb¨ oz˝ o ´ert´ekeket jel¨ olnek. Vizsg´ alja meg, hogy biztosan igazak-e az R(ABCD) s´em´an a funkcion´alis f¨ ugg˝os´egekre vonatkoz´o k¨ovetkez˝ o ´ll´ıt´ a asok: A a1 a1 a2 a2 A→B
igaz — nem igaz
B 6→ C
igaz — nem igaz
BC → D
igaz — nem igaz
B b1 b1 b2 b2
C c1 c2 c1 c2
D d1 d2 d2 d1
pont(1):
13
