Studia informatyka – Drzewa i grafy

Co to jest drzewo w informatyce?

Drzewo to struktura danych składająca się z węzłów, gdzie każdy węzeł ma rodzica (oprócz korzenia) oraz zero lub więcej dzieci.

Czym jest węzeł liściasty?

Węzeł liściasty to węzeł, który nie ma dzieci, co oznacza, że jest to końcowy punkt w strukturze drzewa.

Jakie są główne typy drzew?

Główne typy drzew to: drzewo binarne, drzewo AVL, drzewo czerwono-czarne oraz drzewo B.

Różnica między drzewem binarnym a drzewem binarnym wyszukiwania

Drzewo binarne nie ma ograniczeń co do wartości węzłów, natomiast drzewo binarne wyszukiwania wymaga, aby wartości lewej poddrzewa były mniejsze, a prawe większe od wartości węzła.

Ile dzieci może mieć węzeł w drzewie binarnym?

Węzeł w drzewie binarnym może mieć maksymalnie 2 dzieci.

Jak wygląda struktura drzewa?

Struktura drzewa składa się z węzła korzeniowego, który rozgałęzia się na poddrzewa, tworząc hierarchiczną organizację.

Prawda czy fałsz: Wszystkie drzewa są grafami.

Prawda, ponieważ drzewo jest szczególnym przypadkiem grafu, gdzie nie ma cykli.

Czym różni się drzewo B od drzewa binarnego?

Drzewo B jest drzewem wielowymiarowym, które może mieć więcej niż 2 dzieci oraz jest zbalansowane, co ułatwia operacje na dużych zbiorach danych.

Jakie są zastosowania drzew?

Drzewa są używane w strukturach danych, systemach plików, bazach danych (np. jako indeksy) oraz w algorytmach kompresji.

Uzupełnij zdanie: Węzeł korzeniowy ma ___ rodziców.

0 rodziców.

Czym jest głębokość węzła?

Głębokość węzła to długość najkrótszej ścieżki od korzenia do tego węzła.

Co to jest przechodzenie drzewa?

Przechodzenie drzewa to proces odwiedzania węzłów w określonej kolejności, np. pre-order, in-order, post-order.

Ile węzłów ma pełne drzewo binarne wysokości h?

W pełnym drzewie binarnym wysokości h jest $\displaystyle 2^{h+1} - 1$ węzłów.

Prawda czy fałsz: Drzewa są zawsze zbalansowane.

Fałsz, ponieważ niektóre drzewa, jak drzewo binarne, mogą być niezbalansowane.

Czym jest drzewo AVL?

Drzewo AVL to samobalansujące się drzewo binarne wyszukiwania, które utrzymuje różnicę wysokości między lewym a prawym poddrzewem nie większą niż 1.

Czym jest graf?

Graf to zbiór węzłów (wierzchołków) połączonych krawędziami, które mogą być skierowane lub nieskierowane.

Jakie są podstawowe rodzaje grafów?

Podstawowe rodzaje grafów to: grafy nieskierowane, skierowane, ważone oraz nieważone.

Prawda czy fałsz: Każdy graf ma cykle.

Fałsz, ponieważ grafy mogą być acykliczne, co oznacza, że nie mają cykli.

Czym jest graf pełny?

Graf pełny to graf, w którym każda para wierzchołków jest połączona krawędzią.

Jakie są zastosowania grafów?

Grafy są używane w sieciach komputerowych, analizie społecznej, planowaniu tras oraz w problemach optymalizacji.

Różnica między grafem skierowanym a nieskierowanym

W grafie skierowanym krawędzie mają kierunek, co oznacza, że przejście z jednego wierzchołka do drugiego jest jednostronne.

Co to jest stopień wierzchołka?

Stopień wierzchołka to liczba krawędzi, które są z nim połączone. W grafach skierowanych rozróżniamy stopień przychodzący i wychodzący.

Ile krawędzi ma graf pełny z n wierzchołkami?

Graf pełny z n wierzchołkami ma $\displaystyle \frac{n(n-1)}{2}$ krawędzi.

Uzupełnij zdanie: Wykres grafu przedstawia ___.

Relacje między wierzchołkami w postaci węzłów i krawędzi.

Czym jest algorytm Dijkstry?

Algorytm Dijkstry służy do znajdowania najkrótszej ścieżki w grafie ważonym o nieujemnych wagach krawędzi.

Czym jest cykl w grafie?

Cykl to ścieżka w grafie, która zaczyna i kończy się w tym samym wierzchołku, nie przechodząc przez inne wierzchołki więcej niż raz.

Prawda czy fałsz: Graf nieskierowany nie może mieć krawędzi wielokrotnych.

Fałsz, graf nieskierowany może mieć krawędzie wielokrotne między tymi samymi wierzchołkami.

Jak nazywa się metoda przeszukiwania grafu?

Metody przeszukiwania grafu to DFS (Depth First Search) i BFS (Breadth First Search).

Czym jest graf acykliczny?

Graf acykliczny to graf, w którym nie występują żadne cykle.

Różnica między BFS a DFS

BFS (Breadth First Search) eksploruje wierzchołki warstwami, natomiast DFS (Depth First Search) zagłębia się w grafie, odwiedzając wierzchołki w miarę ich odkrywania.