Minta felvételi feladatsor programozásból 1. feladat: Rendezés (20 pont) A Comenius Logo egyik játékprogramjában békákat kell sorba rakni úgy, hogy lépésenként kijelölhetjük, hogy melyik béka ugorjon. Ugorni vagy csak szomszédos zsombékra lehet, vagy egy békát lehet átugrani. Kezdetben a jobboldali zsombék üres, s a sorba rakás után bármelyik (akár középen is) lehet üres. Add meg, hogy minimálisan hány ugrás szükséges ahhoz, hogy az alábbi ábrán látható békákat sorbarendezzük!
A.
D.
B.
E.
C. Példa:
Kezdőállapot:
1. lépés:
2. lépés:
Utolsó lépés: Értékelés: A. 1 lépés B. 2 lépés C. 7 lépés D. 5 lépés E. 9 lépés
4 pont 4 pont 4 pont 4 pont 4 pont
2. feladat: Szűrés (20 pont) Az alábbi három algoritmus az egyetlen sort tartalmazó X szöveges változó karakterei közül bizonyosakat a Z szöveges változóba ír. Add meg, hogy melyik eljárás milyen elemeket, illetve milyen elemsorozatokat nem másol át a Z változóba!
1
Minta felvételi feladatsor programozásból Első: Második: Z:='' Z:=''; L:=igaz Ciklus i=1-től hossz(X)-ig Ciklus i=1-től hossz(X)-ig Ha X[i]≠' ' akkor Z:=Z+X[i] Ha X[i]≠' ' vagy L akkor Z:=Z+X[i] L:=(X[i]≠' ') Ciklus vége Ciklus vége Eljárás vége. Eljárás vége. Harmadik: Z:=''; L:=hamis Ciklus i=1-től hossz(X)-ig Ha X[i]≠' ' vagy L akkor Z:=Z+X[i] L:=(X[i]≠' ') Ciklus vége Eljárás vége.
Értékelés: Első: kihagyja az összes szóközt Második: egymás melletti szóközökből pontosan egyet hagy meg Harmadik: egymás melletti szóközökből pontosan egyet hagy meg, de ha a sor elején szóközök vannak, azokat mind elhagyja
5 pont 5 pont 5 pont 5 pont
3. feladat: Áramkör (20 pont) Egy áramkör kétféle alapelemből épül fel. A vezetékek elágazásait festett körrel, bemeneteit és kimeneteit pedig üres + * Y1 Z1 Z0 Y0 körrel jelöljük. Minden vezeté+ + ken 0 vagy 1 értékű * jel van. A + jelű alapelem a két bemenete összegét adja modulo 2, a * jelű pedig a két U0 bemenetét összeszorozza. + Az alapelemekből felépítettük a mellékelt * * * hálózatot. U1 A. Határozd meg a hálózat U0, U1, U2 kime+ neteit, ha a bemenetei értéke: A1. Y0=0, Y1=0, Z0=0, Z1=0, + A2. Y0=1, Y1=1, Z0=1, Z1=1, A3. Y0=1, Y1=0, Z0=0, Z1=1, U
2 A4. Y0=0, Y1=1, Z0=0, Z1=1. B. Fogalmazd meg általánosan, hogyan függ az U kimenet az Y,Z bemenettől! Értékelés: A1. U0=0, U1=0, U2=0 1+1+1 pont A2. U0=0, U1=1, U2=1 1+1+1 pont A3. U0=1, U1=1, U2=0 1+1+1 pont A4. U0=0, U1=0, U2=1 1+1+1 pont B. Az áramkör kétbites összeadó, azaz 8 pont U0=(Y0+Z0) mod 2, AT0=(Y0+Z0) div 2
2
Minta felvételi feladatsor programozásból U1=(Y1+Z1+AT0) mod 2, AT1=(Y1+Z1+AT0) div 2 U2=AT1 4. feladat: Címletezés (20 pont) Egy pénztárban hatféle bankjegyet (címletet) kezelnek. Az alábbi címletező algoritmus, szándékunk szerint, meghatározza, hogy a P összeg hogyan fizethető ki a lehető legkevesebb bankjeggyel. Az eredményt a DB vektor tartalmazza. Minden címletből korlátlan mennyiség használható fel. Címletezés(P,C,DB): K:=6; DB:=(0,0,0,0,0,0) Ciklus amíg P>0 Ciklus amíg P≥C(K) DB(K):=DB(K)+1; P:=P-C(K) Ciklus vége K:=K-1 Ciklus vége Eljárás vége. Ez az algoritmus például a C=(1,2,5,10,20,50) címletkészlet és 96 forint kifizetése esetén a DB=(1,0,1,0,2,1) vektort állítja elő. Legyenek a címletkészletek a következők: i) C=(1,3,6,10,60,100) iii) C=(1,2,5,12,60,120) ii) C=(1,4,6,10,40,60) iv) C=(1,5,7,21,35,49) A. Mi lesz a DB vektor értéke 73 forint kifizetésekor a négy címletkészlet esetén? B. A négy címletkészlet közül melyeknél címletez hibásan az algoritmus (azaz nem a lehető legkevesebb bankjegyet használja fel)? C. Minden hibás eredményhez vezető címletkészletre add meg azt a legkisebb P összeget, amelynek a kifizetésére az algoritmus nem a lehető legkevesebb bankjegyet használja fel! Add meg az algoritmus által előállított hibás, valamint a helyes DB vektort is! Értékelés: A. i) DB=(0,1,0,1,1,0) 1 pont ii) DB=(3,0,0,1,0,1) 2 pont iii) DB=(1,0,0,1,1,0) 2 pont iv) DB=(3,0,0,1,0,1) 2 pont B. Hibás: i), ii), iv), jó: iii) 1+1+1+1 pont C. i) P=12, algoritmus=(2,0,0,1,0,0), helyes=(0,0,2,0,0,0) 1+1+1 pont ii) P=8, algoritmus=(2,0,1,0,0,0), helyes=(0,2,0,0,0,0) 1+1+1 pont iv) P=10, algoritmus=(3,0,1,0,0,0), helyes=(0,2,0,0,0,0) 1+1+1 pont 5. feladat: Adatbázis (20 pont) A SZÉTSZÓRT iskola több város több épületében működik. Az osztályokról és az osztályfőnökökről nyilvántartást készítettünk (lásd a két táblázatot). Városonként egy osztályfőnököt vezetőnek neveztek ki. Osztályfőnökök azon
név
szak
vezető
osztály
101 102 103
Nagy Péter Kiss Anna Kovács Pál
Matematika Matematika Magyar
0 104 101
1A 1B 2A
3
Minta felvételi feladatsor programozásból 104 105 106 107
Németh Erika Szabó János Horváth Zsuzsanna Kiss Etelka Osztályok
kód
város
létszám
1A 2A 3A 1B 2B 3B 4C
Budapest Budapest Budapest Miskolc Miskolc Miskolc Debrecen
40 36 32 24 26 26 20
Történelem Magyar Kémia Rajz A táblázatok SELECT utasítás:
0 101 104 0 lekérdezésére
2B 3A 3B 4C használható
a
SELECT oszlopnév, oszlopnév, ... FROM táblázatnév, táblázatnév, ... WHERE logikai kifejezés;
A logikai kifejezésben műveleti jel (pl. VAGY, ÉS, =, <, >=), állandó (pl. "Miskolc"), oszlopnév (pl. város) vagy zárójelben egy újabb, beágyazott SELECT utasítás használható. A lekérdezés azokat a sorokat (két táblázat esetén: sorpárokat) választja ki a táblázat(ok)ból, amelyekre a logikai kifejezés teljesül. Minden kiválasztott sorból, illetve sorpárból csak a megnevezett oszlopok adatait kapjuk eredményül. A nem beágyazott SELECT utasítás kiírja az eredményt a képernyőre. Például SELECT kód FROM osztályok WHERE város="Miskolc" OR város="Debrecen";
kiírja a miskolci és a debreceni osztályok kódját. A: Milyen parancs írja ki A1: a 30-nál kisebb létszámú osztályok kódját és létszámát? A2: a Debrecenben dolgozók nevét és osztályuk létszámát? B: Mit ír ki az alábbi SELECT parancs? SELECT név FROM Osztályfőnökök WHERE vezető = (SELECT azon FROM Osztályfőnökök WHERE név = "Nagy Péter"); C: Milyen parancs írja ki azon főnökök nevét, akiknek van Magyar szakos beosztottja? Értékelés: A1: SELECT kód, létszám 2 pont FROM Osztályok 2 pont WHERE létszám < 30 2 pont A2: SELECT név, létszám 2 pont FROM Osztályfőnökök, Osztályok 2 pont WHERE osztály=kód AND város="Debrecen" 2 pont B: Kiírt nevek: Kovács Pál, Szabó János 1+1 pont Minden hibáért egy pont levonás jár a 2-ből! C. SELECT név 1 pont FROM Osztályfőnökök 1 pont WHERE azon=(SELECT vezető 1+1 pont FROM Osztályfőnökök 1 pont
4
Minta felvételi feladatsor programozásból WHERE szak=”Magyar”)
5
1 pont