Test na Radiace a vyhľadávacie algoritmy

Otázka 1: Pri triedení vkladaním sa predpokladá, že prvý prvok zoznamu je už usporiadaný.

A. Áno

B. Nie

Vysvetlenie: Podľa postupu triedenia vkladaním je prvým krokom: 'Predpokladajte, že prvý prvok je už usporiadaný'.

Otázka 2: Ktorý z nasledujúcich krokov je charakteristický pre postup bublinkového triedenia (Bubble Sort)?

A. Nájdete stredný prvok zoznamu a porovnáte ho s hľadanou hodnotou, čím sa vyhľadávací priestor zmenší na polovicu.

B. Opakovane prechádzate zoznamom, porovnávate susedné prvky a vymieňate ich, ak sú v nesprávnom poradí, až kým sa neurobí žiadna výmena.

C. V každom prechode nájdete najmenší prvok v neusporiadanej časti zoznamu a vymeníte ho s prvým prvkom tejto neusporiadanej časti.

D. Rozdelíte zoznam na dve približne rovnaké polovice, rekurzívne ich triedite a potom zlučujete do jedného usporiadaného zoznamu.

Vysvetlenie: Bublinkové triedenie opakovane prechádza zoznamom, porovnáva susedné prvky a vymieňa ich, ak sú v nesprávnom poradí. Tento proces sa opakuje, kým sa v jednom prechode neurobí žiadna výmena, čo signalizuje, že zoznam je usporiadaný. Možnosť 0 popisuje binárne vyhľadávanie, možnosť 2 popisuje triedenie výberom a možnosť 3 popisuje triedenie zlučovaním.

Otázka 3: Binárne vyhľadávanie má časovú zložitosť O(log n) len v niektorých prípadoch.

A. Áno

B. Nie

Vysvetlenie: Časová zložitosť binárneho vyhľadávania je O(log n) vo všetkých prípadoch, nie len v niektorých, pretože v každom kroku sa vyhľadávací priestor zmenší na polovicu.

Otázka 4: Pri binárnom vyhľadávaní sa v každom kroku vyhľadávací priestor zmenší na polovicu.

A. Áno

B. Nie

Vysvetlenie: Podľa popisu časovej zložitosti sa v každom kroku binárneho vyhľadávania vyhľadávací priestor zmenší na polovicu, čo prispieva k rýchlemu nájdeniu prvku.

Otázka 5: Pri pokuse nájsť číslo 15 v usporiadanom zozname [5, 12, 18, 23, 30, 45, 50] pomocou binárneho vyhľadávania, ktorá z nasledujúcich možností správne popisuje krok vedúci k záveru, že prvok 15 sa v zozname nenachádza, podľa poskytnutého príkladu?

A. Po zúžení na pravú polovicu ([18]) je stredný prvok 18. Hľadaná hodnota 15 je menšia ako 18, čo vedie k ďalšiemu zúženiu na prázdny zoznam.

B. Po zúžení na ľavú polovicu ([5, 12, 18]) je stredný prvok 12. Hľadaná hodnota 15 je menšia ako 12, čo naznačuje, že prvok sa nenachádza.

C. Prvý stredný prvok je 23. Hľadaná hodnota 15 je menšia ako 23, a už v tomto kroku vieme, že 15 sa nenachádza v zozname.

D. Po zúžení na ľavú polovicu ([]) je zoznam prázdny, čo znamená, že prvok sa v zozname nenachádza.

Vysvetlenie: Podľa príkladu 2, po zúžení na pravú polovicu ([18]), je stredný prvok 18. Hľadaná hodnota 15 je menšia ako 18. Následne sa vyhľadávací priestor zúži na ľavú polovicu, ktorá je prázdna ([]), čo vedie k záveru, že prvok 15 sa v zozname nenachádza. Možnosť, ktorá presne popisuje tento krok vedúci k prázdnemu zoznamu je prvá. Ostatné možnosti buď popisujú iný krok alebo robia chybný záver.