Test na Triedenie zlučovaním (merge sort)
Triedenie zlučovaním (Merge Sort): Kompletný Rozbor pre študentov
Test: Triedenie zlučovaním (Merge Sort)
20 otázok
Otázka 1: Triedenie zlučovaním (Merge Sort) nezachováva relatívne poradie rovnakých prvkov v poli po dokončení triedenia.
A. Áno
B. Nie
Vysvetlenie: Merge Sort je stabilný triediaci algoritmus, čo znamená, že zachováva relatívne poradie rovnakých prvkov. Ak sú v pôvodnom poli dva rovnaké prvky, ich poradie sa po triedení nezmení.
Otázka 2: Triedenie zlučovaním je algoritmus založený na princípe „rozdeľ a panuj“.
A. Áno
B. Nie
Vysvetlenie: Študijné materiály explicitne uvádzajú, že triedenie zlučovaním je založené na princípe „rozdeľ a panuj“ (Divide and Conquer).
Otázka 3: Štandardná implementácia algoritmu Merge Sort nepotrebuje dodatočný pamäťový priestor pre dočasné polia, pretože zlučovanie vykonáva priamo do pôvodného poľa.
A. Áno
B. Nie
Vysvetlenie: Študijné materiály jasne uvádzajú, že pamäťová náročnosť Merge Sort je O(n), čo znamená, že algoritmus vyžaduje dodatočný pamäťový priestor pre dočasné polia, ktoré sa používajú počas fázy zlučovania. Je tiež spomenutá mylná predstava, že ide o in-place algoritmus, pričom sa potvrdzuje, že štandardná implementácia vyžaduje O(n) dodatočného priestoru.
Otázka 4: Simulácia triedenia zlučovaním zobrazuje strom delenia, ktorý sa rozvetvuje smerom nadol, pričom listové uzly stromu delenia predstavujú jednoprvkové polia.
A. Áno
B. Nie
Vysvetlenie: Študijné materiály uvádzajú, že vo fáze delenia simulácia triedenia zlučovaním zobrazuje strom, ktorý sa rozvetvuje smerom nadol, pričom každý uzol predstavuje podpole a jeho deti sú jeho rozdelené polovice. Tento proces pokračuje, kým sa nedostanete k listovým uzlom, ktoré predstavujú jednoprvkové polia.
Otázka 5: Doba behu algoritmu triedenia zlučovaním (Merge Sort) sa zvyšuje lineárne s veľkosťou vstupu pre rôzne veľkosti polí.
A. Áno
B. Nie
Vysvetlenie: Doba behu algoritmu triedenia zlučovaním sa zvyšuje logaritmicky s veľkosťou vstupu, nie lineárne.