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

Graf składa się z:

  1. AWierszy i kolumn
  2. BWyłącznie kluczy i skrótów
  3. CTylko korzenia i liści
  4. DWierzchołków (węzłów) połączonych krawędziami
2.Łatwy

Tablica mieszająca (hash table) przechowuje dane jako:

  1. ACiąg znaków o stałej długości
  2. BPary klucz–wartość lokalizowane przez funkcję mieszającą
  3. CWyłącznie posortowaną listę
  4. DDrzewo z uporządkowanymi kluczami
3.Łatwy

Czym jest współczynnik zapełnienia (load factor) tablicy mieszającej?

  1. ADotychczasową liczbą kolizji
  2. BCzasem potrzebnym do wczytania tablicy z dysku
  3. CLiczbą przechowywanych elementów podzieloną przez liczbę kubełków
  4. DLiczbą kubełków podzieloną przez średnią długość przechowywanych kluczy
4.Średni

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

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

Której struktury danych używa przeszukiwanie w głąb (DFS) w wersji iteracyjnej?

  1. AKolejki
  2. BKopca
  3. CStosu
  4. DWyłącznie tablicy mieszającej
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 postorder?

  1. A4 2 5 1 3
  2. B5 4 3 2 1
  3. C1 2 4 5 3
  4. D4 5 2 3 1
7.Trudny

Obiekt jest przechowywany jako klucz w mapie mieszającej, a następnie zmienia się pole używane przez jego funkcję mieszającą. Jaki jest prawdopodobny skutek?

  1. AMapa zgłasza błąd w chwili zmiany pola
  2. BWyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu
  3. CNic się nie zmienia, bo skrót klucza oblicza się tylko raz przy uruchomieniu programu
  4. DMapa automatycznie przenosi klucz do nowego kubełka
8.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. BKopiec minimalny przechowujący wszystkie n wartości, z którego na końcu zdejmuje się k najmniejszych
  3. CPosortowana tablica wszystkich n wartości
  4. DKolejka FIFO ostatnich k wartości

Klucz odpowiedzi

  1. 1. D · Wierzchołków (węzłów) połączonych krawędziami
  2. 2. B · Pary klucz–wartość lokalizowane przez funkcję mieszającą
  3. 3. C · Liczbą przechowywanych elementów podzieloną przez liczbę kubełków
  4. 4. C · O(V + E)
  5. 5. C · Stosu
  6. 6. D · 4 5 2 3 1
  7. 7. B · Wyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu
  8. 8. A · Kopiec maksymalny o rozmiarze k, którego korzeń zastępuje się, gdy pojawi się mniejsza wartość

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