Test na Dynamické dátové štruktúry a algoritmy

Otázka 1: Žiadny porovnávací triediaci algoritmus nemôže byť asymptoticky rýchlejší ako Ω(n log n).

A. Áno

B. Nie

Vysvetlenie: Študijné materiály uvádzajú, že „Pre porovnávacie triedenie platí: Ω(nlogn) – žiadny porovnávací algoritmus nemôže byť asymptoticky rýchlejší“.

Otázka 2: Časová zložitosť O(log n) vyjadruje lineárnu zložitosť algoritmu.

A. Áno

B. Nie

Vysvetlenie: Časová zložitosť O(log n) vyjadruje logaritmickú zložitosť. Lineárna zložitosť je vyjadrená ako O(n).

Otázka 3: Ktoré tvrdenie o porovnaní triediacich algoritmov Merge Sort a Quick Sort je správne?

A. Merge Sort má v najhoršom prípade časovú zložitosť O(n²), zatiaľ čo Quick Sort má O(n log n).

B. Quick Sort je stabilný algoritmus, zatiaľ čo Merge Sort nie je.

C. Merge Sort vyžaduje dodatočnú pamäť O(n), kým Quick Sort vyžaduje O(log n).

D. Oba algoritmy majú v priemernom prípade rovnakú časovú zložitosť O(n²).

Vysvetlenie: Podľa študijných materiálov má Merge Sort pamäťovú zložitosť O(n), zatiaľ čo Quick Sort má pamäťovú zložitosť O(log n). Ostatné tvrdenia sú nesprávne: Merge Sort má v najhoršom prípade O(n log n) a Quick Sort O(n²); Merge Sort je stabilný a Quick Sort nie je; oba algoritmy majú v priemernom prípade časovú zložitosť O(n log n), nie O(n²).

Otázka 4: Ktoré tvrdenie o hašovaní a kolíziách je správne?

A. Hašovanie je technika, pri ktorej sa prvok pomocou hašovacej funkcie priamo mapuje na pozíciu v tabuľke.

B. Kolízia nastáva, keď dva rôzne kľúče majú rovnaký index v tabuľke.

C. Dobrá hašovacia funkcia by mala minimalizovať kolízie a rovnomerne rozdeľovať prvky.

D. Pri hašovaní reťazením sa kolízie riešia tak, že nový prvok prepíše existujúci prvok na danom indexe.

Vysvetlenie: Podľa študijných materiálov je hašovanie technika, pri ktorej sa prvok pomocou hašovacej funkcie priamo mapuje na pozíciu v tabuľke. Kolízia nastáva, keď dva rôzne kľúče majú rovnaký index v tabuľke. Dobrá hašovacia funkcia rovnomerne rozdeľuje prvky, minimalizuje kolízie a je rýchla na výpočet. Tvrdenie, že pri hašovaní reťazením nový prvok prepíše existujúci, je nesprávne; namiesto toho sa nový prvok pridá do zoznamu na danom indexe.

Otázka 5: V reprezentácii grafu pomocou zoznamu susedov je jednou z výhod rýchlejšie zisťovanie existencie konkrétnej hrany.

A. Áno

B. Nie

Vysvetlenie: Študijné materiály uvádzajú, že nevýhodou reprezentácie grafu pomocou zoznamu susedov je práve pomalšie zisťovanie konkrétnej hrany, nie rýchlejšie.