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

Jaka jest cecha definiująca zbiór jako abstrakcyjny typ danych?

  1. APrzechowuje pary klucz–wartość
  2. BPrzechowuje elementy w kolejności posortowanej
  3. CPrzechowuje elementy bez duplikatów
  4. DPozwala na dostęp tylko z jednego końca
2.Łatwy

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

  1. AW losowej kolejności
  2. BRówne wartości węzła
  3. CMniejsze od wartości węzła
  4. DWiększe od wartości węzła
3.Łatwy

Co przechowuje mapa (słownik)?

  1. AWartości posortowane według wielkości
  2. BPary klucz–wartość z unikalnymi kluczami
  3. CPary równych kluczy
  4. DTylko wartości w kolejności wstawiania
4.Średni

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

  1. AO(log n)
  2. BO(1)
  3. CO(n log n)
  4. DO(n)
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(V)
  4. DO(E)
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 liście dwukierunkowej
  2. BW posortowanej tablicy
  3. CW liście jednokierunkowej
  4. DW tablicy dynamicznej
7.Trudny

Jak wykryć, czy lista jednokierunkowa zawiera cykl, używając O(1) dodatkowej pamięci?

  1. APrzesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
  2. BZapisywać każdy odwiedzony węzeł w zbiorze mieszającym
  3. CPosortować listę i szukać duplikatów
  4. DLiczyć węzły, aż liczba przekroczy pole z długością listy
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. BPojedynczą rotację w lewo w węźle
  3. CRotację w prawo w lewym dziecku, a potem rotację w lewo w węźle
  4. DPojedynczą rotację w prawo w węźle

Klucz odpowiedzi

  1. 1. C · Przechowuje elementy bez duplikatów
  2. 2. C · Mniejsze od wartości węzła
  3. 3. B · Pary klucz–wartość z unikalnymi kluczami
  4. 4. A · O(log n)
  5. 5. B · O(1)
  6. 6. A · W liście dwukierunkowej
  7. 7. A · Przesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
  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.