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

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

  1. AAdres pierwszego węzła
  2. BLiczbę węzłów na liście
  3. CNull (brak węzła)
  4. DAdres poprzedniego węzła
2.Łatwy

Co przechowuje mapa (słownik)?

  1. APary równych kluczy
  2. BWartości posortowane według wielkości
  3. CTylko wartości w kolejności wstawiania
  4. DPary klucz–wartość z unikalnymi kluczami
3.Ł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łem i jego rodzicem
  3. CWęzłami, które nie mają dzieci
  4. DWęzłami, które mają tego samego rodzica
4.Średni

Ile węzłów ma doskonałe drzewo binarne o wysokości h, gdy wysokość liczy się w krawędziach?

  1. A2h+1 − 1
  2. B2h + 1
  3. Ch2
  4. D2h
5.Średni

Ile pamięci zajmują listy sąsiedztwa dla grafu o V wierzchołkach i E krawędziach?

  1. AO(V + E)
  2. BO(V × E)
  3. CO(E²)
  4. DO(V²)
6.Ś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 2 5 1 3
  3. C4 5 2 3 1
  4. D1 2 3 4 5
7.Trudny

Która struktura pozwala obliczyć maksimum każdego okna o rozmiarze k w tablicy w łącznym czasie O(n)?

  1. ADeque przechowująca indeksy w kolejności malejących wartości
  2. BPosortowana tablica aktualizowana przez przesuwanie
  3. CLista jednokierunkowa elementów okna
  4. DKopiec minimalny budowany od nowa dla każdego okna
8.Trudny

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

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

Klucz odpowiedzi

  1. 1. C · Null (brak węzła)
  2. 2. D · Pary klucz–wartość z unikalnymi kluczami
  3. 3. D · Węzłami, które mają tego samego rodzica
  4. 4. A · 2h+1 − 1
  5. 5. A · O(V + E)
  6. 6. A · 1 2 4 5 3
  7. 7. A · Deque przechowująca indeksy w kolejności malejących wartości
  8. 8. A · Odpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)

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