N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
MI
pont(90) :
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 2011. 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.
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
2011. m´ajus 31.
2
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Algoritmuselm´elet
2011. m´ajus 31.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AL
pont(30) :
1. Legyen f (n) = 3f (n − 2) + 5n + 8. Igaz-e, hogy (i) f = O(n2 ) ?
Megold´ as: nem
n
(ii) f = O(4 ) ?
Megold´ as: igen pont(2):
´ 2. Az al´ abbi kupacon hajtsa v´egre a BESZUR(3) m˝ uveletet! Megold´ as: 2 3 6 14
4 5
8
10
7
9
pont(2):
3. Az 1, 2, . . . , 20 sz´ amokb´ ol 7 elem˝ u r´eszhalmazokat k´epez¨ unk. H´any olyan van k¨oz¨ott¨ uk, amelyik metszi az {1, 2} halmazt? (A pontos sz´ am nem fontos, el´eg egy z´art formul´aval megadni.) 20 18 18 19 2 Megold´ as: − = + · 7 7 5 6 1
pont(2): 4. Az al´ abbi gr´ afon a Bellman-Ford algoritmust kezdt¨ uk el alkalmazni. Fejezze be Mit adnak meg az utols´ o sorbeli sz´ amok az algoritmus v´eg´en? B D 1 3 5 Megold´ as: 2 F A B C A 4 4 −1 1. 0 3 5 6 2. 0 3 5 5 −2 E 3. 0 2 5 C 4. 0 2 5 5. 0 2 5 Az utols´ o sor az A-t´ ol m´ert legr¨ ovidebb utak hossza.
az algoritmust!
D ∞ 4 2 2 2
E ∞ 3 3 3 3
F ∞ ∞ 9 7 7 pont(4):
5. Adott n pozit´ıv sz´ am x1 , x2 , . . . , xn , valamint egy k pozit´ıv eg´esz. Azt kell eld¨onten¨ unk, hogy vannak-e olyan I1 , I2 , . . . , Ik ⊆ {1, 2, . . . , n} diszjunkt indexhalmazok (I ∩ I = ∅, ha j = 6 t), melyekre ∪kj=1 Ij = {1, 2, . . . , n} ´es j t P minden 1 ≤ j ≤ k eset´en i∈Ij xi ≤ 1. Melyik ismert feladatot ´ırja le a k´erd´es? Megold´ as: L´ adapakol´ as (eld¨ ont´esi v´ altozata) pont(4):
3
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Algoritmuselm´elet
2011. m´ajus 31.
6. Tegy¨ uk fel, hogy P tartalmazza az NP oszt´ alyt. Tekints¨ uk a k¨ovetkez˝o A ´es B probl´em´at. A:
Adott egy G ir´ any´ıtatlan gr´ af. K´erd´es, hogy van-e G-ben legal´ abb 5 pont´ u teljes r´eszgr´af.
B:
Adott egy G ir´ any´ıtatlan gr´ af ´es egy k > 0 eg´esz sz´am. K´erd´es, hogy van-e a G gr´ afban pontosan k pont´ u teljes r´eszgr´af.
Van-e A-r˝ ol B-re polinomi´ alis visszavezet´es (Karp-redukci´o)? V´alasz´at r¨oviden indokolja is! Megold´ as: A, B ∈ NP ⊆ P ´es b´ armely k´et nem u ¨res P-beli visszavezethet˝o egym´asra. Vagy: A ∈ P, B NP-teljes, teh´ at A visszavezethet˝ o B-re (a felt´etelt˝ ol f¨ uggetlen¨ ul) pont(4): 7. Az A t¨ omb, amely n csupa k¨ ul¨ onb¨ oz˝ o sz´ amot tartalmaz. Adjon algoritmust, amely az A t¨omb ismeret´eben O(n2 ) l´ep´esben meghat´ arozza az A-beli leghosszabb monoton cs¨okken˝o r´eszsorozat hossz´at! (Azaz a maxim´alis olyan k sz´ amot, melyre tal´ alhat´ o olyan i1 < i2 < · · · < ik , hogy A[i1 ] > A[i2 ] > · · · > A[ik ].) Megold´ as: Dinamikus prograoz´ assal: Legyen T [1] = 1, j = 2, . . . , n: T [j] = 1 + max{T [`] : ` < j ´es A[`] > A[j]}, A keresett ´ert´ek a T t¨ omb maximuma: k = 1, j = 2, . . . , n: k = max{k, T [j] }.
pont(6): 8. K´et marslak´ o a k¨ ovetkez˝ o j´ at´ekot j´ atssza. Az egyik marslak´o mond k´et 10 marsi karakterb˝ol ´all´o sz´ot (term´eszetesen marsi nyelven), A-t ´es B-t. A m´ asik marslak´o feladata tetsz˝oleges sz´am´ u l´ep´esben eljutni az A sz´ ot´ ol a B sz´ oig u ´gy, hogy minden l´ep´esben egyetlen karaktert m´odos´ıthat, azonban ezt csak u ´gy teheti, hogy a k¨ ozb¨ uls˝ o l´ep´esben kapott sz´ o szint´en ´ertelmes marsi sz´o legyen. (Az eredetileg kapott A ´es B szavak ´ertelmes szavak.) Adjon algoritmust, amely az A ´es B szavak, valamint az ¨osszes 10 karakterb˝ol ´all´o ´ertelmes marsi sz´o L list´ aja alapj´ an meghat´ arozza, hogy megoldhat´ o-e a marslak´o feladata! Az algoritmus l´ep´essz´ama legyen O(|L|2 ), ahol |L| az L lista hossz´ at jel¨ oli! (A marsi karakterek sz´am´ar´ol csak annyit tudunk, amennyi a feladat sz¨oveg´eb˝ ol k¨ ovetkezik.) Megold´ as: A G = (V, E) gr´ afban V = L, k´et cs´ ucs k¨oz¨ott akkor van ´el, ha egy l´ep´esben egym´asba alak´ıthat´ ok. Ebben kell utat tal´ alni A ´es B k¨ oz¨ ott – pl. egy sz´eless´egi bej´ar´assal, aminek l´ep´essz´ama O(n2 ).
pont(6):
4
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2011. m´ajus 31.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
H
pont(15) :
1. Mi annak a protokollnak a neve, amelynek seg´ıts´eg´evel az IP-c´ım ismeret´eben meg lehet hat´arozni az adatkapcsolati r´etegbeli c´ımet? Megold´ as: Address Resolution Protocol (ARP)
pont(2):
2. Mit csin´ al egy IPv4 router, ha akkora t¨ ored´ekekben ´erkezik hozz´a egy csomag, amelyek kicsit nagyobbak, mint a kimen˝ o porton haszn´ alt adatkapcsolati keret payloadj´anak m´erete? a) Megn¨ oveli az adatkapcsolati r´eteg payloadj´anak m´eret´et. ¨ b) Osszerakja a t¨ ored´ekeket az eredeti csomagg´a, ´es u ´jrat¨ordeli a megfelel˝o m´eretre. c) Eldobja a csomagot, mert t¨ ored´eket nem szabad tov´abb t¨ordelni. d) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. Megold´ as: d)
pont(2):
3. 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(2):
4. Az al´ abbiak k¨ oz¨ ul mely ´ all´ıt´ as(ok) igaz(ak) az Ethernet backoff strat´egi´aj´ara? a) Tiszt´ an exponenci´ alis. b) Tiszt´ an line´ aris. c) Lehet˝ ov´e teszi az adapt´ aci´ ot a felhaszn´ al´ ok sz´am´ahoz. d) A 3. u ¨tk¨ oz´es ut´ an a 0, . . ., 7 intervallum lesz a sorsol´asi intervallum. e) A backoff ´ert´ek´et r´esid˝ okben sz´ amoljuk. f ) A t¨ obbi v´ alasz k¨ oz¨ ul egyik sem helyes. Megold´ as: c), d), e)
pont(2):
5. Az al´ abbiak k¨ oz¨ ul mely param´eter(ek) sz¨ uks´eges(ek) egy alkalmaz´as megc´ımz´esre az IP-h´al´ozaton kereszt¨ ul? a) IP-verzi´ o ´es IP-c´ım. b) Sz´ all´ıt´ asi r´etegbeli protokoll azonos´ıt´ oja. c) Alkalmaz´ as futtathat´ o´ allom´ any´ anak f´ ajlneve. d) Az alkalmaz´ as mem´ oriac´ıme. e) A h´ al´ ozati csatol´ o fizikai c´ıme. f ) Sz´ all´ıt´ asi r´etegbeli protokoll alkalmaz´ ashoz rendelt portsz´ama. Megold´ as: a), b), f )
pont(2):
5
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Sz´am´ıt´og´ep-h´al´ozatok
2011. m´ajus 31.
6. Nevezze meg (magyarul vagy angolul) azt a jellemz˝oen t¨obbportos eszk¨ozt, amely ak´ar t¨obb k¨ ul¨onf´ele h´ al´ ozat k¨ oz¨ ott is ´ atj´ ar´ ast biztos´ıthat u ´jrakeretez´essel an´elk¨ ul, hogy a hordozott h´al´ozati r´etegbeli csomagot ´ertelmezn´e, feldolgozn´ a! Megold´ as: h´ıd (bridge)
pont(2):
7. Az A ´es B v´egpont k¨ oz¨ otti kommunik´ aci´ o sor´an A v´egpont utols´ok´ent elk¨ uld¨ott TCP PDU-j´aban a sorsz´ am (sequence number) 4740, a hasznos adatr´esz 150 byte. B v´alaszk´ent k¨ uld¨ott TCP PDU-j´aban az ACK-sz´ am 4350. H´ any byte-nyi adatot k¨ uldhet m´eg A a k¨ovetkez˝o nyugta meg´erkez´es´eig, ha az ablakm´eret 600? Megold´ as: 60
pont(3):
6
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2011. m´ajus 31.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
O
pont(15) :
1. Az al´ abbi ´ all´ıt´ asok k¨ oz¨ ul melyik hamis az oper´aci´os rendszerek tipikus bels˝o fel´ep´ıt´es´evel kapcsolatban? a) Az oper´ aci´ os rendszer magja (kernel) csak az alapfunkci´okat, pl. mem´oriakezel´es, folyamat- ´es sz´alkezel´es, CPU u ¨temez´es tartalmazza. b) A felhaszn´ al´ oi programok nem ´erhetik el direkt m´odon (pl. I/O g´epi utas´ıt´asok) a hardver elemeket. c) Az alkalmaz´ oi programok f¨ uggv´enyh´ıv´ asokkal vagy szubrutinh´ıv´asokkal ´erik el az oper´aci´os rendszer szolg´ altat´ asait. d) Az oper´ aci´ os rendszerekben mindig tal´ alunk egy als´o, hardverk¨ozeli r´eteget, amely elfedi a hardware elemek specialit´ asait, ´es absztrakt hozz´ af´er´est tesz lehet˝ov´e a hardverhez. Megold´ as: c)
pont(2):
2. Az al´ abbi esetek k¨ oz¨ ul melyik nem hozza m˝ uk¨od´esbe az oper´aci´os rendszert, ha a sz´am´ıt´og´ep ´eppen egy felhaszn´ al´ oi programot futtat? a) A fut´ o program a yield( ) rendszerh´ıv´ as megh´ıv´as´aval lemond a fut´as jog´ar´ol. b) A h´ al´ ozati interf´eszen be´erkezik egy IP csomag, amely hardvermegszak´ıt´ast (HW interrupt) okoz. c) A felhaszn´ al´ oi program egy a fizikai mem´ ori´aban is megtal´alhat´o virtu´alis mem´orialapra ´ır. d) A felhaszn´ al´ oi program user m´ odban illeg´alis g´epi utas´ıt´ast k´ıs´erel meg v´egrehajtani, aminek hat´as´ara a CPU kiv´etelt (exception) hajt v´egre. Megold´ as: c)
pont(2):
3. Melyik ´ all´ıt´ as igaz minden esetben a folyamatokra (process)? a) A folyamat szekvenci´ alis program. b) A folyamat v´egrehajt´ as alatt ´ all´ o program. c) A folyamatok k¨ oz¨ otti kommunik´ aci´ o k¨ oz¨ os mem´ori´an kereszt¨ ul t¨ort´enik. d) A folyamatok l´etrehoz´ asa ´es megsz¨ untet´ese kev´esb´e er˝oforr´as ig´enyes a sz´alakkal ¨osszehasonl´ıtva. Megold´ as: b)
pont(2):
4. A folyamatok egyszer˝ u´ allapot´ atmeneti diagramja alapj´an mely ´all´ıt´as hamis a k¨ovetkez˝o ´all´ıt´asokb´ol kooperat´ıv (nem preempt´ıv) oper´ aci´ os rendszer eset´en? a) A folyamatok ,,Fut´ asra k´esz” ´ allapotba ker¨ ulnek l´etrehoz´asuk ut´an. b) Az I/O l¨ oket alatt a folyamatok ,,V´ arakoz´o” ´allapotban v´arnak a rendszerh´ıv´as befejez´es´ere. c) A processzort a fut´ o folyamatt´ ol az oper´ aci´os rendszer elveheti. d) A folyamat csak fut´ o´ allapotb´ ol fejez˝ odhet be. Megold´ as: c)
pont(2):
7
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Oper´aci´os rendszerek
2011. m´ajus 31.
5. Mely processzor¨ utemez´esi algoritmusokkal kapcsolatos ´all´ıt´as igaz az al´abbiak k¨oz¨ ul? a) A k¨ orforg´ o (RR: Round Robin) algoritmus a legr¨ovidebb l¨oketidej˝ u (SJF: Shortest Job First) algoritmus preempt´ıv v´ altozata. b) A legr´egebben v´ arakoz´ o (FCFS: First Come First Serve) algoritmus ´atmegy a k¨orforg´o (RR: Round Robin) algoritmusba, ha t´ ul hossz´ u id˝ oszeletet v´ alasztunk. c) A k¨ orforg´ o (RR: Round Robin) u ¨temez˝ o algoritmusban megjelenhet a konvoj hat´as. d) A legr¨ ovidebb h´ atral´ev˝ o l¨ oketidej˝ u (SRTF, Shortest Remaining Time First) algoritmus priorit´asos algoritmus. Megold´ as: d)
pont(2):
6. Melyik ´ all´ıt´ as hamis a virtu´ alis t´ arkezel´est haszn´al´o rendszerekkel kapcsolatban? a) Az el˝ oretekint˝ o lapoz´ as (anticipatory paging) mindig n¨oveli a virtu´alis t´arkezel´es teljes´ıtm´eny´et. b) Virtu´ alis mem´ oriakezel´es eset´en a rendelkez´esre ´all´o k¨ozponti (fizikai) mem´ori´an´al nagyobb fizikai mem´ oria ig´eny˝ u programok is futtathat´ ok. c) A fut´ o programok mem´ ori´ aj´ anak csak a t´enylegesen haszn´alt r´esze kell, hogy megtal´alhat´o legyen a k¨ ozponti (fizikai) mem´ ori´ aban. d) A virtu´ alis t´ arkezel´es a felhaszn´ al´ oi programokat fejleszt˝ok sz´am´ara l´athatatlan, azzal nem kell t¨or¨odni, csup´ an a program t´enyleges fut´ asi sebess´eg´et fogja befoly´asolni. Megold´ as: a)
pont(2):
7. Rajzolja fel, hogyan t¨ ort´enik a c´ımtranszform´aci´o lapszervez´es eset´en egyszint˝ u lapt´abla alkalmaz´as´aval! Az asszociat´ıv gyors´ıt´ ot´ ar felrajzol´ asa nem sz¨ uks´eges.
Megold´ as: k¨ onyv 3.17 ´ abra.
pont(3):
8
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2011. m´ajus 31.
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
S1
pont(10) :
1. Az al´ abbi UML2 diagram alapj´ an – a kulcs felhaszn´al´as´aval – jellemezze az ´all´ıt´asokat! <
> Q
W
+foo( )
+bar( )
E
R
-inf
-rparam +bar(e:E)
+m11(q:Q)
T
A B C D E
– – – – –
Y
-q
-val
-qux(y:Y)
+foo(r:R)
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
(+ + +) (+ + –) (+ –) (– +) (– –)
(i) E helyettes´ıthet˝ o R-rel, mert R interf´esze kompatibilis E interf´esz´evel.
(ii) T-nek m11(q:Q) met´ odusa nem kaphat param´eterk´ent R-et, mert T nem f¨ ugg R-t˝ol. Megold´ as: E, D
pont(2):
2. A szoftverfejleszt´es v´ızes´esmodellje szerint a fejleszt´esnek melyik az els˝o f´azisa? Megold´ as: K¨ ovetelm´eny pont(2): 3. Nevezzen meg egy statikus ´es egy dinamikus verifik´aci´os technik´at! Megold´ as: Statikus: fel¨ ulvizsg´ alat, ´ atvizsg´ al´ as, review, audit Dinamikus: teszt pont(2):
9
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnol´ogia
2011. m´ajus 31.
4. Pali k´esz´ıt egy t´ akolm´ anyt, majd azt berakja a vitrinbe. K´es˝obb Feri elk´eri Palit´ol a t´akolm´anyt, ´es azonnal r´ a´ırja a d´ atumot. Rajzoljon UML2 szekvenciadiagramot! Megold´ as:
sd vv
Pali:Ember
:Vitrin
1 create
t:Tákolmány
Feri:Ember
2 berak(t) 3. elkér
3.1 kivesz t t 4. ráír
pont(2): 5. Elk´esz´ıtj¨ uk az al´ abbi O oszt´ aly k´et p´eld´ any´ at, o1-et ´es o2-t. Ezt k¨ovet˝oen – sorrendben – v´egrehajtjuk a k¨ovetkez˝ o m˝ uveleteket: O
o2.x o1.y o2.y
= = =
3; o1.x = -2; o2.x + 5; o2.x + o1.y;
int x = 11 int y = -4 private xx(): int
Mennyi lesz az o2.y v´ altoz´ o ´ert´eke? Megold´ as: pont(2):
o2.y =1
10
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
2011. m´ajus 31.
Szoftvertechnik´ak
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
S2
pont(10) :
¨ 1. Egy-k´et mondatban adja meg, milyen ´ altal´ anos probl´em´at old meg a Composite (Osszetett) tervez´esi minta! Megold´ as: Az objektumokat fastrukt´ ur´ aba szervezi, ´es lehet˝ov´e teszi az elemi ´es ¨osszetett objektumok egys´eges kezel´es´et.
pont(2): 2. 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(2): 3. Rajzolja fel ´ altal´ anoss´ ag´ aban vagy egy p´eld´ara vonatkoz´oan a Factory Method (Met´odusgy´ar) minta oszt´ alydiagramj´ at! Megold´ as:
<> Creator
<> Product
<> + Fact or yM et hod () + A nO per at io n()
ConcreteCreator Concret ePr odu ct
Create
+ FactoryM ethod()
AnOper ati on() { .. . p roduct = FactoryM ethod () .. . }
Factor yM e tho d() { retu rn ne w Co ncr eteProdu ct() }
pont(2):
11
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
Szoftvertechnik´ak
2011. m´ajus 31.
4. Az el˝ oz˝ o feladat oszt´ alydiagramj´ ara ´ep´ıtve ismertesse ´altal´anoss´ag´aban vagy egy p´elda alapj´an a Factory Method minta m˝ uk¨ od´es´et, jellemezze a benne szerepl˝o oszt´alyokat! Megold´ as: A Creator ´es a Product tipikusan egy keretrendszer r´eszei. A keretrendszernek (a Creator-nak) ConcreteProduct t´ıpus´ u objektumot kell l´etrehoznia, de ezt a t´ıpust nem ismeri. A Creator egy absztrakt FactoryMethod m˝ uveletet defini´ al, amit fel¨ uldefini´ al a Creator-b´ol sz´armaz´o ConcreteCreator oszt´aly: ebben ez a m˝ uvelet egy u ´jonnan l´etrehozott ConcreteProduct objektummal t´er vissza. A ConcreteProduct l´etrehoz´as´ahoz ´ıgy a k¨ ornyezet egy ConcreteCreator objektumot p´eld´anyos´ıt, melyre tipikusan Creator t´ıpus´ u referenci´aval/mutat´ oval hivatkozik: az u ´j ConcreteProduct objektumot a FactoryMethod m˝ uvelet megh´ıv´as´aval hozza l´etre.
pont(2): 5. Hasonl´ıtsa ¨ ossze a kliens ´es a kiszolg´ al´ o oldali szkript szerep´et a webalkalmaz´asokra vonatkoz´oan! Megold´ as: A kliens oldali szkript (pl. JavaScript) a b¨ong´esz˝oben fut, a felhaszn´al´o sz´am´ara megjelen´ıtett HTML oldal tartalm´ at ´es a b¨ ong´esz˝ o megjelen´es´et m´ odos´ıtja (pl. ablak mozgat´as, u ´j ablak megnyit´as, stb.). A kiszolg´ al´ o oldali szkriptet a webkiszolg´ al´ o futtatja, szerepe egyr´eszt a be´erkez˝o k´er´es feldolgoz´asa (pl. a felhaszn´ al´ o´ altal megadott adatok kinyer´ese), m´ asr´eszt a kliens sz´am´ara visszak¨ uld¨ott HTML oldal el˝o´all´ıt´asa. Ehhez a kiszolg´ al´ o oldali szkript felhaszn´ alhatja a szerver oldali er˝oforr´asokat is (pl. adatb´azis).
pont(2):
12
M´ern¨ ok informatikus BSc z´ ar´ ovizsga – MSc felv´eteli
2011. m´ajus 31.
Adatb´azisok
N´ev, felv´eteli azonos´ıt´ o, Neptun-k´ od:
AD
pont(10) :
1. Egy adatb´ azis rekordjainak a kulcs´ert´ek¨ uk szerinti el´er´es´et ,,v¨odr¨os hash” szervez´essel szeretn´enk gyors´ıtani. 10 milli´ o rekord tal´ alhat´ o az adatb´ azisban, melyek hossza fix 240 byte, benne a kulcs 25 byte. A h´ att´ert´ ar blokkel´er´es˝ u, egy blokk kapacit´ asa (a fejr´eszt nem sz´am´ıtva) 4000 byte. Minden mutat´o 8 byte-on t´arolt. Az alkalmaz´ as nem teszi lehet˝ ov´e, hogy 5 blokkel´er´esn´el t¨obb id˝o legyen a keres´esre. Mennyi legyen a v¨ odr¨ ok minim´ alis sz´ ama ´es mekkora lesz ekkor a hash-t´abla m´erete? (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: Egy blokkban 4000/240 = 16 rekord f´er el. A rekordok t´arol´as´ahoz ez´ert 10 000 000/16 = 625 000 adatblokk sz¨ uks´eges. 5 megengedett blokkel´er´es mellett a v¨odr¨ok hossza 5 blokknyi lesz, ehhez legal´abb 625 000/5 = 125 000 v¨ od¨ or kell. A v¨ od¨ orkatal´ ogus m´erete ekkor 125 000 ∗ 8 = 1 000 000 byte.
pont(2): 2. Hat´ arozza meg az atomi attrib´ utumokat tartalmaz´o R(L, M, N, O) rel´aci´os s´ema norm´alform´aj´at az F = {M → O, LM → LN, N → M, N O → M } f¨ ugg´eshalmaz mellett! Megold´ as: 1NF
pont(2):
3. Ekvivalens-e a k¨ ovetkez˝ o k´et f¨ ugg´eshalmaz? {AB → C, AC → B, A → BC}
´es
Megold´ as: igen
{A → B, A → C AC → BC} pont(2):
4. Mutasson p´eld´ at olyan rel´ aci´ os s´em´ ara, amely nem bonthat´o fel vesztes´egmentesen ´es f¨ ugg˝os´eg˝orz˝oen BCNF r´eszs´em´ akra!
Megold´ as: Pl. R(A, B, C), F = {AB → C, C → A}
pont(2):
´ 5. Erveljen a k¨ ovetkez˝ o okfejt´es mellett vagy ellen: Minden BCNF s´ema egyben 3NF is. Mivel minden 3NF s´em´ara illeszked˝o rel´aci´o tartalmazhat redundanci´ at funkcion´ alis f¨ ugg´es k¨ ovetkezt´eben, ez´ert a BCNF s´em´ara illeszked˝o rel´aci´o is tartalmazhat redundanci´ at funkcion´ alis f¨ ugg´es k¨ ovetkezt´eben. Megold´ as: Minden BCNF s´ema egyben 3NF is: igaz. Minden 3NF s´em´ ara illeszked˝ o rel´ aci´ o tartalmazhat redundanci´at funkcion´alis f¨ ugg´es k¨ovetkezt´eben: igaz. A BCNF s´em´ ara illeszked˝ o rel´ aci´ o is tartalmazhat redundanci´at funkcion´alis f¨ ugg´es k¨ovetkezt´eben: hamis, mivel 3NF s´ema eset´en az illeszked˝ o rel´ aci´ ok redundanci´aja csak lehet˝os´eg, amely ´eppen soha nem fog teljes¨ ulni a 3NF speci´ alis esete, a BCNF s´em´ ak eset´en.
pont(2):
13
