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 preorder (wzdłużne) drzewa binarnego odwiedza węzły?

  1. APoziomami, od góry
  2. BLewe poddrzewo, potem prawe poddrzewo, potem węzeł
  3. CLewe poddrzewo, potem węzeł, potem prawe poddrzewo
  4. DWęzeł, potem lewe poddrzewo, potem prawe poddrzewo
2.Łatwy

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

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

Jak nazywa się operacja na stosie, która dodaje element na wierzchołek?

  1. APeek
  2. BEnqueue
  3. CPush
  4. DPop
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 3 4 5
  2. B4 5 2 3 1
  3. C1 2 4 5 3
  4. D4 2 5 1 3
5.Średni

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

  1. APoziomami
  2. BZawsze malejącej
  3. CRosnącej (posortowanej)
  4. DWstawiania
6.Średni

Która metoda rozwiązywania kolizji przechowuje kolidujące klucze w liście w tym samym kubełku?

  1. AHaszowanie podwójne
  2. BSondowanie kwadratowe
  3. CSondowanie liniowe
  4. DŁańcuchowanie (separate chaining)
7.Trudny

Która para przejść zawsze jednoznacznie wyznacza drzewo binarne o różnych kluczach?

  1. ASamo przejście poziomami
  2. BPreorder i inorder
  3. CSam preorder
  4. DPreorder i postorder
8.Trudny

Który problem próbkowania liniowego zmniejsza przede wszystkim haszowanie podwójne?

  1. APotrzebę przechowywania kluczy w tablicy
  2. BKoszt O(n) odczytu wartości klucza
  3. CGrupowanie pierwotne (primary clustering), czyli powstawanie długich ciągów zajętych pozycji
  4. DPotrzebę funkcji mieszającej

Klucz odpowiedzi

  1. 1. D · Węzeł, potem lewe poddrzewo, potem prawe poddrzewo
  2. 2. A · Lewe poddrzewo, potem prawe poddrzewo, potem węzeł
  3. 3. C · Push
  4. 4. C · 1 2 4 5 3
  5. 5. C · Rosnącej (posortowanej)
  6. 6. D · Łańcuchowanie (separate chaining)
  7. 7. B · Preorder i inorder
  8. 8. C · Grupowanie pierwotne (primary clustering), czyli powstawanie długich ciągów zajętych pozycji

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