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 robi funkcja mieszająca w tablicy mieszającej?

  1. ASzyfruje wartości w tablicy
  2. BOdwzorowuje klucz na indeks w tablicy
  3. CSortuje klucze w tablicy
  4. DLiczy, ile kluczy jest przechowywanych
2.Łatwy

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

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

Graf składa się z:

  1. ATylko korzenia i liści
  2. BWierzchołków (węzłów) połączonych krawędziami
  3. CWyłącznie kluczy i skrótów
  4. DWierszy i kolumn
4.Średni

Ile czasu zajmuje sprawdzenie, czy istnieje krawędź (u, v), przy użyciu macierzy sąsiedztwa?

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

Klucze 50, 30, 70, 20, 40 wstawia się w tej kolejności do pustego binarnego drzewa poszukiwań. Co jest lewym dzieckiem 30?

  1. A50
  2. B40
  3. C70
  4. D20
6.Średni

W binarnym kopcu minimalnym przechowywanym w tablicy (indeksowanie od 0) dzieci węzła o indeksie i znajdują się na pozycjach:

  1. Ai + 1 i i + 2
  2. B2i i 2i + 1
  3. C2i + 1 i 2i + 2
  4. Di/2 i i/2 + 1
7.Trudny

Struktura union-find (zbiory rozłączne) z łączeniem według rangi i kompresją ścieżki ma zamortyzowany koszt operacji równy:

  1. AO(n)
  2. BO(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała
  3. CDokładnie O(log n)
  4. DO(n²)
8.Trudny

Klucze 5, 3, 8, 1 wstawia się w tej kolejności do pustego binarnego kopca minimalnego opartego na tablicy. Jak wygląda końcowa tablica?

  1. A[1, 3, 5, 8]
  2. B[1, 5, 8, 3]
  3. C[1, 3, 8, 5]
  4. D[3, 1, 8, 5]

Klucz odpowiedzi

  1. 1. B · Odwzorowuje klucz na indeks w tablicy
  2. 2. A · Pary klucz–wartość lokalizowane przez funkcję mieszającą
  3. 3. B · Wierzchołków (węzłów) połączonych krawędziami
  4. 4. B · O(1)
  5. 5. D · 20
  6. 6. C · 2i + 1 i 2i + 2
  7. 7. B · O(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała
  8. 8. C · [1, 3, 8, 5]

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