Test na Bublinkové triedenie (bubble sort)
Bublinkové Triedenie (Bubble Sort): Kompletný Rozbor pre Študentov
Test: Bublinkové triedenie
20 otázok
Otázka 1: Je bublinkové triedenie považované za algoritmus, ktorý na svoju činnosť vyžaduje konštantné množstvo dodatočnej pamäte?
A. Áno
B. Nie
Vysvetlenie: Bublinkové triedenie je triediaci algoritmus „na mieste“ (in-place), čo znamená, že na svoju činnosť potrebuje len minimálne dodatočné miesto v pamäti, nezávislé od veľkosti vstupu. Potrebuje len niekoľko premenných na uloženie indexov a dočasnú premennú na výmenu prvkov. Preto je jeho priestorová zložitosť konštantná, O(1).
Otázka 2: Vo všeobecnom pseudokóde bublinkového triedenia s vnútorným cyklom `PRE j OD 0 DO n - i - 2 KROK 1` porovnáva algoritmus susedné prvky až po posledný prvok zoznamu v každom prechode vonkajšieho cyklu.
A. Áno
B. Nie
Vysvetlenie: Podľa pseudokódu a textu sa vnútorný cyklus `PRE j OD 0 DO n - i - 2 KROK 1` (pre porovnanie `zoznam[j]` a `zoznam[j+1]`) skracuje. Po každom prechode vonkajšieho cyklu sa najväčší prvok presunie na svoju správnu pozíciu na konci netriedenej časti zoznamu. To znamená, že vnútorný cyklus neporovnáva prvky až po úplne posledný prvok zoznamu v každom prechode, ale iba po predposledný netriedený prvok, čím sa efektívne skracuje o počet už usporiadaných prvkov.
Otázka 3: Je hlavnou výhodou bublinkového triedenia ľahká pochopiteľnosť a implementácia?
A. Áno
B. Nie
Vysvetlenie: Hlavnou výhodou bublinkového triedenia je ľahká pochopiteľnosť a implementácia, čo ho robí vhodným na úvod do štúdia algoritmov.
Otázka 4: Pre bublinkové triedenie nastáva najhorší prípad časovej zložitosti O(n²), keď je zoznam už usporiadaný vo vzostupnom poradí.
A. Áno
B. Nie
Vysvetlenie: Najhorší prípad časovej zložitosti O(n²) pre bublinkové triedenie nastáva, keď je zoznam usporiadaný v opačnom poradí (napríklad zostupne pri vzostupnom triedení). Keď je zoznam už usporiadaný, nastáva najlepší prípad časovej zložitosti O(n), ak sa použije optimalizácia s príznakom výmeny.
Otázka 5: Simulácia bublinkového triedenia vždy zobrazuje počítadlo porovnaní a výmen.
A. Áno
B. Nie
Vysvetlenie: Študijné materiály uvádzajú, že 'Ak simulácia zobrazuje počítadlo porovnaní a výmen, sledujte, ako sa tieto čísla menia'. Formulácia 'Ak simulácia zobrazuje...' naznačuje, že nie každá simulácia musí nutne zobrazovať počítadlo porovnaní a výmen. Preto tvrdenie, že ich 'vždy zobrazuje', nie je pravdivé.