N´ev, azonos´ıt´ o:
AL
pont(30) :
1. Jel¨ olje T (n) egy algoritmus maxim´ alis l´ep´essz´am´at az n hossz´ u bemeneteken. Tudjuk, hogy T (1) = 7 ´es T (n) ≤ 3n + T (n − 1), ha n > 1. K¨ ovetkezik-e ebb˝ ol, hogy (i) T (n) = O(nlog n ) ? (ii) T (n) = O(n2 ) ?
Megold´ as: Mindkett˝ o k¨ ovetkezik.
pont(2):
2. Egy rendez´es sor´an a kezdeti 5, 6, 3, 8, 4, 1, 2, 7 sorrendb˝ ol valah´ any l´ep´es ut´ an a pillanatnyi helyzet a 3, 5, 6, 8, 1, 2, 4, 7 sorrend. Lehetett-e a rendez´es a besz´ ur´ asos, az ¨osszef´es¨ ul´eses, illetve a gyorsrendez´es?
¨ Megold´ as: Besz´ ur´ asos: nem; Osszef´ es¨ ul´eses: igen; Gyorsrendez´es: nem.
pont(2):
3. H´ any k¨ ul¨ onb¨ oz˝o 4 hossz´ u k¨ or tal´ alhat´ o a Kn,m teljes p´ aros gr´ afban?
Megold´ as:
n m 2 · 2
pont(2):
4. Egy bin´ aris fa cs´ ucsai az 1 ´es 8 k¨oz¨otti eg´esz sz´amokkal vannak megc´ımk´ezve. A cs´ ucsok preorder bej´ ar´ as szerinti sorrendje: 1, 2, 4, 5, 8, 3, 6, 7, a postorder bej´ ar´ as szerinti sorrend pedig 4, 8, 5, 2, 6, 7, 3, 1. Rajzoljon fel egy, a felt´eteleknek megfelel˝o f´ at! Megold´ as: 1 2 4
3 5
6
Megjegyz´es: a 8 cs´ ucs az 5-nek baloldali gyereke is lehet.
7
8
pont(4): 5. Egy orsz´ag v´ arosai k¨oz¨ott csak busszal vagy vonattal tudunk k¨ ozlekedni. Minden X ´es Y v´ arosra (X = Y ) adott, hogy van-e olyan buszj´ arat, amivel a´tsz´ all´ as n´elk¨ ul el tudunk jutni X-b˝ ol Y -ba. Ha van ilyen j´arat, akkor adott az is, hogy X ´es Y k¨ oz¨ott mennyibe ker¨ ul egy buszjegy. Hasonl´ oan adottak a vonattal val´ o el´erhet˝os´egek ´es jegy´ar-inform´aci´ok is. Egy r¨ ogz´ıtett A v´ arosb´ ol szeretn´enk egy r¨ ogz´ıtett B v´ arosba eljutni a lehet˝o legolcs´ obb m´odon. Utunk sor´ an a´t is sz´ allhatunk ´es v´althatunk buszr´ ol vonatra, vonatr´ ol buszra, ak´ ar t¨ obbsz¨ or is. A legolcs´ obb u ´tvonal a´r´ anak meghat´ aroz´as´ara melyik ismert algoritmust haszn´aln´ a, ´es milyen bemeneten futtatn´ a azt?
Megold´ as: Dijkstra- vagy Bellman-Ford-algoritmus. arat, s´ ulya a kisebb k¨ olts´eg. A gr´ af cs´ ucsai a v´ arosok, kett˝ o k¨ oz¨ott akkor van ´el, ha van k¨ oz¨ott¨ uk busz vagy vonat j´ Az A-b´ ol a B-be keres¨ unk legr¨ ovidebb utat. pont(4):
1
6. Tegy¨ uk fel, hogy P = NP. Mindk´et al´abbi feladatra d¨ ontse el, hogy P-ben van-e: A G ir´ any´ıtatlan gr´ afban l´etezik (i) legfeljebb 100 ´el˝ uu ´t? (ii) legal´ abb k ´el˝ uu ´t (ha k r´esze a bemenetnek)?
Megold´ as: (i) P-beli (ii) nincs P-ben (mert NP-teljes).
pont(4):
7. Az A halmaz ´alljon azokb´ ol a G = (A, B, E) p´ aros gr´ afokb´ ol, melyekre van olyan X ⊆ E, hogy minden a ∈ A cs´ ucshoz l´etezik b ∈ B cs´ ucs, hogy {a, b} ∈ X, valamint {a1 , b1 }, {a2 , b2 } ∈ X eset´en a1 = a2 ⇔ b1 = b2 . V´azoljon egy polinom l´ep´essz´am´ u algoritmust, ami eld¨onti, hogy egy ´ellist´aval megadott G = (A, B, E) p´ aros gr´ af beletartozik-e az A halmazba!
Megold´ as: A magyar m´ odszert haszn´aljuk. Ha az ezzel tal´alt p´ aros´ıt´ as lefedi A-t, akkor G az A halmazhoz tartozik, egy´ebk´ent nem. pont(6): 8. Legyen s1 s2 . . . sn ´es t1 t2 . . . tm k´et olyan karaktersorozat, mely null´akb´ ol ´es egyesekb˝ol a´ll. Azt szeretn´enk, hogy az n × m m´eret˝ u A m´atrix A[i, j] eleme tartalmazza azt a legnagyobb k sz´amot, melyre az s1 s2 . . . si ´es a t1 t2 . . . tj karaktersorozatok utols´o k tagja megegyezik. Adjon elj´ ar´ ast, ami az A t¨ omb¨ ot O(nm) l´ep´esben kit¨ olti.
Egy lehets´eges megold´ as, ha az al´ abbi m´ odon ´es sorrendben t¨oltj¨ uk ki a t¨ omb elemeit (dinamikus programoz´ as). A[1, j] = A[i, 1] = A[i, j] =
0 1
ha ha
s1 = tj s 1 = tj
j = 1, . . . , m
0 1
ha ha
t1 si = s i = t1
i = 1, . . . , n
0 1 + A[i − 1, j − 1]
ha ha
tj si = s i = tj
i = 2, . . . , n, j = 2, . . . , m pont(6):
2
H
N´ev, azonos´ıt´ o: pont(15) :
1. Az al´ abbiak k¨ oz¨ ul mely(ek) nem a TCP feladata(i)? ´ a) Utvonalv´ alaszt´as b) Forgalomszab´ alyoz´ as c) V´ alt´ as a karakterk´eszletek k¨oz¨ott d) Sorrendhelyes a´tvitel e) A fentiek k¨ oz¨ ul mindegyik a TCP feladata. Megold´ as: a), c)
pont(2):
2. Melyik megfogalmaz´as ´ırja le legjobban a CIDR (Classless Inter-Domain Routing) l´enyeg´et az al´abbiak k¨ oz¨ ul? a) Alh´ al´ ozatokra osztjuk az A- vagy a B-oszt´ aly´ u tartom´ anyt. b) A c´ımtartom´ anyt b´ arhol meg lehet osztani h´al´ ozati ´es v´egpont-c´ımre. c) A c´ımtartom´ any egys´eges, nem oszlik h´al´ ozati ´es v´egpontc´ımre. d) A be´erkez˝o IP c´ım oszt´aly´ at´ ol f¨ uggetlen¨ ul a domainen bel¨ ul b´ armilyen priv´ at c´ımet kioszthatunk. e) A fentiek k¨ oz¨ ul egyik v´ alasz sem helyes. Megold´ as: b)
pont(2):
3. Az al´ abbiak k¨ oz¨ ul mely ISO OSI r´eteg(ek) nem tal´ alhat´ o(k) meg a TCP/IP modellben? a) Fizikai r´eteg b) Alkalmaz´ asi r´eteg c) Adatkapcsolati r´eteg d) Megjelen´ıt´esi r´eteg. e) H´ al´ ozati r´eteg f ) Viszonyr´eteg Megold´ as: d), f )
pont(2):
4. Az al´ abbiak k¨ oz¨ ul mely (al)r´eteg(ek)et tartalmazza az IEEE 802.3 szabv´any szerinti LAN-architekt´ ura? a) H´ al´ ozati r´eteg b) K¨ ozeghozz´af´er´esi alr´eteg c) Fizikai alr´eteg d) Menedzsment r´eteg e) A fentiek k¨ oz¨ ul egyiket sem tartalmazza Megold´ as: b), c)
pont(2):
5. V´ alassza ki az Ethernet keretek hossz´ara vonatkoz´o helyes ´all´ıt´ as(oka)t! a) Minimum´ at csak a c´ım hossza hat´arozza meg. b) Nincs maxim´alis hossz el˝o´ırva. c) A minim´ alis hossz´ us´ agot a k´ abelhossz ´es az ´atviteli sebess´eg alapj´ an hat´ arozt´ak meg. d) Kapcsolt Ethernetn´el nem sz´am´ıt a hossz´ us´ ag. e) A fentiek k¨ oz¨ ul egyik a´ll´ıt´ as sem helyes. Megold´ as: c)
pont(2):
6. Milyen szolg´ altat´ as(oka)t ny´ ujt az UDP? a) Sorrendhelyes a´tvitel 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 egyik szolg´ altat´ ast sem ny´ ujtja. Megold´ as: b)
pont(2):
3
7. Eg´esz´ıtse ki az al´abbi sz¨oveget egy-egy helyes sz´oval, r¨ ovid´ıt´essel! ,,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 v´egzi, melyre ................... r¨ ovid´ıt´essel hivatkozunk. Ennek a hierarchikus rendszernek a cs´ ucs´ at k´epezik a rootnak nevezett n´evfelold´ as´ert felel˝os kiszolg´ al´ ok. A terhel´es cs¨okkenthet˝ o, ha egy z´ on´ at t¨ obb szerver is kiszolg´al, vagy az u ´ gynevezett ...................... haszn´alat´ aval. Ez ut´ obbi elj´ar´ as azt jelenti, hogy ha a v´egpont – vagy a nev´eben elj´ ar´ o – 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.”
Megold´ as: IP; DNS; cache (gyors´ır´ ot´ ar)
pont(3):
4
O
N´ev, azonos´ıt´ o: pont(15) :
1. Adja meg, hogy az al´ abbi v´ alaszok k¨ oz¨ ul melyek igazak illetve hamisak ! (i) Szorosan csatolt (elosztott) rendszerekben az egyes g´epeknek nincs k¨ ul¨ on mem´ori´ aja. igaz – hamis (ii) Egy, csak egy folyamat a´ltal, kiz´ ar´ olagosan haszn´ alt file megnyit´ asa felhaszn´al´ oi m´odban t¨ ort´enik. igaz – hamis (iii) Lapszervez´es˝ u rendszerekben nem l´ep fel k¨ uls˝ o t¨ ordel˝ od´es. igaz – hamis (iv) A digit´ alis al´ a´ır´ as k´et c´elja: a k¨ uld˝ o szem´ely ´es a k¨ uld¨ ott sz¨oveg hiteles´ıt´ese. igaz – hamis (v) Egy folyamat munkahalmaz´ anak nevezz¨ uk a folyamat a´ltal egy adott id˝ ointervallum alatt haszn´alt lapok osszess´eg´et. ¨ igaz – hamis (vi) A ,,(bin´ aris) szemafor” univerz´alis szinkroniz´ aci´os eszk¨ oz, amely a ,,k¨olcs¨ on¨ os kiz´ar´ as”, a ,,halad´ as”, ´es a ,,v´eges v´arakoz´ asi id˝ o” felt´etel´et is biztos´ıtja. igaz – hamis pont(6): 2. Adja meg a helyes v´alaszt az al´abbi k´erd´esekre! (i) Az ´eppen fut´ o taszkot megszak´ıtja egy k¨ uls˝ o interrupt (IT). Preempt´ıv oper´ aci´os rendszer eset´en mindig a megszak´ıtott taszk fogja-e visszakapni a fut´ asi jogot az IT rutin v´egrehajt´asa ut´ an? igen – nem (ii) Ha folyamatok egy¨ uttm˝ uk¨ od´ese k¨oz¨os mem´ori´ an kereszt¨ ul val´ osul meg, akkor a PRAM modell szerint m˝ uk¨ od˝ o mem´oria o¨nmag´ aban biztos´ıtja-e a helyes m˝ uk¨ od´est? igen – nem (iii) Igaz-e, hogy a B´el´ady-f´ele anom´alia csak FIFO virtu´ alis lapcsere strat´egia alkalmaz´ asa eset´en k¨ ovetkezhet be? igen – nem pont(3): 3. V´ alassza ki, melyek azok a tulajdons´ agok, amelyek egyar´ ant jellemz˝oek a r¨ ovid-, k¨ oz´ep- ´es hossz´ ut´ av´ uu ¨ temez˝ ore az al´abbiak k¨ oz¨ ul: a) Valamilyen szempont szerint optimaliz´ alja (jav´ıtja) a rendszer m˝ uk¨ od´es´et. b) Biztos´ıtja a CPU 100%-os kihaszn´alts´ag´at. c) A kernel r´esze. d) A folyamatok er˝ oforr´ as-haszn´alat´ at szab´ alyozza valamilyen c´elf¨ uggv´eny szerint. e) Minden rendszerben megtal´alhat´ o. Megold´ as: a), d)
pont(2):
5
4. Egy oper´ aci´os rendszer a Shortest Remaining Time First (SRTF, legr¨ovidebb h´ atralev˝o l¨ oketidej˝ u) r¨ ovidt´ av´ u u ¨ temez´esi strat´egi´at alkalmazza. Az u ¨temez´esi sorba a k¨ovetkez˝ o folyamatok ´erkeznek.
P1 P2 P3
´ Erkez´ esi id˝o 0 1 3
L¨oketid˝ o 5 3 5
(i) Melyik folyamat fog futni az 5.–6. o´ra¨ ut´es k¨oz¨ott? (ii) Mennyi lesz a P3 folyamat v´ arakoz´ asi ideje?
Megold´ as: (i) P1; (ii) 5
pont(4):
6
S1
N´ev, azonos´ıt´ o: pont(10) :
1. Az al´ abbi UML2 diagram alapj´ an – a kulcs felhaszn´al´ as´aval – jellemezze az a´ll´ıt´ asokat!
A B C D E
– – – – –
ha mindk´et tagmondat igaz ´es a k¨ovetkeztet´es is helyes ha mindk´et tagmondat igaz, de a k¨ovetkeztet´es hamis ha csak az els˝o tagmondat igaz ha csak a m´asodik tagmondat igaz egyik tagmondat sem igaz
(+ + +) (+ + –) (+ –) (– +) (– –)
(i) W nem helyettes´ıthet˝o M-mel, mert W-nek nincs bar(z:Z) szignat´ ur´ aj´ u met´odusa.
(ii) W sort(x:X) met´ odusa megh´ıvhatja egy param´eter¨ ul kapott Y objektum foo() met´ odus´ at, mert Y-megval´os´ıtja az X interf´eszt. Megold´ as: D; D
pont(2):
2. Milyen elemek lehetnek egy adatfolyam´ abr´ an, bele´ertve a k¨ornyezeti (context) diagramot is? termin´ ator . . . . . . . . . . . . . . . . . . . . . . . . . . .
adatfolyam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
procesz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
adatt´ ar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . pont(2):
3. Mely f´ azis el˝ozi meg ´es k¨oveti a szoftverspecifik´ al´ ast ? El˝ oz˝o: K¨ ovetelm´eny. . . . . . . . . . . . . . . . . . .
K¨ ovetkez˝ o: Tervez´es . . . . . . . . . . . . . . . . . . . . . . . . pont(2):
7
4. Az InterCredit Bank felsz´ ol´ıt´ o levelet ´ır, amelyet elk¨ uld egyik u ¨gyfel´enek, Gerzsonnak, akinek hiteltartoz´ asa van. Gerzson a levelet elolvassa, majd a dar´ al´ on ledar´ alja. Rajzoljon UML2 szekvenciadiagramot!
sd w :Bank
:Ügyfél
:Daráló
create I:Levél küld(I) olvas darál(I)
pont(2): 5. T´etelezze fel, hogy a fenti t¨ort´enetben szerepl˝o objektumok oszt´ alyai k¨ oz¨ott nincs m´ as egy´eb – a t¨ ort´enetb˝ol nem kiolvashat´o – kapcsolat (pl. o¨r¨ okl´es)! Az al´abbi UML2 oszt´ alydiagramba rajzolja be az oszt´ alyok k¨ oz¨otti kapcsolatokat!
Ügyfél
Daráló
Bank
Levél pont(2):
8
S2
N´ev, azonos´ıt´ o: pont(10) :
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, mm´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(2): 2. Milyen a´ltal´ 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(2): 3. Mutasson egy C++, Java vagy C# megold´ ast (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!
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(2):
9
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 asok sor´ an m´ ar ezzel h´ıv´ askor ez l´etrehozza az u ´j objektumot, ´es elt´arolja az instance tagban. A k´es˝obbi h´ıv´ 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(2): 5. Adja meg r¨ oviden a webalkalmaz´asokra vonatkoz´ oan a szerveroldali szkript fogalm´ at!
Megold´ as: A webszerver ´altal futtatott szkript, melynek els˝odleges feladata a k´er´essel ´erkez˝o felhaszn´al´ oi input feldolgoz´ asa, ´es ennek f¨ uggv´eny´eben a kimeneti HTML oldal renderel´ese. pont(2):
10
AD
N´ev, azonos´ıt´ o: pont(10) :
1. V´egezzen rel´aci´oanal´ızist az al´abbi P–Q a´ll´ı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
– – – – –
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
P1: mivel Q1:
Egy tranzit´ıv funkcion´ alis f¨ ugg´es lehet trivi´ alis f¨ ugg´es is,
P2:
Ha egy legal´ abb 1NF rel´ aci´os s´ema minden kulcsa egyetlen attrib´ utumb´ ol a´ll, akkor a s´ema automatikusan legal´ abb 2NF is,
ez´ert Q2:
P3: mert Q3:
egy attrib´ utumhalmazt´ ol trivi´alisan f¨ ugg a r´eszhalmaz´anak r´eszhalmaza.
b´ armely pontosan 1NF s´em´at vesztes´egmentesen ´es f¨ ugg˝ os´eg˝orz˝oen fel lehet bontani legal´ abb 2NF r´eszs´em´akba. Egy els˝odleges attrib´ utum lehet kulcs, de nem felt´etlen¨ ul els˝ odleges kulcs az els˝odleges kulcs egy attrib´ utum, ami mindig els˝ odleges attrib´ utum.
as: B, B, C Megold´
pont(6):
2. T¨ obbsz¨ or¨ os v´alaszt´as (karik´ azza be valamennyi helyeset)! Az al´abbiak k¨ oz¨ ul melyiket z´ arj´ ak ki a BCNF s´em´ak? a) f¨ ugg˝ os´eg˝orz´es (nemtrivi´ alis f¨ ugg´eseket tartalmaz´o f¨ ugg´eshalmaz eset´en) b) ´ert´ekf¨ ugg˝ o k´enyszerek ´erv´enyes´ıt´ese c) funkcion´ alis f¨ ugg´es alap´ u redundancia d) nemtrivi´ alis funkcion´ alis f¨ ugg´es e) ¨ osszetett (nem atomi) attrib´ utum f ) t¨ obb kulcs egy s´em´aban g) m´asodlagos attrib´ utum h) ism´etl˝ od˝ o attrib´ utum´ert´ek Megold´ as: c), e)
pont(2):
3. Adja meg az F = {A → B, AB → CD, B → AC, CD → E, D → A} funkcion´ alis f¨ ugg´eshalmaz egy minim´alis fed´es´et!
Megold´ as: Fmin = {A → B, A → D (vagy B → D), A → C (vagy B → C), B → A, D → E, D → A} pont(2):
11
12
