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 danych najlepiej nadaje się do funkcji „cofnij” (undo) w edytorze tekstu?

  1. AKolejka
  2. BZbiór mieszający
  3. CStos
  4. DGraf
2.Ł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. CWęzeł, potem lewe poddrzewo, potem prawe poddrzewo
  4. DLewe poddrzewo, potem węzeł, potem prawe poddrzewo
3.Łatwy

Czym jest liść w drzewie?

  1. AWęzłem o największej wartości
  2. BWęzłem bez dzieci
  3. CWęzłem z dokładnie jednym dzieckiem
  4. DWęzłem bez rodzica
4.Średni

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

  1. AO(V + E)
  2. BO(E²)
  3. CO(V × E)
  4. DO(V²)
5.Średni

Gdzie w kopcu binarnym przechowywanym w tablicy od indeksu 0 znajduje się rodzic węzła o indeksie i?

  1. APod indeksem ⌊(i − 1) / 2⌋
  2. BPod indeksem ⌊i / 2⌋ + 1
  3. CPod indeksem 2i + 1
  4. DPod indeksem i − 1
6.Średni

Której struktury danych używa się, by sprawdzić, czy nawiasy w „{[()]}” są zrównoważone?

  1. ATablicy mieszającej
  2. BKolejki
  3. CBinarnego drzewa poszukiwań
  4. DStosu
7.Trudny

Która struktura danych umożliwia pamięć podręczną LRU (least recently used) z operacjami get i put w O(1)?

  1. AWyłącznie binarne drzewo poszukiwań
  2. BPojedyncza posortowana tablica
  3. CWyłącznie stos
  4. DMapa mieszająca połączona z listą dwukierunkową
8.Trudny

Filtr Blooma potrafi odpowiedzieć na pytanie „czy ten element należy do zbioru?”:

  1. AZ możliwymi fałszywie dodatnimi wynikami, ale bez fałszywie ujemnych
  2. BZawsze dokładnie
  3. CTylko dla liczb
  4. DZ możliwymi fałszywie ujemnymi wynikami, ale bez fałszywie dodatnich

Klucz odpowiedzi

  1. 1. C · Stos
  2. 2. C · Węzeł, potem lewe poddrzewo, potem prawe poddrzewo
  3. 3. B · Węzłem bez dzieci
  4. 4. A · O(V + E)
  5. 5. A · Pod indeksem ⌊(i − 1) / 2⌋
  6. 6. D · Stosu
  7. 7. D · Mapa mieszająca połączona z listą dwukierunkową
  8. 8. A · Z możliwymi fałszywie dodatnimi wynikami, ale bez fałszywie ujemnych

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