|
|
| 47. sor: |
47. sor: |
| === ZH === | | === ZH === |
| A félév során egy ZH van, melyen 60 pontot lehet elérni. | | A félév során egy ZH van, melyen 60 pontot lehet elérni. |
| | | ====Korábbi ZH-k==== |
| === NZH 2018. ===
| | *[[Algoritmusok és gráfok ZH 2018|NZH 2018]] |
| =====1. feladat===== | |
| Igaz-e, hogy ha egy algoritmus lépésszáma 100×n<sup>2</sup>+10<sup>10</sup>×n+17, akkor az algoritmus lépésszáma O(n<sup>2</sup>)? Ha úgy véli, hogy ez igaz, akkor megfelelő c konstans és n<sub>0</sub> 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 kettő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 h(K) = K maradéka 11-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
| |
| |}
| |
| | |
| <br />
| |
| a, Mi lehetett az a 30-nál kisebb pozitív egész szám, amit a 7-es cellából töröltünk?<br />
| |
| Az összes lehetőséget adja meg!<br />
| |
| b, Mi lehetett az a 30-nál kisebb pozitív egész szám amit a 3-as cellából töröltünk?<br />
| |
| Az összes lehetőséget adja meg!
| |
| =====3. feladat=====
| |
| Egy bináris keresőfában az 1, 3, 8, 9, 10, 11, 13, 14 számokat tároljuk valamilyen elrendezésben és tudjuk, hogy amikor a 10-et keressük akkor a keresés során először a 3-as számot látjuk, utána a 13-at, majd a 9-et, végül pedig a 10-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 n elemű rendezett tömbben pontosan három különböző érték szerepel. Adjon O(log n) lépésszámú algoritmust ennek a három értéknek a megkeresésére. Például ha az input 0, 0, 1, 1, 1, 8 akkor az elvárt kimenet 0, 1, 8.
| |
| =====5. feladat=====
| |
| Egy szomszédossági mátrixával adott n csúcsú, egyszerű, irányított G gráfban minden csúcs színes: piros vagy kék. A csúcsok színei egy, a csúcsokkal indexelt S tömbben adottak. Adott továbbá két kijelölt csúcs, s (ez a csúcs piros) és t (ez a csúcs kék) és szeretnénk eldönteni, hogy van-e olyan irányított út s-ből t-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 G szomszédossági mátrixát oly módon, hogy ezután egy tanult algoritmus egyszeri futtatásával megkaphassuk az eredményt. Adjon O(n<sup>2</sup>) 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 n csúcsú, 2018n élű, egyszerű, irányítatlan gráf. Adjon O(n log n) lépésszámú algoritmust annak eldöntésére, hogy van-e két olyan csúcs a gráfban, melyek fokszáma eggyel tér el.
| |
| === Vizsga === | | === Vizsga === |
| TODO | | TODO |