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

Wysokość drzewa definiuje się zwykle jako:

  1. ALiczbę liści w drzewie
  2. BLiczbę krawędzi na najdłuższej ścieżce od korzenia do liścia
  3. CLiczbę dzieci korzenia
  4. DŁączną liczbę węzłów w drzewie, wliczając korzeń i każdy liść
2.Łatwy

Czym jest liść w drzewie?

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

Co robi operacja peek (lub top) na stosie?

  1. AUsuwa wszystkie elementy ze stosu
  2. BUsuwa element z wierzchołka i go zwraca
  3. CZwraca element z wierzchołka bez usuwania go
  4. DZwraca element z dna stosu
4.Średni

Którego abstrakcyjnego typu danych używa algorytm Dijkstry do wyboru następnego wierzchołka do przetworzenia?

  1. AZbioru bez uporządkowania
  2. BStosu
  3. CKolejki FIFO
  4. DKolejki priorytetowej typu min
5.Średni

Jaki jest maksymalny możliwy współczynnik zapełnienia tablicy mieszającej z adresowaniem otwartym?

  1. A1
  2. B2
  3. C0,5
  4. DNie ma maksimum
6.Średni

Co jest prawdą o macierzy sąsiedztwa grafu nieskierowanego?

  1. ANa jej głównej przekątnej zawsze są jedynki
  2. BJest symetryczna względem głównej przekątnej
  3. CKażdy wiersz ma dokładnie jedną jedynkę
  4. DJest zawsze górnotrójkątna
7.Trudny

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

  1. AWysokość wynosi co najwyżej n / 2
  2. BWysokość wynosi dokładnie log2 n
  3. CWysokość wynosi co najwyżej 2 log2(n + 1)
  4. DWysokość wynosi co najwyżej log2 n + 1
8.Trudny

Do czego służy struktura union-find w algorytmie Kruskala wyznaczania minimalnego drzewa rozpinającego?

  1. ADo przechowywania bieżącej odległości każdego wierzchołka od źródła w trakcie przeszukiwania
  2. BDo sortowania krawędzi według wag
  3. CDo wyboru wierzchołka początkowego
  4. DDo sprawdzania, czy oba końce krawędzi są już połączone

Klucz odpowiedzi

  1. 1. B · Liczbę krawędzi na najdłuższej ścieżce od korzenia do liścia
  2. 2. A · Węzłem bez dzieci
  3. 3. C · Zwraca element z wierzchołka bez usuwania go
  4. 4. D · Kolejki priorytetowej typu min
  5. 5. A · 1
  6. 6. B · Jest symetryczna względem głównej przekątnej
  7. 7. C · Wysokość wynosi co najwyżej 2 log2(n + 1)
  8. 8. D · Do sprawdzania, czy oba końce krawędzi są już połączone

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