Nemes Tihamér OKSzTV 2002

1. feladat: Rendezés (20 pont)

Az alábbi eljárások az N db különböző egész számot tartalmazó T tömb növekvő sorrendbe rendezésére készültek.

A. Mi a B változó szerepe az Egyik, illetve a B és a D változó szerepe a Másik eljárásban?
B. Hányszor hajtja végre Egyik a {*}, illetve Másik a {*}, {**}, {***} jellel megjelölt sorokat (az összehasonlító műveleteket)?
C. Melyik eljárásban kevesebb az összehasonlítások száma?
 

Egyik(T,N):   Ciklus i=0-tól N-1-ig     A:=T(i); B:=i     Ciklus j=i+1-től N-1-ig        Ha T(j)<A akkor A:=T(j); B:=j     {*}     Ciklus vége     T(B):=T(i); T(i):=A   Ciklus vége Eljárás vége.

Másik(T,N):   Ciklus i=0-tól N/2-1-ig     Ha T(i)<T(N-i-1)       {*}         akkor  A:=T(i); B:=i; C:=T(N-i-1); D:=N-i-1       különben A:=T(N-i-1); B:=N-i-1; C:=T(i); D:=i     Ciklus j=i+1-től N-i-2-ig       Ha T(j)<A akkor A:=T(j); B:=j    {**}       Ha C<T(j) akkor C:=T(j); D:=j    {***}     Ciklus vége     T(B):=T(i); T(D):=T(N-i-1); T(i):=A; T(N-i-1):=C   Ciklus vége Eljárás vége.

 

üres(sorozat)	igaz, ha a sorozat üres, hamis, ha nem
első(sorozat)	a sorozat első elemét adja
utolsó(sorozat)	a sorozat utolsó elemét adja
elsőnélküli(sorozat)	a sorozat első elem nélküli részsorozatát adja
utolsónélküli(sorozat)	a sorozat utolsó elem nélküli részsorozatát adja
elsőnek(elem,sorozat)	a sorozat első eleme elé szúrja be az új elemet
utolsónak(elem,sorozat)	a sorozat utolsó eleme mögé szúrja be az elemet

Az alábbi kölcsönösen rekurzív (azaz önmagukat és egymást hívó) függvénypárokat páros karakterszámú karaktersorozatokra (sztringekre) alkalmazzuk.
 

Egyik(S):   Ha üres(S) vagy üres(elsőnélküli(S)) akkor Egyik:=S   különben Egyik:=utolsónak(első(S),elsőnek(utolsó(S),                   Másik(elsőnélküli(utolsónélküli(S))))) Függvény vége.

Másik(S):   Ha üres(S) vagy üres(elsőnélküli(S)) akkor Másik:=S   különben Másik:=elsőnek(első(S),utolsónak(utolsó(S),                   Egyik(elsőnélküli(utolsónélküli(S))))) Függvény vége.

Alfa(S):   Ha üres(S) vagy üres(elsőnélküli(S)) akkor Alfa:=S   különben Alfa:=utolsónak(első(S),                  elsőnek(első(elsőnélküli(S)),                  Béta(elsőnélküli(elsőnélküli(S))))) Függvény vége.

Béta(S):   Ha üres(S) vagy üres(elsőnélküli(S)) akkor Béta:=S   különben Béta:=elsőnek(utolsó(S),                  utolsónak(utolsó(utolsónélküli(S)),                  Alfa(utolsónélküli(utolsónélküli(S))))) Függvény vége.

A. Mi az eredménye az Egyik("ABCDEF") függvényhívásnak? Fogalmazd meg általánosan is!
B. Mi az eredménye a Másik("ABCDEF"”) függvényhívásnak? Fogalmazd meg általánosan is!
C. Mi az eredménye az Alfa("ABCDEFGHIJ") függvényhívásnak? Fogalmazd meg általánosan is!
D. Mi az eredménye a Béta("ABCDEFGHIJ") függvényhívásnak? Fogalmazd meg általánosan is!

Az alábbi eljárás egy szövegben (s) keres egy másik szöveget (sminta). A szöveg csak az angol ábécé 26 nagybetűjét tartalmazza. A kód függvény minden betűhöz egy 0 és 25 közötti számot rendel (különböző betűkhöz különböző számot).
 

Eljárás Keresés(s,sminta,siker,i):   Konstans q : Egész(33554393)            d : Egész(26)   m:=Hossz(sminta); dh:=1; s1:=0; s2:=0   Ciklus i=1-től m-1-ig     dh:=(d*dh) mod q   Ciklus vége   Ciklus i=1-től m-ig     s1:=(s1*d+Kód(sminta(i))) mod q   Ciklus vége   Ciklus i=1-től m-ig     s2:=(s2*d+Kód(s(i))) mod q   Ciklus vége   i:=1   Ciklus amíg (s1*s2) és i*Hossz(s)-m     s2:=(s2+d*q-Kód(s(i))*dh) mod q     s2:=(s2*d+Kód(s(i+m))) mod q; i:=i+1   Ciklus vége   siker:=(s1=s2) Eljárás vége.

A. Milyen érték van a dh változóban? Mi az oka, hogy a maradékszámítást nem a ciklus lefutása után végezzük el?
B. Mi lesz s1 és s2 értéke az utolsó ciklus megkezdése előtt (mi közük az s és az sminta szöveges változókhoz)?
C. Hogyan, milyen elven változtatja s2 értékét az utolsó ciklus?
D. Van olyan eset, amikor az algoritmus leáll, a siker változó igaz értékű, pedig az s változóban nem található meg az sminta. Mi ennek a feltétele?

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	Nagy Péter	matematika	0	1A
102	Kiss Anna	matematika	104	1B
103	Kovács Pál	magyar	101	2A
104	Németh Erika	történelem	0	2B
105	Szabó János	magyar	101	3A
106	Horváth Zsuzsanna	kémai	104	3B
107	Kiss Etelka	rajz	0	4C

 

Osztályok
kód	város	létszám
1A	Budapest	40
2A	Budapest	36
3A	Budapest	32
1B	Miskolc	24
2B	Miskolc	26
3B	Miskolc	26
4C	Debrecen	20

A táblázatok lekérdezésére használható a SELECT utasítás:
 

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 hely = "Miskolc" OR hely = "Debrecen";

kiírja a miskolci és a debreceni osztályok kódját.
 

Példa:

Ha 6 autó van, az autók kezdeti sorrendje 3, 4, 1, 5, 6, 2, akkor 3 menet kell.

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?

A prioritási sor olyan adatszerkezet, amelybe az elemek a prioritásuknak (fontosságuknak) megfelelő helyre lépnek be, és amelyből a legmagasabb prioritású elem lép ki. Az alábbi eljárásokban a prioritási sort egy hossz darab elemet tartalmazó K tömb va-lósítja meg (kezdetben hossz=0).
 

Eljárás Sorba(e: ElemTip, p: Prioritás):   hossz:=hossz+1   K(hossz).elem:=e; K(hossz).pr:=p   gy:=hossz; sz:=gy DIV 2   Ciklus amíg sz>=1 és K(gy).pr>K(sz).pr     Csere(K(gy),K(sz)); gy:=sz; sz:=gy DIV 2   Ciklus vége Eljárás vége.

Eljárás Sorból(e: ElemTip, p: Prioritás):   e:=K(1).elem; p:=K(1).pr   sz:=1; K(1):=K(hossz); hossz:=hossz-1   gy:=2; Ha 2<hossz és K(2).pr<K(3).pr akkor gy:=3   Ciklus amíg sz<=hossz DIV 2 és K(gy).pr>K(sz).pr     Csere(K(sz),K(gy)); sz:=gy; gy:=sz*2     Ha gy<hossz és K(gy).pr<K(gy+1).pr akkor gy:=gy+1   Ciklus vége Eljárás vége.

A. Hol lesz a tömbben a legmagasabb prioritású elem?
B. Milyen összefüggés van a tömbben az egyes elemek sorrendje és prioritása között?
C. Mi a ciklusok maximális lépésszáma a két eljárásban?
D. Mi lesz lépésenként a K tömbben az alábbi műveletsor hatására: Sorba(A,5); Sorba(B,3); Sorba(C,7); Sorba(D,2); Sorba(E,4); Sorból(X,Y)?

Elérhető összpontszám: 100 pont