Algoritmusok és gráfok ZH 2018 forrásának megtekintése

===NZH 2018.===
====1. feladat====
Igaz-e, hogy ha egy algoritmus lépésszáma <math>100\cdot n^22+10^{10}\cdot n+17</math>, akkor az algoritmus lépésszáma <math>O(n^2)</math>? Ha úgy véli, hogy ez igaz, akkor megfelelő <math>c</math> konstans és <math>n_0</math> küszöbérték megadásával lássa ezt be, ha pedig úgy véli, hogy hamis, akkor bizonyítsa be ezt.
====2. feladat====
Egy kezdetben üres, 11 méretű hash táblába nyílt címzéssel, lineáris próbával  szúrtunk be néhány egész számot, majd 2-t közülük kitöröltünk, így az alábbi állapotot kaptuk. (* jelöli a törölt cellákat, a kitöltetlen cellák mindvégig üresek voltak) A használt hash függvény a <math>h(K)=K</math> maradéka <math>11</math>-gyel osztva függvény volt.
{| class="wikitable"
|-
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
|-
| 11 || 1  || 26 || * || 15 ||    || 6  || * ||    ||    || 10
|}

* a, Mi lehetett az a <math>30</math>-nál kisebb pozitív egész szám, amit a 7-es cellából töröltünk? Az összes lehetőséget adja meg.
* b, Mi lehetett az a <math>30</math>-nál kisebb pozitív egész szám amit a 3-as cellából töröltünk? Az összes lehetőséget adja meg.
====3. feladat====
Egy bináris keresőfában az <math>1, 3, 8, 9, 10, 11, 13, 14</math> számokat tároljuk valamilyen elrendezésben és tudjuk, hogy amikor a <math>10</math>-et keressük akkor a keresés során először a <math>3</math>-as számot látjuk, utána a <math>13</math>-at, majd a <math>9</math>-et, végül pedig a <math>10</math>-et. Rajzolja fel azt a 8 csúcsú bináris keresőfát, ahol ez megtörténhetett, majd lássa be, hogy a fa csak így nézhet ki.
====4. feladat====
Egy <math>n</math> elemű rendezett tömbben pontosan 3 különböző érték szerepel. Adjon <math>O(log n)</math> lépésszámú algoritmust ennek a 3 értéknek a megkeresésére. Például ha az input <math>0, 0, 1, 1, 1, 8</math> akkor az elvárt kimenet <math>0, 1, 8</math>.
====5. feladat====
Egy szomszédossági mátrixával adott <math>n</math> csúcsú, egyszerű, irányított <math>G</math> gráfban minden csúcs színes: piros vagy kék. A csúcsok színei egy, a csúcsokkal indexelt <math>S</math> tömbben adottak. Adott továbbá 2 kijelölt csúcs, <math>s</math> (ez a csúcs piros) és <math>t</math> (ez a csúcs kék) és szeretnénk eldönteni, hogy van-e olyan irányított út <math>s</math>-ből <math>t</math>-be melyen a csúcsok felváltva pirosak és kékek. (Azaz minden páratlanadik csúcs piros, minden párosadik csúcs kék.) Úgy akarjuk megoldani ezt a feladatot, hogy módosítjuk <math>G</math> szomszédossági mátrixát oly módon, hogy ezután egy tanult algoritmus egyszeri futtatásával megkaphassuk az eredményt. Adjon <math>O(n^2)</math> lépésszámú algoritmust, ami megfelelően módosítja a szomszédossági mátrixot, majd alkalmazza a megfelelő tanult algoritmust.
====6. feladat====
Éllistájával adott egy <math>n</math> csúcsú, <math>2018n</math> élű, egyszerű, irányítatlan gráf. Adjon <math>O(n log n)</math> lépésszámú algoritmust annak eldöntésére, hogy van-e 2 olyan csúcs a gráfban, melyek fokszáma eggyel tér el.
===NPZH 2018.===
====1. feladat====
Az alábbi futási idők közül pontosan egyikre igaz, hogy <math>O(n^2)</math>.
* a, <math>2^{17}n^2+2018^2-100n log n</math>
* b, <math>\frac{10n^3}{log n}-10n^2</math>
Válassza ki, hogy melyik az és erre bizonyítsa is ezt be megfelelő <math>c</math> konstans és <math>n_0</math> küszöb megadásával.
====2. feladat====
Egy kezdetben üres, 11 méretű hash táblába nyílt címzéssel, lineáris próbával  szúrtunk be néhány egész számot, majd 2-t közülük kitöröltünk, így az alábbi állapotot kaptuk. (* jelöli a törölt cellákat, a kitöltetlen cellák mindvégig üresek voltak) A használt hash függvény a <math>h(K)=K</math> maradéka <math>11</math>-gyel osztva függvény volt.
{| class="wikitable"
|-
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
|-
| 11 || 1  || 26 || * || 15 || 16 || 6  || * ||    ||    || 10
|}

* a, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a <math>4</math>-es szám keresése során?
* b, Mely cellákas és milyen sorrendbe járjuk be ebben a táblában a <math>4</math>-es szám beszúrása során?

====3. feladat====
Egy bináris keresőfa preorder bejárása során a fa csúcsait <math>3, 10, 4, 8, 7, 9</math> sorrendben látogatjuk meg. Rajzolja fel ezt a 6 csúcsú bináris keresőfát, ahol ez megtörténhetett, majd lássa be, hogy a fa csak így nézhet ki.
====4. feladat====
Adott 2 tömb, mindegyik <math>n</math> különböző egész számot tartalmaz. Adjon <math>O(n log n)</math> lépésszámú algoritmust az összes olyan szám megkeresésére, amik mindkét tömbben benne vannak.
====5. feladat====
Egy szomszédossági mátrixával adott <math>n</math> csúcsú, egyszerű, irányított <math>G</math> gráfban 2 csúcs kivételével minden csúcs színes: piros vagy kék vagy zöld. A csúcsok színei egy, a csúcsokkal indexelt <math>S</math> tömbben adottak. A 2 színtelen csúcs <math>s</math> és <math>t</math> és az a célunk, hogy megkeressük az <math>s</math>-ből <math>t</math>-be vezető legrövidebb egyszínű út hosszát. Adjon <math>O(n^2)</math> lépésszámú algoritmust, ami a szomszédossági mátrix (esetleg többszöri) módosításával és egy tanult algoritmus (esetleg többszöri) változtatás nélküli futtatásával megoldja ezt a feladatot.
====6. feladat====
Éllistájával adott egy <math>n</math> csúcsú, <math>2018n</math> élű egyszerű, irányított gráf. Adjon <math>O(n)</math> lépésszámú algoritmust, ami megkeresi a gráfban előforduló legnagyobb be-fokot és az összes olyan csúcsot, amibe ennyi él fut be.