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. ASortuje klucze w tablicy
  2. BSzyfruje wartości w tablicy
  3. COdwzorowuje klucz na indeks w tablicy
  4. DLiczy, ile kluczy jest przechowywanych
2.Łatwy

Jaka jest cecha definiująca zbiór jako abstrakcyjny typ danych?

  1. APozwala na dostęp tylko z jednego końca
  2. BPrzechowuje elementy bez duplikatów
  3. CPrzechowuje pary klucz–wartość
  4. DPrzechowuje elementy w kolejności posortowanej
3.Łatwy

Czym jest korzeń drzewa?

  1. AWęzeł o największej wartości
  2. BNajwyższy węzeł, który nie ma rodzica
  3. CWęzeł bez dzieci
  4. DDowolny węzeł w środku
4.Średni

Której struktury danych używa działający program do śledzenia aktywnych wywołań funkcji i ich zmiennych lokalnych?

  1. AStosu wywołań
  2. BTablicy mieszającej funkcji
  3. CBinarnego drzewa poszukiwań ramek
  4. DKolejki pamięci sterty
5.Średni

Ile pamięci zajmuje macierz sąsiedztwa grafu o V wierzchołkach?

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

Jaka jest złożoność czasowa wyszukiwania klucza w zrównoważonym binarnym drzewie poszukiwań?

  1. AO(1)
  2. BO(log n)
  3. CO(n)
  4. DO(n log n)
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. BDokładnie O(log n)
  3. CO(n)
  4. DO(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała
8.Trudny

Algorytm Kahna sortowania topologicznego wielokrotnie usuwa wierzchołki o stopniu wejściowym 0. Która struktura przechowuje te wierzchołki?

  1. AMacierz sąsiedztwa zapisującą, które wierzchołki zostały już usunięte
  2. BKopiec maksymalny uporządkowany według stopnia wyjściowego
  3. CKolejka (lub dowolna kolekcja) wierzchołków o stopniu wejściowym 0
  4. DStos wszystkich odwiedzonych krawędzi

Klucz odpowiedzi

  1. 1. C · Odwzorowuje klucz na indeks w tablicy
  2. 2. B · Przechowuje elementy bez duplikatów
  3. 3. B · Najwyższy węzeł, który nie ma rodzica
  4. 4. A · Stosu wywołań
  5. 5. B · O(V²)
  6. 6. B · O(log n)
  7. 7. D · O(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała
  8. 8. C · Kolejka (lub dowolna kolekcja) wierzchołków o stopniu wejściowym 0

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