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

Gdzie znajduje się najmniejszy element binarnego kopca minimalnego?

  1. ANa ostatniej pozycji tablicy
  2. BW skrajnie lewym liściu
  3. CW korzeniu
  4. DW którymś liściu, którego trzeba szukać
2.Łatwy

Jak elementy tablicy są przechowywane w pamięci?

  1. AW rozproszeniu, połączone wskaźnikami
  2. BW drzewie stron pamięci
  3. CW jednym ciągłym bloku, jeden po drugim
  4. DW losowych miejscach wybranych przez funkcję mieszającą
3.Łatwy

Czym jest cykl w grafie?

  1. AWierzchołkiem bez krawędzi
  2. BKrawędzią o wadze zero
  3. CŚcieżką, która zaczyna się i kończy w tym samym wierzchołku
  4. DŚcieżką, która odwiedza każdy wierzchołek
4.Średni

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

  1. Alog₂ n
  2. B1
  3. C√n
  4. Dn (drzewo staje się listą wiązaną)
5.Średni

Ile trwa wyszukiwanie słowa o długości L w drzewie trie ze stałym alfabetem?

  1. AO(L), niezależnie od liczby przechowywanych słów
  2. BO(log n), gdzie n to liczba słów
  3. CO(L × n)
  4. DO(n), gdzie n to liczba słów
6.Średni

Której struktury danych używa przeszukiwanie w głąb (DFS) w wersji iteracyjnej?

  1. AWyłącznie tablicy mieszającej
  2. BKopca
  3. CKolejki
  4. DStosu
7.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[3, 1, 8, 5]
  2. B[1, 3, 8, 5]
  3. C[1, 5, 8, 3]
  4. D[1, 3, 5, 8]
8.Trudny

Jaka jest główna zaleta listy z przeskokami (skip list) nad posortowaną listą wiązaną?

  1. AOczekiwane wyszukiwanie w O(log n) dzięki kilku poziomom wskaźników do przodu
  2. BPrzechowuje klucze bez uporządkowania
  3. CGwarantowane wyszukiwanie w O(1), bo każdy węzeł przechowuje wskaźnik do każdego innego węzła
  4. DNie zużywa dodatkowej pamięci

Klucz odpowiedzi

  1. 1. C · W korzeniu
  2. 2. C · W jednym ciągłym bloku, jeden po drugim
  3. 3. C · Ścieżką, która zaczyna się i kończy w tym samym wierzchołku
  4. 4. D · n (drzewo staje się listą wiązaną)
  5. 5. A · O(L), niezależnie od liczby przechowywanych słów
  6. 6. D · Stosu
  7. 7. B · [1, 3, 8, 5]
  8. 8. A · Oczekiwane wyszukiwanie w O(log n) dzięki kilku poziomom wskaźników do przodu

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