Test na Binárny vyhľadávací strom

Otázka 1: V prípade mazania uzla z binárneho vyhľadávacieho stromu, ktorý má dvoch potomkov, je vždy najjednoduchšou stratégiou nájsť inorder predchodcu a presunúť ho priamo na miesto uzla, ktorý sa má odstrániť, bez ďalších úprav stromu.

A. Áno

B. Nie

Vysvetlenie: Mazanie uzla s dvoma potomkami je najzložitejší prípad. Riešením je nájsť náhradný uzol (napríklad inorder predchodcu) a skopírovať ho do odstraňovaného uzla. Následne sa tento náhradný uzol musí odstrániť z jeho pôvodného miesta, čo spadá pod Prípad 1 (list) alebo Prípad 2 (jeden potomok), takže nejde o jednoduché priame presunutie bez ďalších úprav.

Otázka 2: V prípade vyhľadávania prvku v binárnom vyhľadávacom strome je časová zložitosť operácie vždy O(log n).

A. Áno

B. Nie

Vysvetlenie: Časová zložitosť vyhľadávania v binárnom vyhľadávacom strome je v priemernom prípade O(log n). Avšak, v najhoršom prípade, keď je strom degenerovaný do lineárneho zoznamu, je zložitosť O(n), nie O(log n).

Otázka 3: Aké sú dôsledky degenerácie binárneho vyhľadávacieho stromu (BST) na lineárny zoznam?

A. Výška stromu sa stáva h ≈ log₂ n.

B. Časová zložitosť základných operácií (vyhľadávanie, vkladanie, mazanie) sa zhoršuje na O(n).

C. Výška stromu sa stáva h = n.

D. Operácie v strome sa stávajú rovnako efektívne ako v dokonale vyváženom binárnom strome.

Vysvetlenie: Degenerácia BST na lineárny zoznam znamená, že výška stromu h sa rovná počtu uzlov n. V dôsledku toho sa časová zložitosť základných operácií, ako sú vyhľadávanie, vkladanie a mazanie, zhoršuje z O(log n) na O(n). To je v protiklade s dokonale vyváženým stromom, kde je výška h ≈ log₂ n a operácie sú rýchle s O(log n) zložitosťou.

Otázka 4: Ktoré tvrdenie správne popisuje poradie navštívených uzlov pri Preorder prechode stromom?

A. Navštívi ľavý podstrom, potom koreň a nakoniec pravý podstrom.

B. Navštívi koreň, potom ľavý podstrom a nakoniec pravý podstrom.

C. Navštívi ľavý podstrom, potom pravý podstrom a nakoniec koreň.

D. Navštívi pravý podstrom, potom koreň a nakoniec ľavý podstrom.

Vysvetlenie: Preorder prechod (Preorder Traversal) navštívi koreň, potom ľavý podstrom a nakoniec pravý podstrom. Toto poradie je 'Koreň → Ľavý podstrom → Pravý podstrom'.

Otázka 5: Interaktívna simulácia binárneho vyhľadávacieho stromu umožňuje aktívne vykonávať operácie vyhľadávania konkrétnych hodnôt.

A. Áno

B. Nie

Vysvetlenie: Študijné materiály uvádzajú, že simulácia umožňuje aktívne vykonávať operácie vkladania a mazania uzlov. Vyhľadávanie nie je spomenuté ako aktívna operácia, ktorú môže používateľ vykonať v simulácii.