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

Która struktura jest zwykle używana do implementacji kolejki priorytetowej?

  1. ANieuporządkowana lista jednokierunkowa
  2. BStos
  3. CKopiec
  4. DCiąg znaków
2.Łatwy

Czym są węzły rodzeństwa (siblings) w drzewie?

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

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

  1. ALista wiązana
  2. BStos
  3. CKolejka
  4. DTablica mieszająca
4.Średni

Klucze 50, 30, 70, 20, 40 wstawia się w tej kolejności do pustego binarnego drzewa poszukiwań. Co jest lewym dzieckiem 30?

  1. A20
  2. B40
  3. C70
  4. D50
5.Średni

Drzewa AVL i drzewa czerwono-czarne gwarantują:

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

Przejście in-order (poprzeczne) binarnego drzewa poszukiwań odwiedza klucze w kolejności:

  1. ARosnącej (posortowanej)
  2. BZawsze malejącej
  3. CPoziomami
  4. DWstawiania
7.Trudny

Drzewo przedziałowe (segment tree) służy zwykle do:

  1. APrzechowywania krawędzi grafu
  2. BAlfabetycznego sortowania napisów przez przechowywanie każdego prefiksu w osobnym węźle drzewa
  3. CImplementacji stosu
  4. DOdpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)
8.Trudny

Struktura union-find (zbiory rozłączne) z łączeniem według rangi i kompresją ścieżki ma zamortyzowany koszt operacji równy:

  1. AO(n)
  2. BO(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała
  3. CO(n²)
  4. DDokładnie O(log n)

Klucz odpowiedzi

  1. 1. C · Kopiec
  2. 2. A · Węzłami, które mają tego samego rodzica
  3. 3. B · Stos
  4. 4. A · 20
  5. 5. C · Wysokość O(log n) dzięki równoważeniu
  6. 6. A · Rosnącej (posortowanej)
  7. 7. D · Odpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)
  8. 8. B · O(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała

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