Test na Dátové štruktúry

Otázka 1: Uzol, ktorý má priameho potomka, sa v stromovej štruktúre nazýva koreň.

A. Áno

B. Nie

Vysvetlenie: Uzol, ktorý má priameho potomka, sa nazýva rodič. Koreň je najvyšší uzol v strome, ktorý nemá žiadneho rodiča.

Otázka 2: Ktoré z nasledujúcich akcií a pozorovaní sú možné pri interaktívnej simulácii Binárneho vyhľadávacieho stromu (BST) podľa študijných materiálov?

A. Sledovanie dynamickej reorganizácie stromu pri vkladaní hodnôt, aby si udržal vlastnosť menšie vľavo, väčšie vpravo.

B. Pozorovanie pohybu algoritmu po strome pri operáciách vyhľadávania a mazania.

C. Vizualizácia prechodov (inorder, preorder, postorder) a pochopenie poradia navštevovaných uzlov.

D. Experimentovanie s preplnením zásobníka a pozorovanie chybových stavov.

Vysvetlenie: Študijné materiály uvádzajú, že pri simulácii Binárneho vyhľadávacieho stromu je možné vkladať rôzne číselné hodnoty a sledovať jeho reorganizáciu (možnosť 0). Ďalej je možné vykonávať operácie vyhľadávania a mazania a vidieť, ako sa algoritmus pohybuje po strome (možnosť 1). Animácia prechodov (inorder, preorder, postorder) pomáha pochopiť poradie navštevovaných uzlov (možnosť 2). Možnosť 3, experimentovanie s preplnením zásobníka, sa týka simulácie zásobníka, nie BST.

Otázka 3: Zložitosť vyhľadávania v binárnom strome je v najhoršom prípade O(log n).

A. Áno

B. Nie

Vysvetlenie: Zložitosť vyhľadávania v binárnom strome je v najhoršom prípade O(n), kedy ide o degenerovaný strom. V priemere je zložitosť O(log n).

Otázka 4: Ktoré z nasledujúcich tvrdení o Inorder prechode binárneho stromu je správne na základe poskytnutých študijných materiálov?

A. Inorder prechod spracováva uzly v poradí: Ľavý podstrom → Koreň → Pravý podstrom.

B. Pre binárny vyhľadávací strom (BST) Inorder prechod vráti prvky v usporiadanom poradí.

C. Zložitosť Inorder prechodu je O(log n).

D. Inorder prechod spracováva uzly v poradí: Koreň → Ľavý podstrom → Pravý podstrom.

Vysvetlenie: Podľa študijných materiálov, Inorder prechod je definovaný ako spracovanie v poradí: Ľavý podstrom → Koreň → Pravý podstrom. Materiály tiež uvádzajú, že pre BST tento prechod vráti prvky v usporiadanom poradí. Zložitosť všetkých prechodov, vrátane Inorder, je O(n), nie O(log n). Poradie Koreň → Ľavý podstrom → Pravý podstrom patrí k Preorder prechodu.

Otázka 5: V matici susednosti pre vážený graf je hodnota prvku A[i][j] vždy rovná 1, ak existuje hrana z vrcholu 'i' do vrcholu 'j'.

A. Áno

B. Nie

Vysvetlenie: Podľa študijných materiálov, v matici susednosti pre vážený graf `A[i][j]` môže byť 1 alebo váha hrany, ak existuje hrana z 'i' do 'j'. Nie je vždy len 1.