Dynamiczne struktury danych

1. O jakich strukturach mówimy, że są dynamiczne:
a) kolejka, drzewo, stos
b) drzewo, tablica, kolejka
c) lista liniowa, klasa, drzewo
d) drzewo, tablica wielowymiarowa, lista liniowa

2. Która z wymienionych cech Dynamicznych Struktur Danych jest prawdziwa
a) Kolejne elementy przechowywane są ZAWSZE w bezpośrednio następujących po sobie komórkach pamięci
b) Przed rozpoczęciem działania na strukturze musimy znać jej rozmiar
c) Ilość elementów może być dowolna (w ramach dostępnej pamięci)
d) Możemy przechowywać w niej tylko małe elementy

3. Co nazywamy Abstrakcyjnym Typem Danych (ADT):
a) Wszystkie dane przechowywane w komputerze
b) Formalną specyfikację sposobu przechowywania obiektów i operacji na tych obiektach
c) Wskaźnik na element kolejki/stosu/drzewa
d) Tablicę wielowymiarową

4. Co charakteryzuje 'stos':
a) Elementy stosu są układane w kolejności malejącej
b) Elementy są zdejmowane w odwrotnej kolejności niż zostały na niego położone
c) Stos rządzi się zasadą FIFO (First-In-First-Out)
d) Elementy stosu zdejmowane są z jego końca

5. Cechy charakterystyczne 'kolejki'
a) Jedynym wyróżnionym elementem kolejki jest jej koniec
b) Nowe elementy dodawane są na początek kolejki
c) Kolejka rządzi się zasadą LIFO (Last-In-First-Out)
d) Elementy zdejmowane są z początku kolejki

6. Tablicowa implementacja stosu/kolejki
a) Jest najbardziej efektywna
b) wykorzystuje tablicę o 'n' elementach gdzie 'n' jest maksymalną ilością elementów stosu/kolejki
c) jest jedyną możliwą implementacją stosu/kolejki
d) umożliwia przechowywanie dowolnej ilości elementów

7. Jaka jest różnica między stosem a kolejką
a) Elementy kolejki zdejmowane są z jej początku natomiast elementy stosu zdejmowane są z jego końca
b) Kolejka ma ograniczoną ilość elementów jakie może przechowywać natomiast stos nie
c) Elementy kolejki zdejmowane są w tej samej kolejności w jakiej zostały położone natomiast elementy stosu w odwrotnej
d) Elementy kolejki zdejmowane są w odwrotnej kolejności w jakiej zostały położone natomiast stos zachowuje kolejność elementów przy zdejmowaniu

8. Cechy charakterystyczne listy
a) Posiada wyróżniony początek i koniec
b) Rozmieszczenie fizyczne elementów listy ZAWSZE odpowiada jej logicznej kolejności
c) Po odczytaniu wszystkich elementów listy są one tracone
d) Możemy wykonywać działania tylko na pierwszym i ostatnim elemencie listy

9. Które z poniższych zdań jest niepoprawne
a) W przypadku dynamicznych struktur danych fizyczne rozmieszczenie elementów nie ma znaczenia
b) W 'stosie' elementy są dodawane i zdejmowane z początku
c) Dynamicznych strukturach danych nie mają ograniczenia co do ilości elementów (jedynym ograniczeniem jest ilość dostępnej pamięci)
d) Elementy listy mogą wskazywać tylko na element następny.
10. Węzeł jest to:
a) Element przechowujący jedynie wskaźnik na następny element
b) Pojedyncza komórka tablicy
c) Element przechowujący dane oraz wskaźnik na następny element struktury
d) Wskaźnik na dowolny element struktury

11. Drzewo charakteryzuje się
a) Istnieje kilka dróg dotarcia od korzenia do pojedynczego węzła
b) Liście posiadają dowolną ilość potomków
c) Może posiadać więcej niż jeden korzeń
d) Każdy węzeł z wyjątkiem korzenia posiada przodka

12. Drzewem binarnym nazywamy
a) Drzewo którego węzły przyjmują jedynie wartości '0' i '1'
b) Drzewo z korzeniem, dla którego każdy węzeł ma co najwyżej 2 potomków
c) Drzewo z korzeniem, dla którego każdy węzeł ma co dokładnie 2 potomków
d) Drzewo w którym każdy liść ma taką samą głębokość

13. Które ze zdań jest prawdziwe
a) Porządek węzłów w drzewie binarnym jest istotny
b) Wysokość drzewa jest sumą długości wszystkich jego ścieżek
c) Drzewo nazywamy 'kompletnym' jeżeli każdy węzeł wewnętrzny ma dokładnie dwóch potomków.
d) Drzewo nazywamy 'pełnym' jeśli każdy liść ma tę samą głębokość.

14. Co to są 'listy cykliczne'
a) Listy w których pojedynczy węzeł posiada wskaźnik na poprzedni i następny element
b) Listy posiadające wskaźnik jedynie na następny element
c) Listy w których wskaźnik z ostatniego węzła pokazuje na węzeł pierwszy
d) Listy w których elementy znajdują się fizycznie w następujących po sobie komórkach pamięci

15. Co charakteryzuje 'listy podwójnie łączone'
a) Lista jest 'cykliczna'
b) Pojedynczy węzeł posiada 3 wskaźniki, jeden na element poprzedni a dwa na elementy następne
c) Są to dwie listy połączone ze sobą tak, że koniec jednej wskazuje na początek drugiej
d) Pojedyncze węzły mają wskaźniki na węzeł poprzedni oraz następny

16. Ilość węzłów na poziomie d w kompletnym drzewie binarnym wynosi:
a)
b)
c)
d)

17. Ilość wszystkich węzłów w kompletnym drzewie binarnym o 'x' poziomach wynosi:
a)
b)
c)
d)

18. Pojedynczy węzeł drzewa binarnego MUSI zawierać
a)dane, wskaźnik na 'rodzica', jeden wskaźnik na 'potomka'
b) dane, dwa wskaźniki na 'potomków' (lewy, prawy)
c) wskaźnik na 'rodzica', dwa wskaźniki na 'potomków' (lewy, prawy)
d) dane, dwa wskaźniki na 'potomków' (lewy, prawy), wskaźnik na korzeń drzewa

19. Abstrakcyjny typ danych :
a)jest zbiorem funkcji i opisem jej argumentów
b)jest rodzajem struktury danych (klasą)
c)jest uzależniony od komputera i systemu operacyjnego
d)jest strukturą statyczną

20. Zgodnie z metodą FIFO (First In- first out) zbudowano
a)kolejkę
b)b- drzewo
c)stos
d)listę

21. Drzewo binarne jest pełne, gdy
a)każdy węzeł ma dokładnie dwóch potomków
b)każdy węzeł wewnętrzny ma dokładnie dwóch potomków
c)każdy węzeł wewnętrzny ma maksymalnie dwóch potomków
d) każdy liść ma dokładnie taką samą głębokość

22. Zaletą korzystania ze struktur dynamicznych w porównaniu ze stosowaniem tablic jest
a)przydzielanie spójnego zasobu pamięci
b)przydzielanie zawsze mniejszego zasobu pamięci
c)zwiększenie wydajności poprzez szybszy dostęp do elementu
d) przechowywanie elementów niezależnie od ich fizycznego położenia

23. wskaż, która z własności listy jest nieprawdziwa
a)Każdy element(z wyjątkiem wskaźnika początku- head argumentów końca- tail) posiada element poprzedni i następny.
b)Lista jest struktura liniową.
c)Listę, która jest dwukrotnie łączona nazywamy cykliczną.
d)Lista jest pusta wtedy i tylko wtedy, gdy head i tail są sobie równe.

24.Aby utworzyć i obsłużyć stos potrzebujemy:
a)Dokonywać działań na wskaźnikach
b)Znać liczbę elementów
c)Ustawić koniec stosu na null
d) Stworzyć procedury Push i Pop

25. Do dynamicznych ATD nie zaliczamy:
a)stosy i kolejki,
b)drzewa czerwono czarne
c)kopców(kolejek priorytetowych)
d) tablicy dwuwymiarowej

26.Aby uzyskać odwróconą kolejność wstawianych elementów należy
a)Elementy ze stosu wstawić na stos
b)Elementy z kolejki wstawić do kolejki
c)Elementy stosu wstawić do kolejki
d)Elementy z kolejki cyklicznej wstawić do kolejki cyklicznej

27. Błąd przepełnienia stosu w implementacji tablicowej (�śoverflow”) powinien wystąpić, gdy:
a)długość stosu przekroczy wymiar tablicy,
b)dokonano operacji zdjęcia elementu priorytetowych pustej kolejki
c)dokonano operacji dodania elementu do tabeli, której wymiar jest równy długości stosu
d) zawsze przed stworzeniem nowej dostatecznie dużej tabeli

28. Nie można wstawiać nowego elementu do listy poprzez
a)wpięcie go na koniec listy,
b)wpięcie go na początek listy
c)wpięcie go pomiędzy dwa inne elementy listy
d)wpięcie go jedynie do uchwytu head

29. Zgodnie z metodą LIFO (Last In- first out) zbudowano
a) kolejkę
b) stos
c) drzewo
d) listę

30. Co to jest drzewo 'trynarne'
a) Drzewo w którym elementy posiadają dane oraz maksymalnie 3 wskaźniki na potomków
b) Drzewo o którym elementy posiadają dane, wskaźnik na przodka oraz dwa wskaźniki na potomków
c) Drzewo w którym elementy posiadają wskaźnik na przodka oraz maksymalnie trzy wskaźniki na potomków
d) Drzewo w którym elementy posiadają dowolną ilość wskaźników na potomki