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 struktura danych działa według zasady „ostatni na wejściu, pierwszy na wyjściu” (LIFO)?

  1. AStos
  2. BTablica mieszająca
  3. CLista wiązana
  4. DKolejka
2.Łatwy

Która operacja ma złożoność O(1) dla tablicy, ale O(n) dla listy jednokierunkowej?

  1. AWstawianie na początku
  2. BDostęp do elementu o indeksie i
  3. COdczyt pierwszego elementu
  4. DUsuwanie pierwszego elementu
3.Łatwy

Gdzie znajduje się najmniejszy element binarnego kopca minimalnego?

  1. AW skrajnie lewym liściu
  2. BW korzeniu
  3. CNa ostatniej pozycji tablicy
  4. DW którymś liściu, którego trzeba szukać
4.Średni

W binarnym kopcu minimalnym przechowywanym w tablicy (indeksowanie od 0) dzieci węzła o indeksie i znajdują się na pozycjach:

  1. Ai/2 i i/2 + 1
  2. Bi + 1 i i + 2
  3. C2i + 1 i 2i + 2
  4. D2i i 2i + 1
5.Średni

Gdzie w kopcu binarnym przechowywanym w tablicy od indeksu 0 znajduje się rodzic węzła o indeksie i?

  1. APod indeksem ⌊i / 2⌋ + 1
  2. BPod indeksem ⌊(i − 1) / 2⌋
  3. CPod indeksem i − 1
  4. DPod indeksem 2i + 1
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 × E)
  4. DO(V²)
7.Trudny

Ile trwa wyszukanie dowolnego klucza w binarnym kopcu minimalnym o n elementach?

  1. AO(n)
  2. BO(log log n)
  3. CO(log n)
  4. DO(1)
8.Trudny

Złożoność czasowa operacji decrease-key w kopcu binarnym (przy znanej pozycji elementu) wynosi:

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

Klucz odpowiedzi

  1. 1. A · Stos
  2. 2. B · Dostęp do elementu o indeksie i
  3. 3. B · W korzeniu
  4. 4. C · 2i + 1 i 2i + 2
  5. 5. B · Pod indeksem ⌊(i − 1) / 2⌋
  6. 6. B · O(V + E)
  7. 7. A · O(n)
  8. 8. C · O(log n)

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