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. BKolejki
  3. CTablicy mieszającej
  4. DStosu
2.Łatwy

Co definiuje drzewo binarne?

  1. AKażdy węzeł przechowuje liczbę binarną
  2. BDrzewo ma dokładnie dwa poziomy
  3. CKażdy węzeł ma co najwyżej dwoje dzieci
  4. DKażdy węzeł ma dokładnie dwoje dzieci
3.Łatwy

Czym są węzły rodzeństwa (siblings) w drzewie?

  1. AWęzłami, które nie mają dzieci
  2. BWęzłami na tej samej głębokości w różnych poddrzewach
  3. CWęzłami, które mają tego samego rodzica
  4. DWęzłem i jego rodzicem
4.Średni

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

  1. AO(E²)
  2. BO(V²)
  3. CO(V + E)
  4. DO(V × E)
5.Średni

Jak znaleźć najmniejszy klucz w binarnym drzewie poszukiwań?

  1. AIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  2. BSprawdzić tylko korzeń
  3. COdwiedzić każdy liść i porównać je
  4. DIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
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 preorder?

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

Usunięcie węzła z dwojgiem dzieci z binarnego drzewa poszukiwań wykonuje się zwykle przez:

  1. AZbudowanie od nowa poddrzewa poniżej węzła i ponowne wstawienie wszystkich zawartych w nim kluczy
  2. BZamianę go z korzeniem
  3. CUsunięcie całego poddrzewa
  4. DZastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
8.Trudny

Którą własność musi spełniać drzewo czerwono-czarne?

  1. AKażdy węzeł musi być czerwony
  2. BKażdy czerwony węzeł musi mieć czerwone dzieci, więc czerwone węzły zawsze tworzą nieprzerwane łańcuchy aż do liści
  3. CKażda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów
  4. DKorzeń musi być czerwony

Klucz odpowiedzi

  1. 1. B · Kolejki
  2. 2. C · Każdy węzeł ma co najwyżej dwoje dzieci
  3. 3. C · Węzłami, które mają tego samego rodzica
  4. 4. C · O(V + E)
  5. 5. A · Iść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  6. 6. C · 1 2 4 5 3
  7. 7. D · Zastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
  8. 8. C · Każda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów

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