Test na Graf a prehľadávanie do šírky a do hĺbky

Otázka 1: Môžu byť k hranám v grafe priradené číselné hodnoty, ktoré reprezentujú vzdialenosť, čas alebo náklady?

A. Áno

B. Nie

Vysvetlenie: Grafy môžu byť vážené, ak sú k hranám priradené číselné hodnoty (váhy), ktoré môžu reprezentovať napríklad vzdialenosť, čas alebo náklady.

Otázka 2: Pre maticu susednosti je pamäťová náročnosť O(V + E), kde E je počet hrán, čo je výhodné pre riedke grafy.

A. Áno

B. Nie

Vysvetlenie: Podľa študijných materiálov je pamäťová náročnosť matice susednosti O(V²), dokonca aj pre riedke grafy. Zoznam susednosti má pamäťovú náročnosť O(V + E).

Otázka 3: Aká je asymptotická časová zložitosť algoritmov BFS (prehľadávanie do šírky) a DFS (prehľadávanie do hĺbky) podľa poskytnutých študijných materiálov?

A. O(V + E)

B. O(V^2)

C. O(V * E)

D. O(log V)

Vysvetlenie: Študijné materiály explicitne uvádzajú, že "Oba algoritmy sú efektívne pre prehľadávanie grafov a majú rovnakú asymptotickú časovú zložitosť O(V + E)".

Otázka 4: Ktoré tvrdenia správne popisujú princíp a kroky algoritmu prehľadávania do šírky (BFS) podľa dodaných študijných materiálov?

A. BFS prehľadáva graf po vrstvách a využíva dátovú štruktúru front (FIFO).

B. Na začiatku algoritmu sa všetky vrcholy označia ako nenavštívené, vytvorí sa zásobník a pridá sa do neho počiatočný vrchol.

C. Počas opakovaných krokov sa vyberie vrchol z frontu a všetci jeho nenavštívení susedia sa označia ako navštívení a pridajú sa do frontu.

D. BFS zaručuje nájdenie najkratšej cesty v nevážených grafoch v zmysle minimálneho počtu hrán, pretože prehľadáva graf do hĺbky.

Vysvetlenie: Prvé tvrdenie je správne, pretože materiály uvádzajú, že 'Algoritmus BFS prehľadáva graf po vrstvách' a 'Používa dátovú štruktúru front (FIFO)'. Druhé tvrdenie je nesprávne, pretože BFS používa front, nie zásobník, ako je uvedené v časti 'Princíp BFS'. Tretie tvrdenie je správne, pretože materiály popisujú opakované kroky ako 'Vyberie sa vrchol u z frontu. Pre všetkých nenavštívených susedov v vrcholu u: Označí sa v ako navštívený. Pridá sa v do frontu.' Štvrté tvrdenie je nesprávne, pretože hoci BFS nájde najkratšiu cestu v nevážených grafoch, prehľadáva ich po vrstvách, nie do hĺbky.

Otázka 5: Počas krokovania DFS z vrcholu A, po tom, ako je navštívený vrchol F, sa ďalší volanie DFS uskutoční pre vrchol C.

A. Áno

B. Nie

Vysvetlenie: Podľa krokovania DFS v študijných materiáloch, po navštívení vrcholu F (Krok 4), je ďalšie volanie DFS pre vrchol E (Zavolaj DFS(E)), nie pre C. Volanie DFS(C) nastane až neskôr, z vrcholu E (Krok 6).