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 cykl w grafie?

  1. AKrawędzią o wadze zero
  2. BŚcieżką, która odwiedza każdy wierzchołek
  3. CŚcieżką, która zaczyna się i kończy w tym samym wierzchołku
  4. DWierzchołkiem bez krawędzi
2.Łatwy

Jaka jest główna różnica między tablicą statyczną a tablicą dynamiczną?

  1. ATablica dynamiczna może rosnąć, przenosząc się do większego bloku pamięci
  2. BTablica statyczna może przechowywać tylko liczby
  3. CTablica statyczna ma wolniejszy dostęp po indeksie
  4. DTablica dynamiczna przechowuje elementy w połączonych węzłach, by mogła rosnąć po jednym elemencie
3.Łatwy

Czym jest stopień wierzchołka w grafie nieskierowanym?

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

Jaka jest złożoność czasowa wyszukiwania klucza w zrównoważonym binarnym drzewie poszukiwań?

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

Masz referencję do węzła w środku listy. W której liście możesz go usunąć w O(1)?

  1. AW posortowanej tablicy
  2. BW liście dwukierunkowej
  3. CW tablicy dynamicznej
  4. DW liście jednokierunkowej
7.Trudny

Usunięcie węzła z dwojgiem dzieci z binarnego drzewa poszukiwań wykonuje się zwykle przez:

  1. AZbudowanie od nowa poddrzewa poniżej węzła i ponowne wstawienie wszystkich zawartych w nim kluczy
  2. BZastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
  3. CZamianę go z korzeniem
  4. DUsunięcie całego poddrzewa
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 prawo w lewym dziecku, a potem rotację w lewo w węźle
  2. BPojedynczą rotację w prawo w węźle
  3. CPojedynczą rotację w lewo w węźle
  4. DRotację w lewo w lewym dziecku, a potem rotację w prawo w węźle

Klucz odpowiedzi

  1. 1. C · Ścieżką, która zaczyna się i kończy w tym samym wierzchołku
  2. 2. A · Tablica dynamiczna może rosnąć, przenosząc się do większego bloku pamięci
  3. 3. C · Liczbą krawędzi z nim połączonych
  4. 4. D · O(L), niezależnie od liczby przechowywanych słów
  5. 5. B · O(log n)
  6. 6. B · W liście dwukierunkowej
  7. 7. B · Zastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
  8. 8. D · 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.