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

Czym jest cykl w grafie?

  1. AŚcieżką, która zaczyna się i kończy w tym samym wierzchołku
  2. BKrawędzią o wadze zero
  3. CWierzchołkiem bez krawędzi
  4. DŚcieżką, która odwiedza każdy wierzchołek
3.Łatwy

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

  1. AOdczyt ostatniego elementu po indeksie
  2. BWstawianie na początku
  3. CUstalenie długości tablicy o stałym rozmiarze
  4. DDostęp do 5. elementu
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 postorder?

  1. A1 2 4 5 3
  2. B5 4 3 2 1
  3. C4 2 5 1 3
  4. D4 5 2 3 1
5.Średni

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

  1. AŁańcuchowanie (separate chaining)
  2. BHaszowanie podwójne
  3. CSondowanie kwadratowe
  4. DSondowanie liniowe
6.Średni

Jaki jest maksymalny możliwy współczynnik zapełnienia tablicy mieszającej z adresowaniem otwartym?

  1. A1
  2. BNie ma maksimum
  3. C0,5
  4. D2
7.Trudny

Musisz zachować k najmniejszych wartości ze strumienia n liczb, używając O(k) pamięci. Które podejście działa w czasie O(n log k)?

  1. AKopiec maksymalny o rozmiarze k, którego korzeń zastępuje się, gdy pojawi się mniejsza wartość
  2. BPosortowana tablica wszystkich n wartości
  3. CKolejka FIFO ostatnich k wartości
  4. DKopiec minimalny przechowujący wszystkie n wartości, z którego na końcu zdejmuje się k najmniejszych
8.Trudny

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

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

Klucz odpowiedzi

  1. 1. B · Węzłami, które mają tego samego rodzica
  2. 2. A · Ścieżką, która zaczyna się i kończy w tym samym wierzchołku
  3. 3. B · Wstawianie na początku
  4. 4. D · 4 5 2 3 1
  5. 5. A · Łańcuchowanie (separate chaining)
  6. 6. A · 1
  7. 7. A · Kopiec maksymalny o rozmiarze k, którego korzeń zastępuje się, gdy pojawi się mniejsza wartość
  8. 8. D · 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.