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

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

  1. ALewe poddrzewo, potem węzeł, potem prawe poddrzewo
  2. BLewe poddrzewo, potem prawe poddrzewo, potem węzeł
  3. CPrawe poddrzewo, potem węzeł, potem lewe poddrzewo
  4. DWęzeł, potem lewe poddrzewo, potem prawe poddrzewo
2.Łatwy

Czym jest kolizja w tablicy mieszającej?

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

Gdzie znajduje się najmniejszy element binarnego kopca minimalnego?

  1. AW skrajnie lewym liściu
  2. BW korzeniu
  3. CW którymś liściu, którego trzeba szukać
  4. DNa ostatniej pozycji tablicy
4.Ś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. AListy sąsiedztwa
  2. BJedna posortowana tablica wierzchołków
  3. CKopiec binarny krawędzi
  4. DMacierz sąsiedztwa
5.Średni

Ile trwa wyszukiwanie słowa o długości L w drzewie trie ze stałym alfabetem?

  1. AO(n), gdzie n to liczba słów
  2. BO(L × n)
  3. CO(log n), gdzie n to liczba słów
  4. DO(L), niezależnie od liczby przechowywanych słów
6.Średni

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

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

Które operacje w O(log n) obsługuje drzewo Fenwicka (binary indexed tree) zbudowane nad tablicą n liczb?

  1. ASortowanie tablicy i wyszukiwanie binarne
  2. BZnajdowanie mediany w O(1)
  3. CZapytania o sumy prefiksowe i aktualizacje pojedynczych elementów
  4. DWstawianie elementów na dowolnej pozycji

Klucz odpowiedzi

  1. 1. B · Lewe poddrzewo, potem prawe poddrzewo, potem węzeł
  2. 2. D · Odwzorowaniem dwóch różnych kluczy na ten sam indeks
  3. 3. B · W korzeniu
  4. 4. A · Listy sąsiedztwa
  5. 5. D · O(L), niezależnie od liczby przechowywanych słów
  6. 6. B · O(1)
  7. 7. C · O(α(n)), gdzie α to odwrotność funkcji Ackermanna, praktycznie stała
  8. 8. C · Zapytania o sumy prefiksowe i aktualizacje pojedynczych elementów

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