Struktury danych: karta pracy z odpowiedziami

Czym jest stopień wierzchołka w grafie nieskierowanym?

1. ALiczbą krawędzi z nim połączonych
2. BDługością najdłuższej ścieżki z niego wychodzącej
3. CJego pozycją na liście sąsiedztwa
4. DLiczbą wierzchołków w grafie

Czym jest kolizja w tablicy mieszającej?

1. AWyczerpaniem pamięci przez tablicę
2. BOdwzorowaniem dwóch różnych kluczy na ten sam indeks
3. CSytuacją, w której klucza w ogóle nie da się zahaszować
4. DDwukrotnym zapisaniem dwóch równych kluczy

Czym jest liść w drzewie?

1. AWęzłem bez rodzica
2. BWęzłem bez dzieci
3. CWęzłem o największej wartości
4. DWęzłem z dokładnie jednym dzieckiem

Ile trwa wyszukiwanie słowa o długości L w drzewie trie ze stałym alfabetem?

1. AO(L × n)
2. BO(n), gdzie n to liczba słów
3. CO(log n), gdzie n to liczba słów
4. DO(L), niezależnie od liczby przechowywanych słów

Dlaczego kopiec binarny można przechowywać w tablicy bez żadnych wskaźników?

1. AWszystkie klucze w kopcu są równe
2. BKopce nigdy nie zawierają więcej niż 100 elementów
3. CTablice automatycznie utrzymują klucze w kolejności posortowanej, więc wskaźniki nie są potrzebne
4. DJest zupełnym drzewem binarnym, więc pozycje wynikają z prostych wzorów na indeksy

Gdzie w kopcu binarnym przechowywanym w tablicy od indeksu 0 znajduje się rodzic węzła o indeksie i?

1. APod indeksem ⌊(i − 1) / 2⌋
2. BPod indeksem ⌊i / 2⌋ + 1
3. CPod indeksem i − 1
4. DPod indeksem 2i + 1

Która struktura danych umożliwia pamięć podręczną LRU (least recently used) z operacjami get i put w O(1)?

1. APojedyncza posortowana tablica
2. BMapa mieszająca połączona z listą dwukierunkową
3. CWyłącznie stos
4. DWyłącznie binarne drzewo poszukiwań

W BST z korzeniem 50, lewym poddrzewem 30 (dzieci 20, 40) i prawym poddrzewem 70 (dzieci 60, 80) usuwa się korzeń przy użyciu następnika w porządku inorder. Który klucz zostaje nowym korzeniem?

1. A80
2. B70
3. C60
4. D40