Test on Lineáris és bináris keresés
Lineáris és Bináris Keresés: Összehasonlítás Diákoknak
Test: Keresési algoritmusok
20 questions
Question 1: A bináris keresés működése során minden lépésben kizárja az adathalmaz felét, ahol a keresett érték biztosan nem lehet.
A. Yes
B. No
Explanation: A bináris keresés a „felezd és uralkodj” elven alapul, és az algoritmus minden lépésben kizárja az adathalmaz felét, ahol a keresett érték biztosan nem lehet.
Question 2: A bináris keresés hatékonyan alkalmazható rendezetlen adathalmazokon is, anélkül, hogy előzetes rendezésre lenne szükség.
A. Yes
B. No
Explanation: A bináris keresésnek alapvető előfeltétele, hogy az adathalmaznak rendezettnek kell lennie. Ha az adathalmaz nincs rendezve, a bináris keresés helytelen eredményt ad, vagy egyáltalán nem találja meg az elemet.
Question 3: A `[12, 5, 28, 17, 3, 42]` listában a `17` érték lineáris kereséssel történő megtalálásához kevesebb, mint négy összehasonlításra van szükség a tananyagban bemutatott példa szerint.
A. Yes
B. No
Explanation: A lineáris keresés példájában a `[12, 5, 28, 17, 3, 42]` listában a `17`-es szám keresése a következő lépéseket mutatja be: Először a `12`-t hasonlítjuk össze `17`-tel (1. összehasonlítás), majd az `5`-öt `17`-tel (2. összehasonlítás), aztán a `28`-at `17`-tel (3. összehasonlítás), végül a `17`-et `17`-tel (4. összehasonlítás), ahol egyezést talál. Tehát pontosan négy összehasonlítás szükséges.
Question 4: A lineáris keresés a bináris kereséshez képest akkor is hatékonyabb lehet bizonyos esetekben, ha az adathalmaz nagyon kicsi, és a bináris keresés inicializálási költségei meghaladnák a gyorsabb keresés előnyét.
A. Yes
B. No
Explanation: A tanulmányi anyag szerint: 'Kis adathalmazok (pl. 10-20 elem) esetén a két algoritmus közötti sebességkülönbség nem feltétlenül drámai. Sőt, a bináris keresés inicializálási költségei (alsó/felső indexek beállítása, középső elem számítása) miatt akár lassabbnak is tűnhet néhány esetben, ha az adathalmaz nagyon kicsi.'
Question 5: A bináris keresés a legoptimálisabb megoldás egy nagyon kicsi, rendezetlen adathalmazban történő egyszeri keresésre, mivel elkerüli a lineáris keresés lehetséges lassúságát.
A. Yes
B. No
Explanation: A tanulmányi anyag szerint kis adathalmazoknál, vagy ha csak egyszer kell keresni egy rendezetlen listában, a lineáris keresés egyszerűsége és a rendezés elhagyása miatt gyorsabb lehet, mint a rendezés + bináris keresés kombinációja. A bináris keresés előfeltétele a rendezett adathalmaz.