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 są węzły rodzeństwa (siblings) w drzewie?

  1. AWęzłami na tej samej głębokości w różnych poddrzewach
  2. BWęzłami, które mają tego samego rodzica
  3. CWęzłem i jego rodzicem
  4. DWęzłami, które nie mają dzieci
2.Łatwy

Co robi funkcja mieszająca w tablicy mieszającej?

  1. ASzyfruje wartości w tablicy
  2. BSortuje klucze w tablicy
  3. COdwzorowuje klucz na indeks w tablicy
  4. DLiczy, ile kluczy jest przechowywanych
3.Łatwy

Która struktura danych działa według zasady „ostatni na wejściu, pierwszy na wyjściu” (LIFO)?

  1. ATablica mieszająca
  2. BLista wiązana
  3. CStos
  4. DKolejka
4.Średni

Drzewo binarne ma korzeń 1 z lewym dzieckiem 2 i prawym dzieckiem 3; węzeł 2 ma dzieci 4 (lewe) i 5 (prawe). Jaki jest wynik przejścia preorder?

  1. A1 2 4 5 3
  2. B4 5 2 3 1
  3. C1 2 3 4 5
  4. D4 2 5 1 3
5.Średni

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

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

Jaki jest koszt wstawienia elementu w środek tablicy o n elementach?

  1. AO(n), bo dalsze elementy trzeba przesunąć
  2. BO(n²), bo każdy element przesuwa się n razy
  3. CO(1), bo indeks jest znany
  4. DO(log n), z powodu wyszukiwania binarnego
7.Trudny

Dlaczego B-drzewa są używane w bazach danych i systemach plików?

  1. ANie wymagają równoważenia
  2. BDuży stopień rozgałęzienia utrzymuje drzewo płytkim, ograniczając wolne odczyty z dysku
  3. CPrzechowują dane nieposortowane
  4. DZajmują mniej pamięci niż jakakolwiek tablica, więc cały indeks zawsze mieści się w pamięci głównej
8.Trudny

Czym drzewo radix (skompresowane trie) przewyższa zwykłe trie?

  1. AZachowuje tylko pierwszą literę każdego słowa
  2. BPrzechowuje każde słowo w tablicy mieszającej w korzeniu zamiast w osobnych węzłach
  3. CSortuje dzieci każdego węzła według częstości
  4. DŁączy łańcuchy węzłów z jednym dzieckiem w jedną krawędź etykietowaną ciągiem znaków

Klucz odpowiedzi

  1. 1. B · Węzłami, które mają tego samego rodzica
  2. 2. C · Odwzorowuje klucz na indeks w tablicy
  3. 3. C · Stos
  4. 4. A · 1 2 4 5 3
  5. 5. C · Pod indeksem ⌊(i − 1) / 2⌋
  6. 6. A · O(n), bo dalsze elementy trzeba przesunąć
  7. 7. B · Duży stopień rozgałęzienia utrzymuje drzewo płytkim, ograniczając wolne odczyty z dysku
  8. 8. D · Łączy łańcuchy węzłów z jednym dzieckiem w jedną krawędź etykietowaną ciągiem znaków

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