Test na Binární vyhledávací strom

Otázka 1: V binárním vyhledávacím stromu jsou všechny hodnoty v levém podstromu libovolného uzlu menší než hodnota samotného uzlu.

A. Ano

B. Ne

Vysvětlení: Klíčová vlastnost binárního vyhledávacího stromu spočívá v uspořádání hodnot uzlů. Pro každý uzel 'U' ve stromu platí, že všechny hodnoty v levém podstromu uzlu 'U' jsou menší než hodnota uzlu 'U' samotného.

Otázka 2: Nezachování vlastnosti BST během operací vkládání nebo mazání neovlivňuje funkčnost vyhledávání, protože je to pouze kosmetická chyba.

A. Ano

B. Ne

Vysvětlení: Materiály uvádějí, že nesprávné vkládání nebo mazání, které poruší pravidlo BST, vede k nefunkčnímu vyhledávání. Není to tedy pouze kosmetická chyba, ale zásadní narušení funkčnosti.

Otázka 3: Které z následujících tvrzení správně popisuje klíčovou vlastnost binárního vyhledávacího stromu (BST)?

A. Všechny hodnoty v pravém podstromu libovolného uzlu 'U' jsou větší než hodnota uzlu 'U' samotného.

B. Každý uzel v BST musí mít přesně dva potomky, levého a pravého.

C. Hodnoty v levém podstromu uzlu 'U' mohou být menší nebo rovny hodnotě uzlu 'U' samotného.

D. Pouze kořen stromu může mít potomky, ostatní uzly jsou listy.

Vysvětlení: Podle studijních materiálů, pro každý uzel 'U' v BST platí, že všechny hodnoty v pravém podstromu uzlu 'U' jsou větší než hodnota uzlu 'U' samotného. Možnost 1 je tedy správná. Ostatní možnosti jsou nesprávné: BST umožňuje uzlům mít jednoho nebo žádného potomka, hodnoty v levém podstromu musí být striktně menší, a potomky mohou mít i jiné uzly než jen kořen.

Otázka 4: Při mazání uzlu z binárního vyhledávacího stromu, který má dva potomky, jaký je správný postup podle studijních materiálů?

A. Nahradíme uzel jeho levým potomkem a poté smažeme levého potomka.

B. Najdeme inorder následníka mazaného uzlu v jeho pravém podstromu, zkopírujeme jeho hodnotu do mazaného uzlu a poté smažeme inorder následníka z jeho původního místa.

C. Nahradíme uzel jeho pravým potomkem a poté smažeme pravého potomka.

D. Jednoduše odstraníme uzel a odkaz jeho rodiče nastavíme na null, protože BST se automaticky přeuspořádá.

Vysvětlení: Studijní materiály uvádí, že při mazání uzlu se dvěma potomky se nejprve najde inorder následník v pravém podstromu, jeho hodnota se zkopíruje do uzlu k mazání a poté se inorder následník smaže z jeho původního místa. Inorder následník bude mít vždy maximálně jednoho potomka, což zjednodušuje jeho odstranění.

Otázka 5: Inorder průchod binárním vyhledávacím stromem vypíše hodnoty uzlů ve vzestupném seřazeném pořadí.

A. Ano

B. Ne

Vysvětlení: Inorder průchod navštíví levý podstrom, poté aktuální uzel a nakonec pravý podstrom. Pro binární vyhledávací strom tato sekvence zajišťuje, že jsou hodnoty uzlů vypsány ve vzestupném seřazeném pořadí.