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

Graf składa się z:

  1. AWierszy i kolumn
  2. BWierzchołków (węzłów) połączonych krawędziami
  3. CTylko korzenia i liści
  4. DWyłącznie kluczy i skrótów
2.Łatwy

Czym jest stopień wierzchołka w grafie nieskierowanym?

  1. ADługością najdłuższej ścieżki z niego wychodzącej
  2. BLiczbą wierzchołków w grafie
  3. CLiczbą krawędzi z nim połączonych
  4. DJego pozycją na liście sąsiedztwa
3.Łatwy

Czym jest graf skierowany?

  1. AGrafem bez cykli
  2. BGrafem, którego krawędzie mają kierunek od jednego wierzchołka do drugiego
  3. CGrafem, którego wszystkie krawędzie mają wagi
  4. DGrafem, w którym każda para różnych wierzchołków jest połączona krawędzią
4.Średni

Drzewa AVL i drzewa czerwono-czarne gwarantują:

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

Jaki jest koszt wstawienia elementu w środek tablicy o n elementach?

  1. AO(log n), z powodu wyszukiwania binarnego
  2. BO(n²), bo każdy element przesuwa się n razy
  3. CO(n), bo dalsze elementy trzeba przesunąć
  4. DO(1), bo indeks jest znany
6.Średni

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

  1. An (drzewo staje się listą wiązaną)
  2. B1
  3. C√n
  4. Dlog₂ n
7.Trudny

W buforze cyklicznym front == rear może oznaczać bufor pusty albo pełny. Jaki jest popularny sposób ich rozróżnienia?

  1. APrzechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji
  2. BUstawienie rozmiaru bufora na potęgę dwójki
  3. CCzyszczenie bufora za każdym razem, gdy front równa się rear, więc stan jest pusty
  4. DPrzechowywanie front i rear w tej samej zmiennej
8.Trudny

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

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

Klucz odpowiedzi

  1. 1. B · Wierzchołków (węzłów) połączonych krawędziami
  2. 2. C · Liczbą krawędzi z nim połączonych
  3. 3. B · Grafem, którego krawędzie mają kierunek od jednego wierzchołka do drugiego
  4. 4. C · Wysokość O(log n) dzięki równoważeniu
  5. 5. C · O(n), bo dalsze elementy trzeba przesunąć
  6. 6. A · n (drzewo staje się listą wiązaną)
  7. 7. A · Przechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji
  8. 8. C · Zastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła

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