Struktury danych: karta pracy z odpowiedziami

Darmowa karta pracy do druku – Struktury danych: 8 zadań od łatwych do poziomu egzaminu, z kluczem odpowiedzi. Wydrukuj ją lub zapisz jako PDF.

Nowa karta pracyĆwicz online z podpowiedziami

Dla nauczycieli: można bezpłatnie drukować, kopiować i używać na zajęciach. Każdy nowy arkusz ma nowe wartości i własny klucz odpowiedzi. Będziemy wdzięczni za link do ExamProblems na stronie kursu.

Imię: ____________________   Data: ____________

1.Łatwy

Czym jest kolizja w tablicy mieszającej?

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

Która operacja jest wolna w tablicy, ale szybka na początku listy wiązanej?

  1. AWstawianie na początku
  2. BOdczyt ostatniego elementu po indeksie
  3. CDostęp do 5. elementu
  4. DUstalenie długości tablicy o stałym rozmiarze
3.Łatwy

Głębokość węzła w drzewie to:

  1. ALiczba krawędzi od tego węzła do najgłębszego liścia
  2. BLiczba krawędzi od korzenia do tego węzła
  3. CLiczba dzieci tego węzła
  4. DLiczba węzłów w jego poddrzewie
4.Średni

Ile pamięci zajmuje macierz sąsiedztwa grafu o V wierzchołkach?

  1. AO(V + E)
  2. BO(V²)
  3. CO(E)
  4. DO(log V)
5.Średni

Drzewa AVL i drzewa czerwono-czarne gwarantują:

  1. AWysokość O(log n) dzięki równoważeniu
  2. BŻe żaden węzeł nie ma dwojga dzieci
  3. CPrzechowywanie kluczy w kolejności wstawiania
  4. DWyszukiwanie w czasie stałym w każdym przypadku
6.Średni

Drzewo trie (drzewo prefiksowe) jest szczególnie wydajne przy:

  1. APrzechowywaniu macierzy
  2. BSortowaniu liczb
  3. CZnajdowaniu najkrótszych ścieżek
  4. DWyszukiwaniu po prefiksie, np. autouzupełnianiu
7.Trudny

Jaki jest pesymistyczny koszt pojedynczej operacji find w strukturze union-find z n elementami bez łączenia według rangi (union by rank) i bez kompresji ścieżek?

  1. AO(α(n))
  2. BO(n)
  3. CO(1)
  4. DO(log n)
8.Trudny

Które stwierdzenie o sortowaniu przez kopcowanie (heapsort) jest poprawne?

  1. ADziała w czasie O(n) dla każdych danych wejściowych
  2. BSortuje w miejscu w pesymistycznym czasie O(n log n), ale nie jest stabilne
  3. CWymaga binarnego drzewa poszukiwań jako dodatkowej pamięci, więc zużywa O(n) pamięci dodatkowej
  4. DJest stabilne i wymaga O(n) dodatkowej pamięci

Klucz odpowiedzi

  1. 1. A · Odwzorowaniem dwóch różnych kluczy na ten sam indeks
  2. 2. A · Wstawianie na początku
  3. 3. B · Liczba krawędzi od korzenia do tego węzła
  4. 4. B · O(V²)
  5. 5. A · Wysokość O(log n) dzięki równoważeniu
  6. 6. D · Wyszukiwaniu po prefiksie, np. autouzupełnianiu
  7. 7. B · O(n)
  8. 8. B · Sortuje w miejscu w pesymistycznym czasie O(n log n), ale nie jest stabilne

Pełne rozwiązania krok po kroku: ćwicz ten temat na examproblems.com.