Test on Rendezési és keresési algoritmusok

Question 1: Az O(2ⁿ) exponenciális idővel jellemezhető algoritmusok futási ideje exponenciálisan növekszik az input méretével, és jellemzően csak kis bemenetek esetén alkalmazhatók.

A. Yes

B. No

Explanation: Az O(2ⁿ) – Exponenciális idő fejezet szerint az algoritmus futási ideje exponenciálisan növekszik az input méretével, és a leírás kiemeli, hogy „Nagyon lassú, csak kis inputokra használható”.

Question 2: Mely állítások írják le pontosan, hogy mit segíthet megérteni a Gyorsrendezés szimulációja a mellékelt tananyag alapján?

A. A pivot elem kiválasztását és a tömb két részre osztását.

B. A szomszédos elemek cseréjét és a nagyobb elemek „felbuborékolását” a lista végére.

C. A gyorsrendezés O(n log n) átlagos és O(n²) legrosszabb esete közötti különbséget.

D. A rekurzív hívásokat és a résztömbök rendezését.

Explanation: A tanulmányi anyag szerint a gyorsrendezés vizualizációja bemutatja a pivot elem kiválasztását és a particionálási folyamatot, ahol a tömb két részre oszlik (0. opció). Továbbá követhetőek a rekurzív hívások és a résztömbök rendezése (3. opció). Segít megérteni az O(n log n) átlagos és az O(n²) legrosszabb eset közötti különbséget is (2. opció). A szomszédos elemek cseréje és a nagyobb elemek „felbuborékolása” a buborékrendezésre jellemző, nem a gyorsrendezésre (1. opció).

Question 3: A mellékelt példában a lineáris keresés során a `8` érték az első lépésben megtalálásra kerül.

A. Yes

B. No

Explanation: A lineáris keresés példájában a `8` érték a 4. lépésben kerül megtalálásra, miután az első három elem (`12`, `5`, `23`) nem egyezett a keresett értékkel.

Question 4: A lineáris keresés legjobb esete O(n) időkomplexitású.

A. Yes

B. No

Explanation: A lineáris keresés legjobb esete O(1) időkomplexitású, amely akkor fordul elő, ha a keresett elem az első az adathalmazban, és nem O(n).

Question 5: Melyik állítás írja le HELYESEN a lineáris és bináris keresési algoritmusok közötti különbséget a rendelkezésre álló tananyag alapján?

A. A lineáris keresés gyorsabb rendezett adathalmazokon, míg a bináris keresés bármilyen adathalmazon hatékony.

B. A lineáris keresés nem igényli az adathalmaz rendezettségét, míg a bináris keresés csak rendezett adathalmazon alkalmazható.

C. A bináris keresés legrosszabb esetbeli időkomplexitása O(n), a lineáris keresésé pedig O(log n).

D. A bináris keresés a „felezd és uralkodj” elven működik, míg a lineáris keresés elemeket hasonlít össze sorban a keresett értékkel.

Explanation: A tananyag szerint a lineáris keresésnek nincs szüksége arra, hogy az adathalmaz rendezett legyen, a bináris keresés viszont csak rendezett adathalmazokon alkalmazható. Ezért a második opció helyes. Továbbá, a bináris keresés a „felezd és uralkodj” elven működik, míg a lineáris keresés sorban vizsgálja az elemeket, összehasonlítva az aktuális elemet a keresett értékkel, ami a negyedik opció helyességét támasztja alá. Az első opció téves, mert a lineáris keresés jellemzően lassabb, és a bináris keresés korlátozottan, csak rendezett adathalmazokon hatékony. A harmadik opció szintén téves, mivel a bináris keresés időkomplexitása O(log n), a lineáris keresésé pedig O(n) a legrosszabb esetben.