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

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

  1. ADequeue
  2. BEnqueue
  3. CInsert
  4. DPush
2.Łatwy

Której struktury danych używa się do przejścia drzewa poziomami (level-order)?

  1. AKolejki
  2. BKolejki priorytetowej
  3. CStosu
  4. DTablicy mieszającej
3.Łatwy

Która struktura jest zwykle używana do implementacji kolejki priorytetowej?

  1. AStos
  2. BCiąg znaków
  3. CKopiec
  4. DNieuporządkowana lista jednokierunkowa
4.Średni

Drzewa AVL i drzewa czerwono-czarne gwarantują:

  1. APrzechowywanie kluczy w kolejności wstawiania
  2. BŻe żaden węzeł nie ma dwojga dzieci
  3. CWyszukiwanie w czasie stałym w każdym przypadku
  4. DWysokość O(log n) dzięki równoważeniu
5.Średni

Jak w kolejce cyklicznej przechowywanej w tablicy o pojemności n oblicza się następną pozycję po indeksie i?

  1. A(i + 1) mod n
  2. B2i + 1
  3. C(i − 1) mod n
  4. Di + 1
6.Średni

Drzewo binarne ma korzeń 1 z lewym dzieckiem 2 i prawym dzieckiem 3; węzeł 2 ma dzieci 4 (lewe) i 5 (prawe). Jaki jest wynik przejścia postorder?

  1. A4 5 2 3 1
  2. B4 2 5 1 3
  3. C5 4 3 2 1
  4. D1 2 4 5 3
7.Trudny

Czym drzewo radix (skompresowane trie) przewyższa zwykłe trie?

  1. AZachowuje tylko pierwszą literę każdego słowa
  2. BŁączy łańcuchy węzłów z jednym dzieckiem w jedną krawędź etykietowaną ciągiem znaków
  3. CSortuje dzieci każdego węzła według częstości
  4. DPrzechowuje każde słowo w tablicy mieszającej w korzeniu zamiast w osobnych węzłach
8.Trudny

Które operacje w O(log n) obsługuje drzewo Fenwicka (binary indexed tree) zbudowane nad tablicą n liczb?

  1. ASortowanie tablicy i wyszukiwanie binarne
  2. BZnajdowanie mediany w O(1)
  3. CWstawianie elementów na dowolnej pozycji
  4. DZapytania o sumy prefiksowe i aktualizacje pojedynczych elementów

Klucz odpowiedzi

  1. 1. A · Dequeue
  2. 2. A · Kolejki
  3. 3. C · Kopiec
  4. 4. D · Wysokość O(log n) dzięki równoważeniu
  5. 5. A · (i + 1) mod n
  6. 6. A · 4 5 2 3 1
  7. 7. B · Łączy łańcuchy węzłów z jednym dzieckiem w jedną krawędź etykietowaną ciągiem znaków
  8. 8. D · Zapytania o sumy prefiksowe i aktualizacje pojedynczych elementów

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