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

Co przechowuje się dla każdego wierzchołka w reprezentacji grafu za pomocą list sąsiedztwa?

  1. AWiersz V wartości logicznych
  2. BŁączną liczbę krawędzi w grafie
  3. CNajkrótszą ścieżkę do każdego innego wierzchołka
  4. DListę jego sąsiednich wierzchołków
2.Ł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łem i jego rodzicem
  4. DWęzłami, które mają tego samego rodzica
3.Łatwy

Jaka jest główna różnica między tablicą statyczną a tablicą dynamiczną?

  1. ATablica statyczna ma wolniejszy dostęp po indeksie
  2. BTablica statyczna może przechowywać tylko liczby
  3. CTablica dynamiczna przechowuje elementy w połączonych węzłach, by mogła rosnąć po jednym elemencie
  4. DTablica dynamiczna może rosnąć, przenosząc się do większego bloku pamięci
4.Średni

Kolejkę zaimplementowano za pomocą dwóch stosów: push na stos „in”, a pop ze stosu „out”, który, gdy jest pusty, uzupełnia się ze stosu „in”. Jaki jest zamortyzowany koszt jednej operacji?

  1. AO(log n)
  2. BO(1)
  3. CO(n²)
  4. DO(n)
5.Średni

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

  1. ASprawdzić tylko korzeń
  2. BOdwiedzić każdy liść i porównać je
  3. CIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
  4. DIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
6.Średni

Jaka jest złożoność czasowa wyszukiwania klucza w zrównoważonym binarnym drzewie poszukiwań?

  1. AO(log n)
  2. BO(n log n)
  3. CO(1)
  4. DO(n)
7.Trudny

Jaki jest czas działania przeszukiwania wszerz (BFS) w grafie o V wierzchołkach przechowywanym jako macierz sąsiedztwa?

  1. AO(V²)
  2. BO(E log V)
  3. CO(V)
  4. DO(V + E)
8.Trudny

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

  1. AUstawienie rozmiaru bufora na potęgę dwójki
  2. BPrzechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji
  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

Klucz odpowiedzi

  1. 1. D · Listę jego sąsiednich wierzchołków
  2. 2. D · Węzłami, które mają tego samego rodzica
  3. 3. D · Tablica dynamiczna może rosnąć, przenosząc się do większego bloku pamięci
  4. 4. B · O(1)
  5. 5. D · Iść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  6. 6. A · O(log n)
  7. 7. A · O(V²)
  8. 8. B · Przechowywanie osobnego licznika elementów albo pozostawianie zawsze jednej wolnej pozycji

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