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

Czym jest kolizja w tablicy mieszającej?

  1. AOdwzorowaniem dwóch różnych kluczy na ten sam indeks
  2. BWyczerpaniem pamięci przez tablicę
  3. CDwukrotnym zapisaniem dwóch równych kluczy
  4. DSytuacją, w której klucza w ogóle nie da się zahaszować
2.Łatwy

Co przechowuje się dla każdego wierzchołka w reprezentacji grafu za pomocą list sąsiedztwa?

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

W binarnym drzewie poszukiwań wartości w lewym poddrzewie węzła są:

  1. AMniejsze od wartości węzła
  2. BW losowej kolejności
  3. CRówne wartości węzła
  4. DWiększe od wartości węzła
4.Ś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. A5 4 3 2 1
  2. B4 2 5 1 3
  3. C4 5 2 3 1
  4. D1 2 4 5 3
5.Średni

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

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

Jak wstawia się nowy element do kopca binarnego?

  1. AWstawia się go na właściwą posortowaną pozycję, przesuwając o jedno miejsce w prawo wszystkie większe elementy
  2. BUmieszcza się go na końcu tablicy i przesuwa w górę, dopóki narusza własność kopca
  3. CUmieszcza się go w korzeniu i przesuwa w dół
  4. DBuduje się cały kopiec od nowa
7.Trudny

Dlaczego serwer może losowo wybierać funkcję mieszającą z rodziny uniwersalnej?

  1. ABy wyeliminować potrzebę zmiany rozmiaru tablicy
  2. BBy było bardzo mało prawdopodobne, że atakujący dobierze wiele kluczy, które wszystkie kolidują
  3. CBy tablica mieszająca była posortowana
  4. DBy zagwarantować, że żadne dwa klucze nigdy nie będą kolidować, jakie klucze by nie wysłał atakujący
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. BStos wszystkich odwiedzonych krawędzi
  3. CKopiec maksymalny uporządkowany według stopnia wyjściowego
  4. DKolejka (lub dowolna kolekcja) wierzchołków o stopniu wejściowym 0

Klucz odpowiedzi

  1. 1. A · Odwzorowaniem dwóch różnych kluczy na ten sam indeks
  2. 2. C · Listę jego sąsiednich wierzchołków
  3. 3. A · Mniejsze od wartości węzła
  4. 4. C · 4 5 2 3 1
  5. 5. B · O(1)
  6. 6. B · Umieszcza się go na końcu tablicy i przesuwa w górę, dopóki narusza własność kopca
  7. 7. B · By było bardzo mało prawdopodobne, że atakujący dobierze wiele kluczy, które wszystkie kolidują
  8. 8. D · 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.