Struktury danych

Question 1

Czym jest graf ?

Answer 1

Graf jest to podstawowy obiekt rozważań teorii grafów, struktura matematyczna służąca do badania i przedstawiania relacji pomiędzy obiektami. W uproszczeniu graf jest to zbiór wierzchołków które mogą być połączone w taki sposób, że każda krawędź zaczyna sie i kończy na którymś w wierzchołków.

Question 2

Czym jest drzewo binarne ? (Binary tree)

Answer 2

Drzewo binarne jest drzewiastą strukturą danych w której każdy węzeł ma maksymalnie dwoje dzieci (childrens) - lewe dziecko (left child) oraz prawe dziecko (prawe dziecko).

Question 3

Czym jest hashtable (Tablica mieszająca) ?

Answer 3

Hashtable jest to struktura danych która jest implementacją tablicy asocjacyjnej, korzystająca z funkcji haszujących do wyznaczania indeksu dla kluczy.

Question 4

Podaj 2 zalety hashmapy

Answer 4

1. Wyszukiwanie średnio (averange) zajmuje O(1)

2. Jako klucze może posłużyć wiele typów danych (muszą być haszowalne)

Question 5

Podaj 4 wady hashmapy

Answer 5

1. Wyszukiwanie w najgorszym przypadku (worst case scenario) zajmuje O(n)
2. Jest nieposortowana, w przypadku wyszukiwania najmniejszego bądź największego klucza musimy przejść po wszystkich kluczach
3. Jedno-kierunkowe wyszukiwanie, podczas gdy wyszukiwanie wartości po kluczu jest szybkie to wyszukiwanie w drugą stronę zajmie O(n)
4. Nie są przyjazne cachowaniu - większość implementacji hashmapy używa struktury zwanej LinkedList, której cachowanie jest trudne w implementacji

Question 6

Czym jest hash collision ?

Answer 6

Hash collision to sytuacja w której dwa różne klucze po haszowaniu wskazują na ten sam indeks.

Question 7

Jakie są strategie obsługi hash collisons ?

Answer 7

1. Separate chaining

2. Open adressing

Question 8

Czym jest dynamiczna tablica (dynamic array) ?

Answer 8

Dynamic array to tablica która umożliwia operacje dodawania bądź usuwania elementów

Question 9

Czym jest kolejka ? Jaki jest to rodzaj buforu ?

Answer 9

Kolejka to liniowa struktura danych w której nowe elementy są dopisywane na koniec kolejki a te z początku są przekazywane do dalszego przetwarzania.

Jest to bufor FIFO

Question 10

Czym jest stos ? Jakie jest to typ bufora ?

Answer 10

Stos jest liniową strukturą danych w której dane dokładane są na wierz stosu i z wierzchołka stosu są pobierane do dalszego przetwarzania.

Jest to bufor typu LIFO.

Question 11

Czym jest Linked list ?

Answer 11

Linked list to liniowa struktura danych w której kolejność danych nie jest określona poprzez ich fizyczne ułożenie w pamięci, a poprzez fakt że każdy element wskazuje na kolejny.