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

Wysokość drzewa definiuje się zwykle jako:

  1. ALiczbę liści w drzewie
  2. BLiczbę dzieci korzenia
  3. CLiczbę krawędzi na najdłuższej ścieżce od korzenia do liścia
  4. DŁączną liczbę węzłów w drzewie, wliczając korzeń i każdy liść
2.Łatwy

Czym jest korzeń drzewa?

  1. AWęzeł o największej wartości
  2. BNajwyższy węzeł, który nie ma rodzica
  3. CDowolny węzeł w środku
  4. DWęzeł bez dzieci
3.Łatwy

Jaka jest główna różnica między tablicą statyczną a tablicą dynamiczną?

  1. ATablica dynamiczna przechowuje elementy w połączonych węzłach, by mogła rosnąć po jednym elemencie
  2. BTablica statyczna ma wolniejszy dostęp po indeksie
  3. CTablica dynamiczna może rosnąć, przenosząc się do większego bloku pamięci
  4. DTablica statyczna może przechowywać tylko liczby
4.Średni

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

  1. AKolejki
  2. BBinarnego drzewa poszukiwań
  3. CStosu
  4. DTablicy mieszającej
5.Średni

Drzewa AVL i drzewa czerwono-czarne gwarantują:

  1. APrzechowywanie kluczy w kolejności wstawiania
  2. BWysokość O(log n) dzięki równoważeniu
  3. CŻe żaden węzeł nie ma dwojga dzieci
  4. DWyszukiwanie w czasie stałym w każdym przypadku
6.Średni

Masz referencję do węzła w środku listy. W której liście możesz go usunąć w O(1)?

  1. AW liście dwukierunkowej
  2. BW posortowanej tablicy
  3. CW liście jednokierunkowej
  4. DW tablicy dynamicznej
7.Trudny

Dlaczego ze standardowego filtru Blooma nie można po prostu usuwać elementów przez zerowanie ich bitów?

  1. ABitów w filtrze Blooma nie można zmieniać po jego utworzeniu
  2. BTe bity mogą należeć także do innych elementów, co spowodowałoby wyniki fałszywie negatywne
  3. CUsuwanie zwiększyłoby odsetek wyników fałszywie pozytywnych do 100%
  4. DFiltry Blooma przechowują całe elementy, których po zahaszowaniu nie da się ponownie zlokalizować
8.Trudny

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

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

Klucz odpowiedzi

  1. 1. C · Liczbę krawędzi na najdłuższej ścieżce od korzenia do liścia
  2. 2. B · Najwyższy węzeł, który nie ma rodzica
  3. 3. C · Tablica dynamiczna może rosnąć, przenosząc się do większego bloku pamięci
  4. 4. C · Stosu
  5. 5. B · Wysokość O(log n) dzięki równoważeniu
  6. 6. A · W liście dwukierunkowej
  7. 7. B · Te bity mogą należeć także do innych elementów, co spowodowałoby wyniki fałszywie negatywne
  8. 8. A · Mapa mieszająca połączona z listą dwukierunkową

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