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 2016. m´ ajus 31. ´ 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
2016. m´ajus 31.
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
2016. m´ajus 31.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AL
´ MEGOLDAS
√
pont(15) :
n 1. Legyen f (n) = 8n n + 10(log2 n) + 312 ´es g(n) = 15 log2 (n ) + 3 . Igaz-e, hogy f (n) = O(g(n)), illetve, 2 hogy g(n) = O(f (n)) ? 2
2
Megold´ as: igen; nem
pont(1):
´ 2. Az al´ abbi kupacon hajtsa v´egre a BESZUR(3) m˝ uveletet ´es rajzolja le az eredm´enyt! 1 1
3
4
5
7
8
5
4
9
8
9
6
7
6
pont(1): 3. Az 1, 2, · · · , 100 sz´ amoknak h´ any olyan permut´aci´oja van, amelyikben az 1 a 2 el˝ott van, ´es van k¨oz¨ott¨ uk legal´ abb egy m´ asik sz´ am? (Nem sz¨ uks´eges kisz´ amolni, elegend˝o egy formul´at megadni.) Megold´ as: 98! ·
99 2
pont(2):
4. Az al´ abbi gr´ afon a Dijkstra-algoritmust haszn´aljuk a D cs´ ucsb´ol indul´o legr¨ovidebb utak hossz´anak meghat´ aroz´ as´ ara. A kapott u ´thosszakat tartalmaz´o t´abl´azat els˝o 3 sor´at felt¨ untett¨ uk. T¨oltse ki a k¨ovetkez˝o sort! 2
A 4
1
1
D
6 5
2
B
E
3
C 4
3 2
F
2
2 5
G
1
H
3
A ∞ ∞ ∞ ∞
B ∞ ∞ ∞
C ∞ ∞ ∞
D 0 0 0
E 6 6 5
F ∞ ∞ 8
G 2 2 2
H ∞ 3 3
I ∞ ∞ 6
6
8
0
5 .. .
7
2
3
6
I
pont(2): 5. Legyen G = (V, E) egy egyszer˝ u, ir´ any´ıtatlan gr´af. A T tulajdons´ag jelentse a k¨ovetkez˝ot: Minden x1 , x2 , x3 , x4 , x5 ∈ V eset´en, van olyan 1 ≤ i < j ≤ 5, hogy • vagy xi = xj • vagy xi 6= xj ´es {xi , xj } 6∈ E. Fogalmazza meg, milyen ismert gr´ aftulajdons´agot ´ır le T ! Megold´ as: a G gr´ afban nincs K5 . pont(2):
3
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Algoritmuselm´elet
2016. m´ajus 31.
6. Egy f fok´ u l´etr´ an bizonyos fokok annyira rozog´ak, hogy ha r´al´ep¨ unk, leszakadnak. Szerencs´ere tudjuk, hogy melyik fokok ilyenek, hova nem szabad l´epn¨ unk. Egy l´ep´essel legfeljebb 3 fokot tudunk l´epni. Legyen L[i] az a sz´ am, hogy h´ anyf´elek´eppen lehet az i-edik fokra feljutni, L[0] = 1. Ekkor L[1] = 1, ha az els˝o fok j´o, egy´ebk´ent 0. Legyen 4 ≤ i ≤ f . Hogyan lehet L[i] ´ert´ek´et meghat´arozni az L[0], L[1], . . . , L[i − 1] seg´ıts´eg´evel? Megold´ as: L[i] = 0, ha az i-edik fok rossz. Egy´ebk´ent L[i] = L[i − 1] + L[ i − 2] + L[i − 3].
pont(2): 7. Tekints¨ uk a k¨ ovetkez˝ o eld¨ ont´esi probl´em´ akat! Jel¨ olj¨ on G egy egyszer˝ u ir´ any´ıtatlan gr´ afot, melynek ´elei pozit´ıv sz´amokkal vannak s´ ulyozva. A : Adott a G gr´ af ´es egy k pozit´ıv eg´esz sz´am. Van G-ben legfeljebb k s´ uly´ u fesz´ıt˝ofa? B : Adott a G gr´ af ´es egy k pozit´ıv eg´esz sz´am. Van G-ben legal´abb k s´ uly´ u fesz´ıt˝ofa? C : Adott a G gr´ af ´es egy k pozit´ıv eg´esz sz´am. Van G-ben legal´abb k s´ uly´ u (egyszer˝ u) u ´t? Tegy¨ uk fel, hogy P 6= NP. Jel¨ olje be, melyik igaz az al´abbi lehet˝os´egek k¨oz¨ ul! P-beli A
X
B
X
NP-teljes
X
C
pont(2): 8. Egy sz´ınh´ aznak k´et j´ atsz´ ohelye van, a kissz´ınpad ´es a nagysz´ınpad. A sz´ınh´az D f´ele darab j´atszik ´es mindegyikre adott, hogy arra kiz´ ar´ olag a kissz´ınpad vagy kiz´ar´olag a nagysz´ınpad alkalmas. M˝ usortervet kell k´esz´ıten¨ unk az elk¨ ovetlez˝ o N ≤ D/10 napra a k¨ ovetkez˝ o felt´etelekkel: • egy napon mindegyik sz´ınpadon csak egy darab j´atszhat´o, • egy nap minden sz´ın´esz legfeljebb egy darabban szerepelhet (adott, hogy melyikben ki j´atszik), • ez id˝ o alatt minden darabb´ ol legfeljebb h´arom el˝oad´as legyen. Azt szeretn´enk eld¨ onteni, hogy van-e olyan beoszt´as, amikor az N nap mindegyik´en mindk´et sz´ınpadon van el˝ oad´ as. Melyik ismert gr´ afelm´eleti algoritmussal ´es azt milyen gr´afon futtatva lehet polinom id˝oben megv´alaszolni a k´erd´est?
Megold´ as: Legyen G egy p´ aros gr´ af, melynek cs´ ucsai a lehets´eges el˝oad´asok, azaz minden darab 3 p´eld´anyban (a kis- ´es nagysz´ınpadiak a k´et oszt´ aly). K´et cs´ ucsot ¨ osszek¨ot¨ unk, ha nincs k¨oz¨os sz´ın´esz benn¨ uk. A k´erd´es, hogy van-e N ´el˝ u p´ aros´ıt´ as. Ehhez a magyar m´ odszert (maxim´alis p´aros´ıt´ast tal´al´o algoritmust) haszn´alhatjuk. Ha az eredm´eny legal´ abb N ´elb˝ ol ´ all, akkor van megold´as.
pont(3):
4
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2016. m´ajus 31.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
H
´ MEGOLDAS
pont(7,5) :
1. Az al´ abbiak k¨ oz¨ ul mely ´ all´ıt´ as(ok) igaz(ak) NAT (Network Address Translation) u ´tvonalv´alaszt´o haszn´ alata eset´en? a) Az IP-c´ımek alapj´ an az ´ allom´ as nev´et adja meg. b) Egyetlen, vagy nagyon kev´es publikus IP-c´ımmel megoldhat´o a teljes mag´anh´al´ozat c´ımz´ese. c) Minden alkalmaz´ asi r´etegbeli protokoll v´ altoztat´as n´elk¨ ul haszn´alhat´o. d) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. Megold´ as: b)
pont(1):
2. Az al´ abbiak k¨ oz¨ ul mely(ek) elosztott t¨ obbsz¨ or¨os hozz´af´er´esi m´odszer(ek)? a) Polling (k¨ orbek´erdez´es) b) Probing (csoportos lek´erdez´es) c) CSMA/CD d) Reservation (helyfoglal´ as) e) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. Megold´ as: c)
pont(1):
3. Hogy h´ıvjuk azt a HTTP kapcsolatot, ahol egy TCP kapcsolaton bel¨ ul t¨obb HTTP k´er´es/v´alasz p´ar is lehet? Megold´ as: perzisztens
pont(1):
4. IPv4 t¨ ordel´es eset´en ki v´egezheti el a t¨ ored´ekek ¨ossze´all´ıt´as´at (ha nem haszn´alunk NAT-ot)? A csom´opont nev´et v´ arjuk v´ alaszk´ent. Megold´ as: c´ımzett
pont(1):
5. A 198.51.100.128/26 h´ al´ ozatra adja meg a broadcast c´ımet! Megold´ as: 198.51.100.10|11 1111, azaz 198.51.100.191
pont(1):
6. Eg´esz´ıtse ki az al´ abbi sz¨ oveget! A(z) AS egy olyan h´ al´ ozatr´esz, amelyen bel¨ ul egys´eges routing m´odszert alkalmaznak. Ezek k¨oz¨ott a(z) . . . . . . . . . . . . . . . . . . . . . . . . . csoportba tartoz´o routing protokollokat haszn´alhatjuk, melyeknek leggyakrabban haszn´ alt v´ altozata a BGP. Megold´ as: EGP
pont(1):
7. Az A ´es B v´egpontok k¨ oz¨ otti kommunik´ aci´ o sor´an az A v´egpont utols´ok´ent elk¨ uld¨ott TCP PDU-j´aban a sorsz´ am (sequence number) 8350, a hasznos adatr´esz 1400 byte. A B v´alaszk´ent k¨ uld¨ott TCP PDU-j´aban az ACK-sz´ am 8050. H´ any byte-nyi adatot k¨ uldhet m´eg A a k¨ovetkez˝o nyugta meg´erkez´es´eig, ha B v´eteli ablakm´erete 2000? Megold´ as: 300
pont(1,5):
5
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
6
2016. m´ajus 31.
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2016. m´ajus 31.
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 igaz a rendszerh´ıv´asokkal kapcsolatban? a) A rendszerh´ıv´ asokat az alkalmaz´ asokat programoz´ok direkt m´odon haszn´alj´ak. b) Alkalmaz´ oi programok a be- ´es kiviteli m˝ uveleteket rendszerh´ıv´asokon kereszt¨ ul ´erik el. c) A rendszerh´ıv´ as egy f¨ uggv´enyh´ıv´ as. d) Az aszinkron rendszerh´ıv´ as a m˝ uveletek befejez´ese ut´an t´er vissza. Megold´ as: b) ( a) – hib´as, mert a rendszerk¨onyvt´arakon kereszt¨ul haszn´alj´ak. b) – a m˝uveletek megval´os´ıtva a kernelben vannak, ´es az alkalmaz´ oi programok direkt m´ odon nem ´erhetik el az I/O-t. c) – hib´ as, mert l´enyeg´eben egy megszak´ıt´ asr´ ol van sz´ o. d) – hib´ as, mert az aszinkron h´ıv´ as csak elind´ıtja a v´egrehajt´ ast. )
pont(1):
2. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik hamis az oper´aci´os rendszerek bels˝o szerkezet´evel kapcsolatban? a) Az oper´ aci´ os rendszer magja felel˝ os a feladatok u ¨temez´es´e´ert. b) Az oper´ aci´ os rendszer magja kezeli a mem´ori´at. c) Az oper´ aci´ os rendszer magja t¨ obbnyire platformf¨ uggetlen m´odon ker¨ ul megval´os´ıt´asra. d) Az oper´ aci´ os rendszer magja tartalmazza a rendszerh´ıv´asokat fogad´o r´eteget. Megold´ as: d) (a rendszerh´ıv´asokat fogad´o r´eteg a kernel felett tal´alhat´o, a kernel ´es az alkalmaz´asok k¨oz¨ott teremti pont(1):
meg a kapcsolatot.)
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 SJF algoritmus preempt´ıv. c) Az RR algoritmus preempt´ıv. d) Az SRTF algoritmus preempt´ıv. Megold´ as: b)
pont(1):
4. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik igaz a folyamatokkal (process) ´es a sz´alakkal (thread) kapcsolatban? a) A sz´ al a folyamathoz rendelt CPU-n fut. b) A folyamatnak saj´ at halomja (heap) van. c) A sz´ alnak saj´ at halomja (heap) van. d) Egy folyamat egy sz´ al kontextus´ aban fut. Megold´ as: b) (az a) hamis, mert a folyamathoz nem rendel¨unk CPU-t, azt a v´egrehajt´as egys´eg´ehez, a sz´alhoz rendelj¨uk, a c) verem eset´en lenne igaz, a d) meg pont ford´ıtva van.) pont(1):
7
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2016. m´ajus 31.
5. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik igaz a szemaforra vonatkoz´oan? a) A szemafor kezdeti ´ert´eke minden alkalmaz´asban 1, vagyis a szemaforhoz tartoz´o er˝oforr´as nem foglalt. b) Szemaforral nem lehet randev´ ut megval´ os´ıtani. c) Szemafor alkalmaz´ as´ aval elker¨ ulhetj¨ uk a holtpont l´etrej¨ott´et. d) A sz´ aml´ al´ o (counter) t´ıpus´ u szemafor alkalmaz´asa eset´en a szemaforhoz rendelt er˝oforr´as egy id˝oben t¨ obb p´ arhuzamos feladat ´ altal haszn´ alhat´ o. Megold´ as: d) (a – hamis, mert szinkroniz´aci´o megval´os´ıt´asa eset´en foglalva inicializ´aljuk a szemafort, b – hamis, mert a szemafor alkalmazhat´ o szinkroniz´ aci´ ora, c – hamis, mert a szemafor alkalmaz´ asa eset´en a holtpont l´etrej¨ ott´enek sz¨ uks´eges pont(1):
felt´eteleit nem z´ arjuk ki.)
6. Az al´ abbi mondatok k¨ oz¨ ul melyik hamis a lapszervez´essel kapcsolatban? a) Lapszervez´es eset´en a logikai lapok ´es a fizikai mem´oria keretek m´erete azonos. b) A lapt´ abl´ at ´ altal´ aban a fizikai mem´ ori´ aban t´arolj´ak. c) A lapt´ abla minden bejegyz´ese egy fizikai mem´oriakeretre mutat. d) A lapszervez´es eset´en nincs k¨ uls˝ o t¨ ordel˝ od´es. Megold´ as: c) (mert csak azok a lapok ker¨ulnek lek´epz´esre, amiket t´enyleg haszn´alunk (valid/invalid bit), az a) ´es a d) egym´ asb´ ol k¨ ovetkezik, ´es ez az egyik legnagyobb el˝ ony, ami miatt haszn´ aljuk a lapoz´ ast, a b) igaz, a TLB-be azt csak
pont(1):
cache-elik.)
7. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik hamis a f´ ajlrendszerekkel kapcsolatban? a) A f´ ajlrendszer feladata az, hogy az inform´aci´ot t´arol´o logikai blokkokat a fizikai f´ajlokhoz rendelj´ek. b) L´ ancolt list´ as t´ arol´ as eset´en az egyes blokkok t´arolj´ak a f´ajlban k¨ovetkez˝o blokkok hely´et. c) Indexelt t´ arol´ as eset´en speci´ alis blokkok t´arolj´ak a f´ajl t´arol´as´ara haszn´alt blokkok hely´et. d) Indexelt t´ arol´ as eset´en a f´ ajl tetsz˝ oleges r´esz´enek gyors el´er´ese lehets´eges. Megold´ as: a) (a fizikai blokkokat kell a logikai f´ajlokhoz rendelni) pont(1): 8. Az al´ abbi k´et a´ll´ıt´ as k¨ oz¨ ul melyik igaz a PRAM mem´oria-hozz´af´er´esi modell eset´en? a) Az olvas´ as-olvas´ as u ¨tk¨ oz´es eset´en nincs versenyhelyzet. b) Az olvas´ as-´ır´ as u ¨tk¨ oz´es eset´en nincs versenyhelyzet. Megold´ as: a) (hiszen minden olvas´o a helyes ´ert´eket fogja olvasni, m´ıg b) eset´en a t´enyleges v´egrehajt´ast´ol f¨ugg˝oen az olvas´ as a r´egi vagy az u ´j ´ert´ekez is visszaadhatja (van versenyhelyzet)).)
8
pont(0,5):
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2016. m´ajus 31.
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 foo(k:K) met´ odusa nem kaphat param´eter¨ ul B t´ıpus´ u objektumot, mert B-nek is van foo(k:K) met´ odusa. Megold´ as: B
pont(1):
2. Mely tesztek ir´ anyulnak a k¨ ovetkez˝ o f´ azisok kimeneteinek ellen˝orz´es´ere? K¨ ovetelm´enyek
valid´ al´ as (validation)
Specifik´ aci´ o
rendszerteszt (system test) pont(1):
9
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2016. m´ajus 31.
3. Izidor leveszi kedvenc k¨ onyv´et a k¨ onyvespolcr´ol. Megn´ezi, hogy ki a k¨onyv kiad´oja, majd a kiad´ot SMS-ben megk¨ uldi Emerenci´ anak. (i) Adja meg a fenti t¨ ort´enet UML2 modellj´eben el˝ofordul´o oper´aci´ok szignat´ ur´ait (haszn´alja a t¨ort´enetben szerepl˝ o szavakat)!
Megold´ as: levesz( ): K¨ onyv megn´ez( ): Kiad´ o oneway megk¨ uld(Kiad´ o) pont(1): (ii) A fenti t¨ ort´enet alapj´ an rajzoljon UML2 kommunik´aci´os diagramot!
Megold´ as: sd vv 1: levesz(): kedvenc p:Polc
Izidor:Ember
3: megküld(kiadó)
2: megnéz(): kiadó
kedvenc:Könyv
Emerencia:Ember
pont(1):
4. Az al´ abbiakban a fontosabb szoftver architekt´ urat´ıpusokat adtuk meg. V´alassza ki, hogy a k¨otegelt feldolgoz´ as (batch) melyik architekt´ ur´ ahoz illeszkedik! a) objektumorient´ alt (object oriented) b) esem´enysz´ or´ o (event-based implicit invocation) c) absztrakt g´ep (interpreter) d) adatfolyam (pipes and filters) e) adatt´ arol´ as (blackboard) Megold´ as: d)
pont(1):
10
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnik´ak
2016. m´ajus 31.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
S2
´ MEGOLDAS
pont(5) :
1. Milyen ´ altal´ anos probl´em´ at old meg a Factory Method (Met´odusgy´ar) tervez´esi minta?
Megold´ as: Interf´eszt defini´ al az objektum l´etrehoz´as´ara, de a lesz´armaztatott oszt´alyra hagyja annak eld¨ ont´es´et, hogy konkr´etan melyik oszt´ alyb´ ol kell p´eld´ anyt l´etrehozni. Akkor haszn´aljuk, ha egy oszt´aly nem l´atja el˝ore annak az objektumnak az oszt´ aly´ at, amit l´etre kell hoznia, valamint ha egy oszt´aly azt szeretn´e, hogy lesz´armazottai hat´ arozz´ ak meg azt az objektumot, amit l´etre kell hoznia.
pont(1): 2. 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
2016. m´ajus 31.
Szoftvertechnik´ak
¨ 3. Milyen ´ altal´ anos probl´em´ at old meg a Composite (Osszetett) tervez´esi minta? Megold´ as: A minta az al´ abbi probl´em´ akra ad megold´ast: (i) R´esz-eg´esz viszonyban ´ all´ o objektumokat fastrukt´ ur´aba rendezi. (ii) A kliensek sz´ am´ ara lehet˝ ov´e teszi, hogy az egyszer˝ u ´es ¨osszetett objektumokat egys´egesen kezelje.
pont(1): 4. Mutassa be ´ altal´ anoss´ ag´ aban vagy egy p´eld´ an kereszt¨ ul a Composite minta m˝ uk¨od´es´et, ezen bel¨ ul rajzolja fel a minta oszt´ alydiagramj´ at! Megold´ as: <
> Component Cli ent
<> <> <> <>
+ + + +
Operati on() Add(Component) Remove(Component) GetChil d(int)
Leaf + Operati on()
+chi ldren 0..*
Composite + + + +
Operati on() Add(Component) Remove(Component) GetChild(int)
Operation() { for each g i n chi ldren g.Operation(); }
A Composite minta oszt´ alydiagramja az ´ abr´an l´athat´o. Objektumdiagramja fastrukt´ ura, amelyben a Leaf objektum lev´el, a Composite bels˝ o objektum. A Component oszt´aly biztos´ıtja a k¨oz¨os interf´eszt a k´et lesz´armazott haszn´ alat´ ahoz. A minta alkalmaz´ asa akkor lehets´eges, ha a k¨oz¨os interf´esz absztrah´alhat´o. A m˝ uveletet mind a Leaf, mind a Composite fel¨ ul´ırja, a Composite gyakran az ´altala tartalmazott Leaf ´es Composite t´ıpus´ u objektumok azonos nev˝ u f¨ uggv´enyeit h´ıvja tov´ abb. Az asszoci´aci´okhoz tartoz´o t¨omb¨ok kezel´es´et mind az ˝ososzt´ alyban, mind a C pont(1): 5. Tegy¨ uk fel, hogy egy adott m˝ uvelet egy webalkalmaz´asban kliens (pl. JavaScript) ´es kiszolg´al´o (pl. ASPX) oldali k´ oddal is megval´ os´ıthat´ o. Adjon meg egy el˝ onyt a kliens oldali megval´os´ıt´asra vonatkoz´oan, ´es egy tipikus el˝ onyt a kiszolg´ al´ o oldali megval´ os´ıt´ asra vonatkoz´ oan! Megold´ as: A kliens oldali szkript (pl. JavaScript) el˝ onye pl.: Gyorsabb, mert nincs sz¨ uks´eg interakci´ora a kiszolg´ al´ oval (vagy ha sz¨ uks´eg is van r´ a, az hat´ekonyabban, kisebb adatforgalom mellett megtehet˝o). A kiszolg´ al´ o oldali k´ od el˝ onyei: A kiszolg´ al´o oldali k´od ´altal´aban leford´ıthat´o. ´Igy a hib´ak egy r´esze m´ ar ford´ıt´ askor kider¨ ul, illetve az alkalmaz´ as fut´asa gyorsabb lesz. Kiszolg´al´o oldali k´oddal ´altal´aban k¨onnyebb b¨ ong´esz˝ o f¨ uggetlen megval´ os´ıt´ ast k´esz´ıteni. pont(1):
12
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Adatb´azisok
2016. m´ajus 31.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AD
´ MEGOLDAS
pont(5) :
1. Adott egy R(ABCDEF ) s´ema ´es az attrib´ utumain egy F = AB → CDE, B → F A, CD → BE, E → AD, EF → A f¨ ugg˝ os´eghalmaz, valamint az R s´ema R1(ABC), R2(CDE), R3(ABF D), R4(EAD) felbont´asa. A t´abl´ azatos teszt alkalmaz´ as´ aval d¨ ontse el, hogy vesztes´egmentes-e a s´emafelbont´as! Megold´ as: ABC CDE ABF D EAD
A a b2 a a a
B a b2 a a b4
C a a b3 a b4
D b1 a a a a
E b1 a a b3 b1 a a
F b1 a b2 a b4
vesztes´egmentes
pont(1):
2. 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 mert 2000/200 = 10 rekord/blokk, 200 000 blokk, 8 · 50000 byte
pont(1):
3. Adjon p´eld´ at – ha l´etezik – olyan, legal´ abb 1NF rel´aci´os s´em´ara, amely nem 2NF, ´es nem is bonthat´ o fel vesztes´egmentesen 2NF r´eszs´em´ akba u ´gy, hogy a s´emafelbont´as f¨ ugg˝os´eg˝orz˝o is legyen! Megold´ as: Nincs ilyen s´ema.
pont(1):
4. Az al´ abbiak k¨ oz¨ ul mely ´ all´ıt´ asok igazak? L´etezik olyan pontosan 3NF s´ema (nem BCNF), hogy l´etezik egy r´a illeszked˝o rel´aci´o, a) amelynek egyetlen m´ asodlagos attrib´ utum´aban sincs redundancia. b) amely valamennyi els˝ odleges attrib´ utum´ aban redund´ans. c) mely az egyik m´ asodlagos attrib´ utum´ aban redund´ans. Megold´ as: a), b)
pont(1):
5. Egy rel´ aci´ os adatb´ azis tervez´es´ehez mintaadatokat kaptunk az R 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. Kijelenthet˝o-e a t´abl´azat alapj´an, hogy igazak az R(ABCD) s´em´ an a k¨ ovetkez˝ o funkcion´ alis f¨ ugg˝ os´egek? A a1 a1 a2 a2
B b1 b1 b2 b2
C c1 c2 c1 c2
D d1 d2 d2 d1
a) A → B b) AC → B
Megold´ as: Egyik sem jelenthet˝ o ki.
pont(1):
13
