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. ´ 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
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 ) ?
Megold´ as: nem
(ii) f2 = O(f1 ) ?
Megold´ as: igen 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
Megold´ as: a 2 (mert a 2., 3., 1, 6. helynek m´ar foglaltnak kellett lenni, amikor ´erkezett, a 3 ´erkez´esekor pedig a 3. ´es 4. hely m´ ar foglalt volt. 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? n n(n + 5) Megold´ as: + 2n + n = 2 2
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
Megold´ as: a) AD, AB, BE, CE, EH, GH, EF , EI (az utols´o kett˝o lehet ford´ıtva, AB helyett lehet AE vagy DE is). b) 3 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? Megold´ as: Az u ´td´ıjakkal s´ ulyozott gr´ afon A pontb´ol egy Dijkstra-algoritmus meghat´arozza a legolcs´obb utakat. Azok a B cs´ ucsok j´ ok, melyekre a kapott ´ert´ek legfeljebb P . 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? Megold´ as: Egy ir´ any´ıtatlan gr´ af cs´ ucsai kisz´ınezhet˝oek-e 2 sz´ınnel, azaz a gr´af p´aros-e. 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! Megold´ as: Mindk´et probl´ema NP-teljes, teh´ at mindk´et ir´any´ u visszavezet´es l´etezik. 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!
Megold´ as: A G egy dag, a pontjainak egy v1 , v2 , . . . , vn topol´ogikus sorrendje meghat´arozhat´o. (2 db DFS-sel, O(|V |2 ) l´ep´esben). Ha T [i] = a vi -ben v´egz˝ od˝o utak max ´ert´eke, akkor T [1] = c1 ´es a T [i] a T [i] = ci · max{T [j] : (j, i) ∈ E} szab´ aly alapj´ an sorban meghat´ arozhat´o az i = 2, 3, . . . , n esetekre, mindegyik O(|V |) l´ep´esben. A v´ alasz maxi T [i], aminek kisz´ amol´ asa m´eg tov´abbi O(|V |) l´ep´es.
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. Megold´ as: e)
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.” Megold´ as: jam vagy zavar´ o jel vagy zajl¨ oket
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! Megold´ as: hub vagy multiport repeater vagy t¨obbportos jelism´etl˝o vagy t¨obbkaus jelism´etl˝o
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. Megold´ as: d)
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. Megold´ as: c)
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.” Megold´ as: slow start
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? Megold´ as: 200
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. Megold´ as: c)
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. Megold´ as: d)
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. Megold´ as: b)
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. Megold´ as: a)
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. Megold´ as: a)
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 FALSE ´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. Megold´ as: c)
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. Megold´ as: b)
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. Megold´ as: a)
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: ir´ anya C-b˝ ol D-be mutat.
(+ + +) (+ + –) (+ –) (– +) (– –)
A) met´ odusa nem h´ıvhatja meg egy C foo( ) met´odus´at, mert az asszoci´ aci´ o
Megold´ as: D
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 Megold´ as: c) 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”? Megold´ as: Architektur´ alis tervez´es 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! Megold´ as:
módosítás <
>
azonosítás Ügyfél <>
vásárlás
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 ?
Megold´ as: 2, mert C v´ altoz´ as´ at B-ben k¨ ovetni kell, A v´altoz´asa k¨oz¨omb¨os.
10
pont(1):
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! 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 ´ 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: C++: 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
2012. janu´ ar 3.
4. Jellemezze az el˝ oz˝ o pontban megadott megold´ast, adja meg a megold´as kulcsgondolatait! o poinMegold´ as: A Singleton oszt´ aly az instance statikus tagv´altoz´oban t´arolja az egyetlen p´eld´anyra mutat´ tert. 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. Adja meg r¨ oviden a webalkalmaz´ asokra vonatkoz´oan a kliensoldali szkript fogalm´at! Milyen jelleg˝ u m˝ uveleteket v´egezhet? Megold´ as: .
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? Megold´ as: 3NF pont(1): 2. Igaz-e, hogy ha minden attrib´ utum szuperkulcst´ol f¨ ugg, akkor a s´ema BCNF? Megold´ as: Nem
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? Megold´ as: Az eredm´eny mindig egy halmaz ´es nem egy lista, f¨ uggetlen¨ ul a lek´erdez´es m´odj´at´ol. pont(1): 4. Minimaliz´ alja az F = {D → DF, C → AB, CD → EAF, A → BA} f¨ ugg´eshalmazt!
Megold´ as: Fmin = {D → F, C → A, CD → E A → B}
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.) Megold´ as: 400 000 byte
pont(1):
13
