Test z Binarne drzewo poszukiwań

Pytanie 1: Wyważanie drzewa to proces modyfikacji jego struktury, mający na celu zminimalizowanie jego wysokości, zbliżając ją do wartości `log₂ n`.

A. Tak

B. Nie

Wyjaśnienie: Wyważanie drzewa polega na modyfikacji struktury drzewa w taki sposób, aby jego wysokość była jak najmniejsza, zbliżona do `log₂ n`. Dzięki temu operacje na drzewie mają logarytmiczną złożoność czasową, co zapewnia wysoką wydajność.

Pytanie 2: Implementacja usuwania węzła z dwoma dziećmi w binarnym drzewie poszukiwań jest prosta i rzadko stanowi źródło błędów.

A. Tak

B. Nie

Wyjaśnienie: Zgodnie z materiałami, przypadek usuwania węzła z dwoma dziećmi jest często źródłem błędów, co wskazuje na to, że nie jest prosty w implementacji.

Pytanie 3: Jaka jest złożoność czasowa podstawowych operacji (wyszukiwania, wstawiania, usuwania) w binarnym drzewie poszukiwań (BST) w najlepszym i najgorszym przypadku?

A. W najlepszym przypadku O(log n), a w najgorszym przypadku O(n).

B. Zawsze O(log n), ponieważ drzewo jest automatycznie wyważone.

C. Zawsze O(n), niezależnie od struktury drzewa.

D. W najlepszym przypadku O(n), a w najgorszym przypadku O(log n).

Wyjaśnienie: Złożoność czasowa operacji wyszukiwania, wstawiania i usuwania w BST wynosi O(h), gdzie h to wysokość drzewa. W najlepszym przypadku, gdy drzewo jest idealnie wyważone (h ≈ log₂ n), złożoność wynosi O(log n). W najgorszym przypadku, gdy drzewo zdegeneruje się do struktury przypominającej listę liniową (h = n), złożoność wynosi O(n).

Pytanie 4: Które z poniższych stwierdzeń opisuje częsty błąd popełniany przez studentów, dotyczący błędnego rozumienia właściwości binarnych drzew poszukiwań (BST)?

A. Mylenie kolejności kluczy w lewym i prawym poddrzewie, co prowadzi do nieprawidłowego działania drzewa.

B. Zakładanie, że BST automatycznie utrzymuje optymalną wysokość.

C. Trudności z implementacją usuwania węzła z dwoma dziećmi.

D. Mylenie różnic między przechodzeniem drzewa typu in-order, pre-order i post-order.

Wyjaśnienie: Częstym błędem związanym z błędnym rozumieniem właściwości BST jest mylenie kolejności kluczy w lewym i prawym poddrzewie, co może skutkować nieprawidłowym działaniem drzewa. Pozostałe opcje, choć również są wymienione jako częste błędy, nie dotyczą bezpośrednio 'błędnego rozumienia właściwości BST', lecz innych aspektów, takich jak jego wyważanie, implementacja operacji czy typy przechodzenia.

Pytanie 5: Aby usunąć węzeł, który jest liściem w binarnym drzewie poszukiwań (BST), wystarczy usunąć ten węzeł i ustawić referencję od jego rodzica na null.

A. Tak

B. Nie

Wyjaśnienie: Usuwanie węzła liścia jest najprostszym przypadkiem. Procedura polega na usunięciu węzła i ustawieniu referencji od jego rodzica na wartość null, co skutecznie odłącza liść od drzewa.