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 przechowuje się dla każdego wierzchołka w reprezentacji grafu za pomocą list sąsiedztwa?

  1. AListę jego sąsiednich wierzchołków
  2. BWiersz V wartości logicznych
  3. CNajkrótszą ścieżkę do każdego innego wierzchołka
  4. DŁączną liczbę krawędzi w grafie
2.Łatwy

Która struktura danych działa według zasady „ostatni na wejściu, pierwszy na wyjściu” (LIFO)?

  1. AStos
  2. BLista wiązana
  3. CKolejka
  4. DTablica mieszająca
3.Łatwy

Czym jest stopień wierzchołka w grafie nieskierowanym?

  1. ADługością najdłuższej ścieżki z niego wychodzącej
  2. BLiczbą wierzchołków w grafie
  3. CLiczbą krawędzi z nim połączonych
  4. DJego pozycją na liście sąsiedztwa
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

Dlaczego kopiec binarny można przechowywać w tablicy bez żadnych wskaźników?

  1. AJest zupełnym drzewem binarnym, więc pozycje wynikają z prostych wzorów na indeksy
  2. BTablice automatycznie utrzymują klucze w kolejności posortowanej, więc wskaźniki nie są potrzebne
  3. CWszystkie klucze w kopcu są równe
  4. DKopce nigdy nie zawierają więcej niż 100 elementów
6.Średni

Sieć drogowa ma 100 000 skrzyżowań, z których każde łączy się z około 4 innymi. Która reprezentacja jest najodpowiedniejsza?

  1. AKopiec binarny krawędzi
  2. BListy sąsiedztwa
  3. CJedna posortowana tablica wierzchołków
  4. DMacierz sąsiedztwa
7.Trudny

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

  1. AZ możliwymi fałszywie ujemnymi wynikami, ale bez fałszywie dodatnich
  2. BTylko dla liczb
  3. CZ możliwymi fałszywie dodatnimi wynikami, ale bez fałszywie ujemnych
  4. DZawsze dokładnie
8.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

Klucz odpowiedzi

  1. 1. A · Listę jego sąsiednich wierzchołków
  2. 2. A · Stos
  3. 3. C · Liczbą krawędzi z nim połączonych
  4. 4. B · O(1)
  5. 5. A · Jest zupełnym drzewem binarnym, więc pozycje wynikają z prostych wzorów na indeksy
  6. 6. B · Listy sąsiedztwa
  7. 7. C · Z możliwymi fałszywie dodatnimi wynikami, ale bez fałszywie ujemnych
  8. 8. D · O(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała

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