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

Na czym polega własność kopca maksymalnego (max-heap)?

  1. AWszystkie liście zawierają klucz maksymalny
  2. BKlucz każdego lewego dziecka jest większy lub równy kluczowi jego prawego rodzeństwa
  3. CKlucz każdego rodzica jest większy lub równy kluczom jego dzieci
  4. DKlucze są posortowane od lewej do prawej
2.Łatwy

Która struktura danych działa według zasady „ostatni na wejściu, pierwszy na wyjściu” (LIFO)?

  1. ALista wiązana
  2. BKolejka
  3. CStos
  4. DTablica mieszająca
3.Łatwy

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

  1. AOdczyt ostatniego elementu po indeksie
  2. BWstawianie na początku
  3. CDostęp do 5. elementu
  4. DUstalenie długości tablicy o stałym rozmiarze
4.Średni

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

  1. AO(V × E)
  2. BO(V + E)
  3. CO(V²)
  4. DO(E²)
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. Bn (drzewo staje się listą wiązaną)
  3. Clog₂ n
  4. D1
6.Średni

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

  1. AKopca
  2. BKolejki
  3. CStosu
  4. DWyłącznie tablicy mieszającej
7.Trudny

Jaką gwarancję co do wysokości drzewa z n kluczami dają reguły drzewa czerwono-czarnego?

  1. AWysokość wynosi co najwyżej 2 log2(n + 1)
  2. BWysokość wynosi co najwyżej n / 2
  3. CWysokość wynosi co najwyżej log2 n + 1
  4. DWysokość wynosi dokładnie log2 n
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, 5, 8]
  2. B[1, 3, 8, 5]
  3. C[3, 1, 8, 5]
  4. D[1, 5, 8, 3]

Klucz odpowiedzi

  1. 1. C · Klucz każdego rodzica jest większy lub równy kluczom jego dzieci
  2. 2. C · Stos
  3. 3. B · Wstawianie na początku
  4. 4. B · O(V + E)
  5. 5. B · n (drzewo staje się listą wiązaną)
  6. 6. C · Stosu
  7. 7. A · Wysokość wynosi co najwyżej 2 log2(n + 1)
  8. 8. B · [1, 3, 8, 5]

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