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

Która operacja jest wolna w tablicy, ale szybka na początku listy wiązanej?

  1. AWstawianie na początku
  2. BOdczyt ostatniego elementu po indeksie
  3. CUstalenie długości tablicy o stałym rozmiarze
  4. DDostęp do 5. elementu
2.Łatwy

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

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

Jak nazywa się operacja na kolejce, która usuwa element z jej początku?

  1. APush
  2. BDequeue
  3. CEnqueue
  4. DInsert
4.Średni

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

  1. AW tablicy dynamicznej
  2. BW liście dwukierunkowej
  3. CW liście jednokierunkowej
  4. DW posortowanej tablicy
5.Średni

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

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

Ile pamięci zajmują listy sąsiedztwa dla grafu o V wierzchołkach i E krawędziach?

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

Dlaczego w tablicy mieszającej z adresowaniem otwartym usuwanie wykonuje się często za pomocą znacznika „nagrobka” (tombstone)?

  1. ADzięki temu tablica staje się posortowana
  2. BNagrobki przyspieszają haszowanie
  3. COpróżnienie miejsca mogłoby przerwać sekwencję sondowania dla innych kluczy
  4. DUsunięte klucze muszą być przechowywane na zawsze ze względów bezpieczeństwa, więc miejsc nigdy nie można użyć ponownie
8.Trudny

Co robi drzewo splay po każdym dostępie?

  1. ABuduje całe drzewo od nowa w formie zrównoważonej
  2. BPrzenosi odwiedzony węzeł do liścia
  3. CRotacjami przenosi odwiedzony węzeł do korzenia
  4. DPrzekolorowuje węzły na ścieżce wyszukiwania

Klucz odpowiedzi

  1. 1. A · Wstawianie na początku
  2. 2. B · Przechowuje elementy bez duplikatów
  3. 3. B · Dequeue
  4. 4. B · W liście dwukierunkowej
  5. 5. C · O(1)
  6. 6. B · O(V + E)
  7. 7. C · Opróżnienie miejsca mogłoby przerwać sekwencję sondowania dla innych kluczy
  8. 8. C · Rotacjami przenosi odwiedzony węzeł do korzenia

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