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

W jakiej kolejności przejście postorder (wsteczne) drzewa binarnego odwiedza węzły?

  1. ALewe poddrzewo, potem węzeł, potem prawe poddrzewo
  2. BLewe poddrzewo, potem prawe poddrzewo, potem węzeł
  3. CPrawe poddrzewo, potem węzeł, potem lewe poddrzewo
  4. DWęzeł, potem lewe poddrzewo, potem prawe poddrzewo
2.Łatwy

Czym jest graf skierowany?

  1. AGrafem, w którym każda para różnych wierzchołków jest połączona krawędzią
  2. BGrafem, którego wszystkie krawędzie mają wagi
  3. CGrafem bez cykli
  4. DGrafem, którego krawędzie mają kierunek od jednego wierzchołka do drugiego
3.Łatwy

Co zawiera wskaźnik next ostatniego węzła listy jednokierunkowej?

  1. ALiczbę węzłów na liście
  2. BAdres poprzedniego węzła
  3. CNull (brak węzła)
  4. DAdres pierwszego węzła
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. A4 2 5 1 3
  2. B4 5 2 3 1
  3. C1 2 4 5 3
  4. D1 2 3 4 5
5.Średni

W binarnym kopcu minimalnym przechowywanym w tablicy (indeksowanie od 0) dzieci węzła o indeksie i znajdują się na pozycjach:

  1. Ai/2 i i/2 + 1
  2. B2i + 1 i 2i + 2
  3. Ci + 1 i i + 2
  4. D2i i 2i + 1
6.Średni

Drzewa AVL i drzewa czerwono-czarne gwarantują:

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

Którą własność musi spełniać drzewo czerwono-czarne?

  1. AKażda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów
  2. BKorzeń musi być czerwony
  3. CKażdy czerwony węzeł musi mieć czerwone dzieci, więc czerwone węzły zawsze tworzą nieprzerwane łańcuchy aż do liści
  4. DKażdy węzeł musi być czerwony
8.Trudny

Dlaczego w tablicy mieszającej z adresowaniem otwartym usuwanie wykonuje się często za pomocą znacznika „nagrobka” (tombstone)?

  1. AOpróżnienie miejsca mogłoby przerwać sekwencję sondowania dla innych kluczy
  2. BUsunięte klucze muszą być przechowywane na zawsze ze względów bezpieczeństwa, więc miejsc nigdy nie można użyć ponownie
  3. CNagrobki przyspieszają haszowanie
  4. DDzięki temu tablica staje się posortowana

Klucz odpowiedzi

  1. 1. B · Lewe poddrzewo, potem prawe poddrzewo, potem węzeł
  2. 2. D · Grafem, którego krawędzie mają kierunek od jednego wierzchołka do drugiego
  3. 3. C · Null (brak węzła)
  4. 4. C · 1 2 4 5 3
  5. 5. B · 2i + 1 i 2i + 2
  6. 6. C · Wysokość O(log n) dzięki równoważeniu
  7. 7. A · Każda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów
  8. 8. A · Opróżnienie miejsca mogłoby przerwać sekwencję sondowania dla innych kluczy

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