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

Tablica mieszająca (hash table) przechowuje dane jako:

  1. AWyłącznie posortowaną listę
  2. BDrzewo z uporządkowanymi kluczami
  3. CPary klucz–wartość lokalizowane przez funkcję mieszającą
  4. DCiąg znaków o stałej długości
2.Łatwy

Czym jest stopień wierzchołka w grafie nieskierowanym?

  1. AJego pozycją na liście sąsiedztwa
  2. BLiczbą wierzchołków w grafie
  3. CLiczbą krawędzi z nim połączonych
  4. DDługością najdłuższej ścieżki z niego wychodzącej
3.Łatwy

Ile krawędzi ma drzewo o n węzłach?

  1. An + 1
  2. B2n
  3. Cn − 1
  4. Dn
4.Średni

Aplikacja potrzebuje szybkiego wyszukiwania, a także wypisywania kluczy w kolejności posortowanej i odpowiadania na zapytania o zakres. Która struktura pasuje najlepiej?

  1. ATablica mieszająca
  2. BNieposortowana lista wiązana
  3. CZrównoważone binarne drzewo poszukiwań
  4. DStos
5.Średni

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

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

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

  1. ANa jej głównej przekątnej zawsze są jedynki
  2. BJest zawsze górnotrójkątna
  3. CKażdy wiersz ma dokładnie jedną jedynkę
  4. DJest symetryczna względem głównej przekątnej
7.Trudny

Jaki jest czas działania przeszukiwania wszerz (BFS) w grafie o V wierzchołkach przechowywanym jako macierz sąsiedztwa?

  1. AO(V)
  2. BO(V²)
  3. CO(V + E)
  4. DO(E log V)
8.Trudny

Węzeł AVL jest niezrównoważony, bo prawe poddrzewo jego lewego dziecka stało się zbyt wysokie (przypadek lewo-prawo). Jaką naprawę się stosuje?

  1. ARotację w lewo w lewym dziecku, a potem rotację w prawo w węźle
  2. BRotację w prawo w lewym dziecku, a potem rotację w lewo w węźle
  3. CPojedynczą rotację w prawo w węźle
  4. DPojedynczą rotację w lewo w węźle

Klucz odpowiedzi

  1. 1. C · Pary klucz–wartość lokalizowane przez funkcję mieszającą
  2. 2. C · Liczbą krawędzi z nim połączonych
  3. 3. C · n − 1
  4. 4. C · Zrównoważone binarne drzewo poszukiwań
  5. 5. D · O(L), niezależnie od liczby przechowywanych słów
  6. 6. D · Jest symetryczna względem głównej przekątnej
  7. 7. B · O(V²)
  8. 8. A · Rotację w lewo w lewym dziecku, a potem rotację w prawo w węźle

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