Test on Összefésülő rendezés (merge sort)

Question 1: Az összefésülő rendezésnél a segédtömb helytelen méretezése általában csak kisebb teljesítménycsökkenést okoz, de nem vezet programhibához vagy memória szivárgáshoz.

A. Yes

B. No

Explanation: A tanulmányi anyag szerint a segédtömb helytelen méretezése vagy felszabadításának elmulasztása kritikus memória kezelési hibához vezethet, ami memória szivárgást vagy programhibát okozhat.

Question 2: Az "oszd meg és uralkodj" paradigmát követő összefésülő rendezés három fő lépésből áll. Melyik opció írja le HELYESEN ezen lépések egyikét?

A. A 'Felosztás' lépés során az alproblémák megoldásait egyesítik az eredeti probléma megoldásához.

B. Az 'Uralkodás' lépés rekurzívan oldja meg az alproblémákat, amíg azok triviálisan megoldhatóvá nem válnak, mint például egy egyelemű lista.

C. Az 'Összefésülés' lépésben a rendezendő listát két nagyjából egyenlő méretű részre osztják.

D. Az 'Uralkodás' lépés csak akkor kezdődik el, miután az összes alprobléma egyetlen elemet tartalmazó listává vált, és ekkor kezdődnek a tényleges összehasonlítások.

Explanation: Az "Uralkodás" lépés lényege, hogy az alproblémákat rekurzívan oldja meg, egészen addig, amíg olyan kicsik nem lesznek, hogy triviálisan megoldhatók, mint például egy egyelemű lista. Az első opció a 'Felosztás' lépést helytelenül az 'Összefésülés' definíciójával írja le. A harmadik opció az 'Összefésülés' lépést hibásan a 'Felosztás' definíciójával keveri. A negyedik opció félreérti az 'Uralkodás' rekurzív természetét, ami nem csak egyelemű listák esetén kezdődik, hanem a rekurzió része.

Question 3: Az összefésülő rendezés időkomplexitását leíró rekurziós relációban a 2T(n/2) rész azt jelenti, hogy két n/2 méretű alproblémát oldunk meg rekurzívan.

A. Yes

B. No

Explanation: A tanulmányi anyag pontosan ezt állítja: "Ez azt jelenti, hogy egy n méretű probléma megoldásához két n/2 méretű alproblémát oldunk meg rekurzívan (ez a 2T(n/2) rész), majd az eredményeket O(n) idő alatt összefésüljük (ez az O(n) rész)."

Question 4: A buborékrendezés vagy a beszúrásos rendezés hatékonyabb nagy adathalmazok esetén, mint az összefésülő rendezés.

A. Yes

B. No

Explanation: A tanulmányi anyag szerint a legegyszerűbb rendezési algoritmusok (pl. buborékrendezés, beszúrásos rendezés) időkomplexitása O(n²), míg az összefésülő rendezésé O(n log n). O(n²) sokkal lassabb nagy adathalmazok esetén, mint O(n log n), ezért az egyszerűbb rendezések nem hatékonyabbak.

Question 5: Mekkora nagyságrendű a különbség egy O(n log n) időkomplexitású és egy O(n²) időkomplexitású algoritmus lépésszáma között, ha n = 1 000 000?

A. Az O(n log n) algoritmus körülbelül 20 millió lépést igényel, míg az O(n²) algoritmus körülbelül 1 billió lépést, ami óriási különbség.

B. Mindkét algoritmus körülbelül 1 billió lépést igényel, így a különbség elhanyagolható.

C. Az O(n log n) algoritmus körülbelül 20 millió lépést igényel, míg az O(n²) algoritmus körülbelül 20 milliárd lépést, ami jelentős különbség.

D. Az O(n log n) algoritmus körülbelül 1 billió lépést igényel, míg az O(n²) algoritmus körülbelül 20 millió lépést, így az O(n²) a gyorsabb.

Explanation: A tananyag szerint, ha n = 1 000 000, az O(n log n) időkomplexitású algoritmus hozzávetőlegesen 20 000 000 lépést (20 millió) igényel, míg az O(n²) időkomplexitású algoritmus 1 000 000 000 000 lépést (1 billió). Ez a különbség óriási.