Temat 1

Question 1

Czym jest ADT? Podaj przykłady.

Answer 1

Abstrakcyjny Typ Danych to opis typu danych uwzględniający już własności wartości i operacje.

Przykłady:
- lista wiązana
- zbiór
- kolejka FIFO/ LIFO/ Priorytetowa
- mapa
- drzewo
- graf

Question 2

Czym różni się ADT od SD?

Answer 2

Różnice między ADT a SD:
- ADT skupia się na wykorzystaniu operacji i wartości, a nie na implementacji, czy reprezentacji

Question 3

Elementarne operacje na ADT i SD

Answer 3

• sprawdzenie, czy kolekcja jest pusta
• zwrócenie liczby elementów w kolekcji
• wyszukanie elementu po pozycji (index), po klucz (key), wartości (value)
• dodanie elementu (append, insert, push)
• usuniecie elementu (remove, pop)
• przejrzenie kolekcji (peek, display)

Question 3

Czym jest SD? Podaj przykłady.

Answer 3

Jest to struktura danych, która służy do zarządzania nimi. Określa ich sposób implementacji i reprezentacji.

Przykłady:
- tablica dynamiczna
- lista wiązana
- tablica mieszająca
- BST, AVL, BLACK-RED tree
- macierz sąsiedztwa, lista sąsiedztwa, lista krawędzi

Question 4

Czym jest typ strukturalny, a czym jest typ obiektowy?

Answer 4

Typ strukturalny jest strukturą, która przechowuje elementy różnego typu. Jest ona dostępna po nazwie.

Typ obiektowy jest to odniesienie do typu strukturalnego. Rozszerza ten typ o definicje zaimplementowanych operacji.

Question 5

Złożoność obliczeniowa rodzaje i analiza dla rozkładu danych wejściowych

Answer 5

• czasowa
• pamięciowa
• komunikacyjna
• równoległa

analiza dla rozkładu danych wejściowych:
- worst-case - górna granica złożoności
- average-case - wartość oczekiwana
- best-case - dolna granica złożoności

Question 6

Czym jest koszt zamortyzowany? Czym jest asymptotyczne tempo wzrostu?

Answer 6

1. Uśredniona złożoność obliczeniowa
2. Jest to miara do opisu złożoności obliczeniowej przy n dążącym do nieskończoności