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 korzeń drzewa?

  1. ANajwyższy węzeł, który nie ma rodzica
  2. BDowolny węzeł w środku
  3. CWęzeł bez dzieci
  4. DWęzeł o największej wartości
2.Łatwy

Co robi funkcja mieszająca w tablicy mieszającej?

  1. AOdwzorowuje klucz na indeks w tablicy
  2. BLiczy, ile kluczy jest przechowywanych
  3. CSortuje klucze w tablicy
  4. DSzyfruje wartości w tablicy
3.Łatwy

W jakiej kolejności przejście postorder (wsteczne) drzewa binarnego odwiedza węzły?

  1. ALewe poddrzewo, potem węzeł, potem prawe poddrzewo
  2. BWęzeł, potem lewe poddrzewo, potem prawe poddrzewo
  3. CLewe poddrzewo, potem prawe poddrzewo, potem węzeł
  4. DPrawe poddrzewo, potem węzeł, potem lewe poddrzewo
4.Średni

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

  1. AKopca
  2. BWyłącznie tablicy mieszającej
  3. CStosu
  4. DKolejki
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. B20
  3. C70
  4. D40
6.Średni

Jak znaleźć najmniejszy klucz w binarnym drzewie poszukiwań?

  1. AIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  2. BSprawdzić tylko korzeń
  3. COdwiedzić każdy liść i porównać je
  4. DIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
7.Trudny

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

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

Jaki jest pesymistyczny koszt pojedynczej operacji find w strukturze union-find z n elementami bez łączenia według rangi (union by rank) i bez kompresji ścieżek?

  1. AO(log n)
  2. BO(α(n))
  3. CO(n)
  4. DO(1)

Klucz odpowiedzi

  1. 1. A · Najwyższy węzeł, który nie ma rodzica
  2. 2. A · Odwzorowuje klucz na indeks w tablicy
  3. 3. C · Lewe poddrzewo, potem prawe poddrzewo, potem węzeł
  4. 4. C · Stosu
  5. 5. B · 20
  6. 6. A · Iść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  7. 7. C · Kolejka (lub dowolna kolekcja) wierzchołków o stopniu wejściowym 0
  8. 8. C · O(n)

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