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órej struktury danych używa się do przejścia drzewa poziomami (level-order)?

  1. AKolejki priorytetowej
  2. BTablicy mieszającej
  3. CKolejki
  4. DStosu
2.Łatwy

Ile krawędzi ma drzewo o n węzłach?

  1. An − 1
  2. B2n
  3. Cn + 1
  4. Dn
3.Łatwy

Czym jest liść w drzewie?

  1. AWęzłem bez rodzica
  2. BWęzłem o największej wartości
  3. CWęzłem z dokładnie jednym dzieckiem
  4. DWęzłem bez dzieci
4.Średni

Sieć drogowa ma 100 000 skrzyżowań, z których każde łączy się z około 4 innymi. Która reprezentacja jest najodpowiedniejsza?

  1. AListy sąsiedztwa
  2. BMacierz sąsiedztwa
  3. CJedna posortowana tablica wierzchołków
  4. DKopiec binarny krawędzi
5.Średni

Jaka jest pesymistyczna wysokość binarnego drzewa poszukiwań z n węzłami, jeśli klucze są wstawiane w kolejności posortowanej?

  1. A√n
  2. B1
  3. Cn (drzewo staje się listą wiązaną)
  4. Dlog₂ n
6.Średni

Drzewo trie (drzewo prefiksowe) jest szczególnie wydajne przy:

  1. APrzechowywaniu macierzy
  2. BZnajdowaniu najkrótszych ścieżek
  3. CSortowaniu liczb
  4. DWyszukiwaniu po prefiksie, np. autouzupełnianiu
7.Trudny

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

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

Klucze 5, 3, 8, 1 wstawia się w tej kolejności do pustego binarnego kopca minimalnego opartego na tablicy. Jak wygląda końcowa tablica?

  1. A[1, 3, 8, 5]
  2. B[3, 1, 8, 5]
  3. C[1, 5, 8, 3]
  4. D[1, 3, 5, 8]

Klucz odpowiedzi

  1. 1. C · Kolejki
  2. 2. A · n − 1
  3. 3. D · Węzłem bez dzieci
  4. 4. A · Listy sąsiedztwa
  5. 5. C · n (drzewo staje się listą wiązaną)
  6. 6. D · Wyszukiwaniu po prefiksie, np. autouzupełnianiu
  7. 7. C · Łączy łańcuchy węzłów z jednym dzieckiem w jedną krawędź etykietowaną ciągiem znaków
  8. 8. A · [1, 3, 8, 5]

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