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¨ okinformatikus szak BME Villamosm´ ern¨ oki ´ es Informatikai Kar 2015. m´ ajus 27. ´ 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.
Specializ´ aci´ ov´ alaszt´ as (Csak felv´eteli vizsga eset´en kell kit¨olteni)
K´erem, a t´ uloldalon tal´ alhat´ o t´ abl´ azatokban jel¨olje meg, mely f˝o-, illetve mell´ekspecializ´aci´on k´ıv´anja tanulm´ anyait folytatni. FIGYELEM! A f˝ o- ´es mell´ekspecializ´ aci´okat k¨ ul¨on-k¨ ul¨on kell sorrendbe ´all´ıtani!
1
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
2015. m´ajus 27.
F˝ ospecializ´ aci´ o v´ alaszt´ asa (Csak felv´eteli vizsga eset´en kell kit¨olteni)
A t´ abl´ azatban a f˝ ospecializ´ aci´ o neve mellett sz´ammal jel¨olje a sorrendet: 1-es sz´am az els˝o helyen kiv´alasztott specializ´ aci´ ohoz, 2-es a m´ asodik helyen kiv´ alasztotthoz tartozik stb. Nem kell az ¨osszes f˝ospecializ´aci´o mell´e sz´ amot ´ırni, de legal´ abb egy f˝ ospecializ´ aci´ ot jel¨ olj¨ on meg.
F˝ ospecializ´ aci´ o
sorrend
Alkalmazott informatika (AUT) Internetarchitekt´ ura ´es szolg´altat´asok (TMIT) Kritikus rendszerek (MIT) Mobil h´ al´ ozatok ´es szolg´altat´asok integr´aci´oja (HIT) Vizu´ alis informatika (IIT)
Mell´ ekspecializ´ aci´ o v´ alaszt´ asa (Csak felv´eteli vizsga eset´en kell kit¨olteni)
A t´ abl´ azatban a mell´ekspecializ´ aci´ o neve mellett sz´ammal jel¨olje a sorrendet: 1-es sz´am az els˝o helyen kiv´alasztott specializ´ aci´ ohoz, 2-es a m´ asodik helyen kiv´ alasztotthoz tartozik stb. Nem kell az ¨osszes mell´ekspecializ´aci´ o mell´e sz´ amot ´ırni, de legal´ abb egy mell´ekspecializ´ aci´ ot jel¨olj¨on meg.
Mell´ ekspecializ´ aci´ o Adat- ´es m´ediainformatika (TMIT) IT biztons´ag (HIT) IT rendszerek fizikai v´edelme (HVT) Intelligens rendszerek (MIT) Mobilszoftver-fejleszt´es (AUT) Sz´ am´ıt´ aselm´elet (SZIT) Sz´ am´ıt´ asi felh˝ ok ´es p´arhuzamos rendszerek (IIT)
2
sorrend
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Algoritmuselm´elet
2015. m´ajus 27.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AL
´ MEGOLDAS
pont(15) :
√ 1. Legyen f (n) = 2015n n + 3n2 log n + 132n(log n)3 . Melyik az a legkisebb pozit´ıv eg´esz d sz´am, melyre f (n) = O(nd ) ? Megold´ as: d = 3
pont(1):
2. Az al´ abbi 11 m´eret˝ u hash-t´ abl´ aban line´ aris pr´ob´at ´es a h(x) = x (mod 11) hash-f¨ uggv´enyt haszn´aljuk. Az X-ek azokat a helyeket jel¨ olik, ahonnan kor´ abban m´ar t¨or¨olt¨ unk elemet. 0 X
1 34
2 X
3
4 38
5 X
6 6
7
8 X
9 20
10 X
Melyik mez˝ oben ´er v´eget a KERES(12) m˝ uvelet? Megold´ as: A 7-ben.
pont(1):
3. A G gr´ af cs´ ucshalmaza V = {a1 , a2 , . . . , an , b1 , b2 , . . . , bn , c}. A gr´afban minden 1 ≤ i, j ≤ n eset´en ai ´es bj ¨ ossze van k¨ otve ´ellel, valamint c-b˝ ol megy ´el az ¨ osszes t¨obbi cs´ ucshoz (m´as ´el nincs a gr´afban). Hat´arozza meg, h´ any olyan 4 hossz´ u k¨ or van a gr´ afban, amely ´ atmegy a c cs´ ucson! Megold´ as: 2 ·
n 2
· n = n3 − n2 pont(2):
4. Az al´ abbi gr´ afon a m´elys´egi bej´ ar´ ast az A cs´ ucsb´ol indulva u ´gy hajtjuk v´egre, hogy amikor t¨obb lehet˝ os´eg van, akkor mindig az ´ ab´ec´e sorrend szerinti els˝ot v´alasztjuk. Adja meg a bej´ar´as sor´an megkapott m´elys´egi ´es befejez´esi sz´ amokat, tov´ abb´ a a gr´ afnak egy topologikus sorrendj´et (ha van ilyen)! Megold´ as: A B C A B C D E F G D
E
F
G
m´elys´egi sz´am
1
2
5
3
4
6
7
befejez´esi sz´am
4
1
7
3
2
6
5
Topologikus sorrend: C, F , G, A, D, E, B (a bef. sz´amokb´ol, de m´ask´ent a G az A, D, E k¨oz¨ott b´arhol lehet) pont(2):
5. A G = (V, E) ir´ any´ıtatlan, egyszer˝ u, ¨ osszef¨ ugg˝o gr´af ´elei s´ ulyozottak. Jel¨olje F a G gr´af egy minim´alis s´ uly´ u fesz´ıt˝ of´ aj´ at ´es legyen u, v ∈ V k´et tetsz˝ oleges cs´ ucsa a gr´afnak. Igaz-e, hogy az u ´es v cs´ ucsokat az F f´ aban osszek¨ ¨ ot˝ ou ´t mindig egyben egy u-t ´es v-t ¨ osszek¨ot˝o minim´alis s´ uly´ uu ´t a G gr´afban? V´alasz´at r¨oviden indokolja is! Megold´ as: Nem, pl. G egy h´ aromsz¨ og, k´et ´el s´ ulya 2, egy ´el´e 3.
pont(2):
3
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Algoritmuselm´elet
2015. m´ajus 27.
6. Legyen G = (V, E) egy egyszer˝ u, ir´ any´ıtatlan gr´af. A T tulajdons´ag jelentse a k¨ovetkez˝ot: Vannak olyan X1 , X2 , X3 ⊆ V halmazok, melyekre • X1 ∪ X2 ∪ X3 = V , • Xi ∩ Xj = ∅ ha i 6= j • ha {a, b} ∈ E ´es a ∈ Xi , b ∈ Xj , akkor i 6= j Fogalmazza meg, milyen ismert gr´ aftulajdons´agot ´ır le T ! Megold´ as: A gr´ af 3 sz´ınnel sz´ınezhet˝ o. pont(2): 7. Tekints¨ uk a k¨ ovetkez˝ o eld¨ ont´esi probl´em´ akat! Adott A: B: C:
egy G egyszer˝ u ir´ any´ıtatlan gr´ af ´es k, ` ≥ 0 eg´esz sz´amok. Van G-nek k cs´ ucsb´ ol ´ all´ o ´es legal´ abb ` ´elet tartalmaz´o r´eszgr´afja? Van G-nek k cs´ ucsb´ ol ´ all´ o ´es pontosan ` ´elet tartalmaz´o r´eszgr´afja? Van G-nek k cs´ ucsb´ ol ´ all´ o ´es legfeljebb ` ´elet tartalmaz´o r´eszgr´afja?
Ha P 6= NP, akkor igaz-e hogy A Karp-reduk´ alhat´ o (polinomi´ alisan visszavezethet˝o) C-re.
igen – nem
C Karp-reduk´ alhat´ o (polinomi´ alisan visszavezethet˝o) A-ra
igen – nem
A Karp-reduk´ alhat´ o (polinomi´ alisan visszavezethet˝o) B-re
igen – nem pont(2):
8. Egy v´ aros bicikli´ utjait a G = (V, E) ir´ any´ıtott gr´af ´ırja le, melyben a csom´opontokat jel¨olik a gr´af cs´ ucsai. A gr´ af ´elei a megfelel˝ ou ´tszakaszok megt´etel´ehez sz¨ uks´eges id˝ovel vannak s´ ulyozva. Jelenleg azonban a csom´opontok egy adott A ⊂ V halmaz´ an´ al ´ atalak´ıt´ asok t¨ ort´ennek, ami egy x ∈ A csom´oponton val´o ´athalad´as idej´et a kor´ abban 0-nak tekinthet˝ o id˝ or˝ ol adott t(x) id˝ ore v´ altoztatja (f¨ uggetlen¨ ul att´ol, onnan merre megy¨ unk tov´abb). Azt szeretn´enk megtudni, hogy ilyen felt´etelek mellett hogyan tudunk leggyorsabban eljutni egy adott a ∈ V pontb´ ol egy adott b ∈ V pontba. (Feltehet˝ o, hogy a, b 6∈ A.) Milyen ismert algoritmust haszn´ alna a feladat megold´as´ara ´es azt milyen bemeneten kellene futtatni? Mennyi lesz az ´ıgy kapott elj´ ar´ as l´ep´essz´ ama?
Megold´ as: M´ odos´ıtott G0 gr´ af: minden A-beli x cs´ ucsot sz´eth´ uzunk, az xbe cs´ ucsba j¨onnek az ´elek, az xki cs´ ucsb´ol mennek tov´ abb, az (xbe , xki ) ir´ any´ıtott ´el s´ ulya t(x). Ebben a gr´afban egy Dijkstra az a (vagy aki ) cs´ ucsb´ol megadja a b-be (bbe -be) a legr¨ ovidebb utat. G0 cs´ ucsainak sz´ ama |V | + |A| ≤ 2|V |, a l´ep´essz´am – m´atrixos megad´asn´al – O(|V |2 ).
pont(3):
4
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2015. m´ajus 27.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
H
´ MEGOLDAS
pont(7,5) :
1. Mit tartalmaz egy HTTP-v´ alasz az al´ abbiak k¨oz¨ ul? ´ a) Allapotk´ odot. b) Az eredeti k´er´est. c) A b¨ ong´esz˝ o nev´et, hogy kliens oldalon annak lehessen eljuttatni. d) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. Megold´ as: a)
pont(1):
2. Az al´ abbiak k¨ oz¨ ul mely ´ all´ıt´ as(ok) igaz(ak) az Address Resolution Protocol-ra (ARP)? a) Ha ismerj¨ uk az adatkapcsolati c´ımet, akkor seg´ıts´eg´evel ki lehet der´ıteni a hozz´a tartoz´o IP-c´ımet. b) A h´ al´ ozati ´es a sz´ all´ıt´ asi r´eteg k¨ oz¨ otti kapcsolatot teremti meg. c) M˝ uk¨ od´ese sor´ an haszn´ al broadcast c´ımz´est. d) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. Megold´ as: c)
pont(1):
3. Egy adott id˝ opontban a h´ al´ ozat ¨ ot csom´ opontja a k¨ovetkez˝o ´allapotvektorokat tartja nyilv´an: A B C D E
B, 1 A, 1 B, 1 C, 1 B, 1
C, 1 D, 1 E, 1 D, 1
D, 2
E, 1
F, 2
G, 1
F, 1
B mely csom´ opont(ok)on kereszt¨ ul fog F -nek csomagot k¨ uldeni a fenti t´abla alapj´an, ha a Bellman–Fordalgoritmust alkalmazza? Megold´ as: Az E-n.
pont(1):
4. Eg´esz´ıtse ki az al´ abbi mondatot: Az auton´ om rendszer egy olyan h´ al´ ozatr´esz, amelyen bel¨ ul egys´eges routing m´odszert alkalmaznak. Ezek k¨ oz¨ ott az EGP csoportba tartoz´ o routing protokollokat haszn´alhatjuk, melyeknek leggyak rabban haszn´ alt v´ altozata a . . . . . . . . . . . . . . . . . . . . . . . . . . Megold´ as: BGP
pont(1):
5. Eg´esz´ıtse ki az al´ abbi mondatot: A TCP-ben haszn´ alt AIMD (Additive Increase Multiplicative Decrease) torl´od´asvez´erl´esi m´odszer egyik kieg´esz´ıt´ese a . . . . . . . . . . . . . . . . . . . . . . . . . , ahol az ¨osszek¨ottet´es kezdet´en a sebess´eg exponenci´ alis n¨ ovel´ese t¨ ort´enik a torl´ od´ aselker¨ ul´esi korl´atig vagy az els˝o csomagveszt´es bek¨ovetkezt´eig. Megold´ as: slow start
pont(1):
5
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2015. m´ajus 27.
6. Az otthoni felhaszn´ al´ asra sz´ ant ,,ADSL router” megnevez´essel forgalomba ker¨ ul˝o eszk¨oz¨ok tipikusan 192.168.1.xes (mag´ an) IP-c´ımeket szoktak kiosztani az otthoni h´al´ozaton tal´alhat´o sz´am´ıt´og´epeknek. Mely technika teszi lehet˝ ov´e, hogy ezek m´egis tudnak internetezni? Megold´ as: NAT (Network Address Translation)
pont(1):
7. Az A ´es B v´egpont k¨ oz¨ otti kommunik´ aci´ o sor´an az A v´egpont ´altal k¨ uld¨ott utols´o 4 szegmens TCP PDU-j´ aban a sorsz´ am (sequence number) 213, 287, 311, 356. B v´alaszk´ent k¨ uld¨ott 4 szegmens TCP PDU-j´aban az ACK-sz´ am 311, 311, 311, 311. Erre v´ alaszk´ent az A terminal h´any b´ajtos szegmenst fog k¨ uldeni fast retransmit eset´en, amennyiben nem j´ art m´eg le a time-out id˝ o? Megold´ as: 45
pont(1,5):
6
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2015. m´ajus 27.
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 ´ all´ıt´ asok k¨ oz¨ ul melyik hamis az oper´aci´os rendszerek fel´ep´ıt´es´evel kapcsolatban? a) Az oper´ aci´ os rendszer maga is egy program. b) Az oper´ aci´ os rendszer feladata a kapcsol´ od´o be- ´es kimeneti eszk¨oz¨ok kezel´ese, azokhoz a felhaszn´al´ oi programok nem f´ernek hozz´ a direkt m´ odon. c) Az oper´ aci´ os rendszer magja kezeli a feladatokat ´es a mem´ori´at. d) Csak az eszk¨ ozkezel˝ ok tartalmaznak hardwarespecifikus k´odot az oper´aci´os rendszerekben. Megold´ as: d) (Minden oper´aci´os rendszerben a kernelnek is van egy HW specifikus interface-e, amit t¨obbnyire HAL-nak pont(1):
(Hardware Abstraction Layer) h´ıvunk. )
2. Az al´ abbi meg´ allap´ıt´ asok k¨ oz¨ ul melyik hamis az u ¨temez´esi algoritmusok jellemz´es´ere haszn´alt m´ert´ekekre? a) Az ´ atbocs´ ajt´ o k´epess´eg m´ert´ekegys´ege az 1/s vagy job/s. b) Az ´ atlagos v´ arakoz´ asi id˝ o mindig nagyobb, mint az ´atlagos k¨or¨ ulfordul´asi id˝o. c) A k¨ ozponti egys´eg kihaszn´ alts´ aga nem lehet 100%-n´al t¨obb egyprocesszoros rendszerben. d) A kihaszn´ alts´ ag sz´ am´ıt´ asa sor´ an figyelmen k´ıv¨ ul kell hagyni a rendszerfeladatok ´altal elhaszn´alt processzorid˝ ot. Megold´ as: b) (a v´arakoz´asi id˝o mindig kisebb, mint a k¨or¨ulfordul´asi id˝o, hiszen az ut´obbi tartalmazza a feladat fut´asi pont(1):
idej´et is (mindig nagyobb). )
3. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik hamis az egyszer˝ uu ¨temez´esi algoritmusokkal (FIFO, RR, SJF, SRTF) kapcsolatban? a) A FIFO algoritmus nem preempt´ıv. b) Az RR algoritmus preempt´ıv. c) Az SJF algoritmus preempt´ıv. d) Az SRTF algoritmus preempt´ıv. Megold´ as: c) (az SJF nem preempt´ıv, b´ar priorit´asos.)
pont(1):
4. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik igaz a feladatok tipikus ´allapot-´atmeneti diagramj´aval kapcsolatban? ´ ´allapotba ker¨ a) Ha egy er˝ oforr´ asra v´ ar´ o feladat megkapja az er˝oforr´ast, akkor FUTO ul. ´ ´ b) VARAKOZO ´ allapotban a feladatok akt´ıvan v´arnak az esem´enyre. ´ ´ ´ feladatot. c) A FUTASRA KESZ feladatok k¨ oz¨ ul a k¨ oz´ept´av´ uu ¨temez˝o v´alasztja ki a FUTO ´ d) Csak FUTO ´ allapotban l´ev˝ o feladat ´ all´ıthatja le mag´at programozottan, pl. az exit() rendszerh´ıv´assal. Megold´ as: d) (Futnia kell, hogy v´egre tudja hajtani a rendszerh´ıv´ast.)
7
pont(1):
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2015. m´ajus 27.
5. 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 tartalmazhat coroutine-okat, amelyek futhatnak p´arhuzamosan a sz´alon bel¨ ul. c) Egy oper´ aci´ os rendszerben csak egy adott folyamat kontextus´aban fut´o k´et sz´al k¨oz¨ott lehets´eges a kommunik´ aci´ o k¨ oz¨ os mem´ oria alkalmaz´ as´ aval. d) Egy folyamathoz tartozik legal´ abb egy sz´al. Megold´ as: b) (A corutin kooperat´ıv eszk¨oz, nem tesz lehet˝ov´e p´arhuzamos fut´ast, a sz´al mag´aban szekvenci´alis.) pont(1): 6. Mely ´ all´ıt´ as igaz a szemaforokkal kapcsolatban? a) A szemafor akt´ıvan v´ ar az er˝ oforr´ as felszabadul´as´ara a modern oper´aci´os rendszerekben. b) A V( ) m˝ uvelettel szabad´ıtjuk fel a szemaforral v´edett er˝oforr´ast. c) K¨ olcs¨ on¨ os kiz´ ar´ as megval´ os´ıt´ as´ ahoz haszn´alt bin´aris szemafort foglalt (0) ´ert´ek˝ ure kell inicializ´alni. d) Sz´ aml´ al´ o t´ıpus´ u szemafor haszn´ alata eset´en egy t¨obbp´eld´anyos er˝oforr´ast egyenk´ent, de t¨obb p´eld´ anyban lefoglalva (pl. for( ) ciklussal) helyesen m˝ uk¨ od˝o programot kapunk. Megold´ as: b)
pont(1):
7. Az al´ abbi virtu´ alis t´ arkezel´essel kapcsolatos ´all´ıt´asok k¨oz¨ ul melyik hamis? a) A virtu´ alis t´ arkezel´es eset´en van bels˝ o t¨ ordel˝od´es a fizikai mem´ori´aban. b) A virtu´ alis t´ arkezel´es fizikai mem´ ori´ aban tal´alhat´o lap eset´en nem befoly´asolja sebess´eg szempontj´ ab´ ol a mem´ oria alrendszer m˝ uk¨ od´es´et, az ugyanolyan gyors, mintha statikus (pl. ford´ıt´asi idej˝ u) c´ımlek´epz´est haszn´ aln´ ank. c) A virtu´ alis t´ arkezel´es alapja a lapszervez´es. d) A virtu´ alis t´ arkezel´es lehet˝ ov´e teszi a rendelkez´esre ´all´o fizikai mem´ori´an´al nagyobb programok futtat´ as´ at. Megold´ as: b) (mivel a lapt´abl´at (vagy minimum a TLB-t, ha van) ´es ut´ana a t´enyleges adatot tartalmaz´o mem´ori´at is el kell ´erni, m´ıg a m´ asik esetben direkt c´ımz´es haszn´ alhat´ o, ami j´ oval gyorsabb.)
pont(1):
8. Az al´ abbi k´et ´ all´ıt´ as k¨ oz¨ ul melyik igaz a permanens t´aron az egyes f´ajlokhoz tartoz´o blokkok azonos´ıt´as´ ara (allok´ aci´ os strat´egia) szolg´ al´ o megold´ asokkal kapcsolatban? a) A l´ ancolt t´ arol´ as eset´en a f´ ajl egy blokkj´anak meghib´asod´asa eset´en r´eszben el´erhetetlenn´e v´alik a f´ ajlban t´ arolt inform´ aci´ o. b) Az indexelt t´ arol´ as eset´en a f´ ajl egy blokkj´anak meghib´asod´asa eset´en el´erhet˝o a teljes f´ajlban t´arolt inform´ aci´ o. Megold´ as: a) (A b) az´ert hamis, mert az indexelt t´arol´as eset´en csak az index blokkokat replik´ajuk, vagyis mag´aban a f´ ajl blokkj´ anak a meghib´ asod´ asa adatveszt´essel j´ ar.) pont(0,5):
8
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2015. m´ajus 27.
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
(+ + +) (+ + –) (+ –) (– +) (– –)
A-nak a bar( ) met´ odusa nem p´eld´ anyos´ıthat D t´ıpus´ u objektumot, mert D nem f¨ ugg A-t´ol. Megold´ as: B
pont(1):
2. Adott az al´ abbi UML2 oszt´ alydiagram
Az al´ abbi Java sorok k¨ oz¨ ul melyik megold´ assal implement´aln´a a min˝os´ıt˝ot (qualifier-t) a) private taj Beteg; b) private Map<String, Beteg> b; c) private taj String; d) private String taj(Beteg b); Megold´ as: b)
pont(1):
9
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2015. m´ajus 27.
3. Mi a refaktor´ al´ as?
Megold´ as: A szoftvert u ´gy fejlesztj¨ uk tov´ abb, hogy a k¨ uls˝o viselked´es v´altozatlan marad, de a bels˝o szerkezet meg´ ujul.
pont(1):
4. Egy met´ odus megh´ıv´ asakor azt tapasztalja, hogy s´er¨ ultek az el˝ofelt´etelek (precondition). Hol keresn´e a hib´ at? a) a h´ıv´ oban b) a h´ıvottban c) a virtu´ alis g´epben Megold´ as: a)
pont(1):
5. Adott az al´ abbi UML2 ´ allapotg´ep (state chart).
Jel¨ olje meg, hogy a kezd´es ut´ an az a, u, b, z, a, v esem´enyszekvencia hat´as´ara melyik lesz a kialakul´o v´eg´ allapot: C
D
E
E
F
G
J pont(1):
10
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
2015. m´ajus 27.
Szoftvertechnik´ak
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
S2
´ MEGOLDAS
pont(5) :
1. Egy-k´et mondatban adja meg, milyen ´ altal´ anos probl´em´at old meg a Proxy (helyettes) tervez´esi minta? Megold´ as: Helyettes´ıt˝ o objektumot vezet be, amely transzparens m´odon szab´alyozza az eredeti objektumhoz val´o hozz´ af´er´est. pont(1): 2. Milyen ´ altal´ anos probl´em´ at old meg az Observer (Megfigyel˝o) tervez´esi minta? Megold´ as: Lehet˝ ov´e teszi, hogy egy objektum a megv´ altoz´asa eset´en ´ertes´ıteni tudjon tetsz˝oleges m´as objektumokat an´elk¨ ul, hogy b´ armit is tudna r´ oluk.
pont(1):
3. Rajzolja fel az Observer minta oszt´ alydiagramj´at, ´es jellemezze r¨oviden az oszt´alydiagramon szerepl˝o oszt´ alyokat! Megold´ as:
Subj ect +observers Attach() Detach() Notify()
0..*
Observer <
> Update()
Notify() { for each o in observers o->Update(); }
ConcreteSubject subjectState
ConcreteObserver
+subject
observerState
GetState() SetState()
Update()
Update() { observerState = subj ect->GetState(); }
GetState() { return subjectState(); }
Subject : T´ arolja a beregisztr´ alt Observer-eket. Observer: Interf´eszt defini´ al azon objektumok sz´am´ara, amelyek ´ertes¨ ulni szeretn´enek a Subject-ben bek¨ ovetkezett v´ altoz´ asr´ ol. ConcreteSubject: Az observer-ek sz´ am´ ara ´erdekes ´allapotot t´arol, ´es ´ertes´ıti a beregisztr´alt observer-eket, amikor az ´ allapota megv´ altozik. ConcreteObserver: Referenci´ at t´ arol a megfigyelt ConcreteSubject objektumra, implemet´alja az Observer interf´esz´et (Update m˝ uvelet). pont(1):
11
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnik´ak
2015. m´ajus 27.
4. Egy UML szekvenciadiagram seg´ıts´eg´evel mutassa be az Observer minta oszt´alyainak egy¨ uttm˝ uk¨od´es´et! Megold´ as:
A lesz´ armazott ConcreteObserverek az Update f¨ uggv´eny fel¨ ul´ır´as´aval ´ertes¨ ulnek a Subject v´altoz´asair´ol. Ilyenkor lek´erik a ConcreteSubject ´ allapot´ at, ´es reag´alnak a v´altoz´asra. Ha az egyik Observer v´altoztatja meg a ConcreteSubject ´ allapot´ at, akkor a Notify f¨ uggv´eny megh´ıv´as´aval ´ertes´ıthetik a t¨obbi Observert bele´ertve saj´ at magukat is.
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 szerver id˝o ki´ır´as´ara: <%@ Page Language="C#" %>
pont(1):
12
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Adatb´azisok
2015. m´ajus 27.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AD
´ MEGOLDAS
pont(5) :
1. Adott egy sz´ all´ıt´ ok (SZ), alkatr´eszek (A) ´es g´epek (G) adatait tartalmaz´o adatb´azis, amely a k¨ovetkez˝o rel´ aci´ okb´ ol a´ll: SZ: SZID: a sz´ all´ıt´ o egyedi azonos´ıt´ oja, a rel´aci´o kulcsa SZN: a sz´ all´ıt´ o neve SZV: a sz´ all´ıt´ o lak´ ohelye (v´ aros) A: AID: az alkatr´esz egyedi azonos´ıt´ oja, a rel´aci´o kulcsa AN: az alkatr´esz neve ASZ: az alkatr´esz sz´ıne G: GID: a g´ep egyedi azonos´ıt´ oja, a rel´aci´o kulcsa GN: a g´ep neve GV: a g´epet ebben a v´ arosban k´esz´ıtett´ek Ha egy adott sz´ all´ıt´ o egy adott g´ephez egy adott alkatr´eszb˝ol DB darabot sz´all´ıt, akkor ennek adatai beleker¨ ulnek az SZGA rel´ aci´ oba, melynek attrib´ utumai: SZGA:
SZID: AID: GID: DB:
ld. fent ld. fent ld. fent darabsz´ am
´Irjon SQL lek´erdez´est, amely visszaadja azoknak az alkatr´eszeknek a nev´et ´es mennyis´eg´et, amelyeket a TZ4K azonos´ıt´ oj´ u kerti traktorhoz sz´ all´ıtottak! (Felt´etelezhetj¨ uk, hogy egy ´arucikket ugyanahhoz a g´ephez csak egyszer rendeltek.)
Megold´ as: SELECT AN, DB FROM SZGA, A WHERE SZGA.AID=A.AID AND GID=’TZ4K’
pont(1):
2. K´esz´ıtse el az R(A, B, C, D) rel´ aci´ os s´ema egy vesztes´egmentes felbont´as´at BCNF r´eszs´em´akba, ha a funkcion´ alis f¨ ugg´esek ismert halmaza F = {ABD → B, BCD → C, AD → CD}!
Megold´ as: R1(A, D, C), R2(A, B, D)
pont(1):
3. Az F = {A → AB, A → C, AC → BC} f¨ ugg´eshalmazb´ol a G = {A → BC, AC → B, AB → C} halmaz melyik f¨ ugg´esei k¨ ovetkeznek?
Megold´ as: Valamennyi.
pont(1):
13
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
2015. m´ajus 27.
Adatb´azisok
4. V´egezzen rel´ aci´ oanal´ızist az al´ abbi P-Q ´ all´ıt´ asp´arok k¨oz¨ott! P ´es Q ¨onmag´aban is lehet igaz vagy hamis, tov´ abb´ a az is eld¨ ontend˝ o, hogy van-e logikai kapcsolat k¨oz¨ott¨ uk. Ennek megfelel˝oen a lehets´eges v´alaszok: A B C D E (i)
– – – – –
P igaz, Q igaz ´es van ¨osszef¨ ugg´es P igaz, Q igaz, de nem kapcsol´odnak P igaz, Q hamis P hamis, Q igaz mindkett˝ o hamis
(+ + +) (+ + –) (+ –) (– +) (– –)
P: Minden legal´ abb h´ arom attrib´ utumos rel´aci´os s´em´anak van m´asodlagos attrib´ utuma, ez´ert Q: csak a legfeljebb k´et attrib´ utumb´ol ´all´o (´es legal´abb 1NF) s´em´akra tudjuk a f¨ ugg´eshalmaz ismerete n´elk¨ ul kijelenteni, hogy biztosan BCNF.
Megold´ as: D (ii)
pont(1):
P: Egy rel´ aci´ os s´ema kulcsai k¨ oz¨ ott lehetnek diszjunkt p´arok, ez´ert Q: lehets´eges, hogy az egyik kulcs nincs teljesen benne a m´asik lez´artj´aban.
Megold´ as: C
pont(1):
14
