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

Czym jest cykl w grafie?

  1. AKrawędzią o wadze zero
  2. BWierzchołkiem bez krawędzi
  3. CŚcieżką, która zaczyna się i kończy w tym samym wierzchołku
  4. DŚcieżką, która odwiedza każdy wierzchołek
2.Łatwy

Której struktury danych używa się do przejścia drzewa poziomami (level-order)?

  1. AStosu
  2. BKolejki
  3. CTablicy mieszającej
  4. DKolejki priorytetowej
3.Łatwy

Ile krawędzi ma drzewo o n węzłach?

  1. A2n
  2. Bn − 1
  3. Cn + 1
  4. Dn
4.Średni

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

  1. ANie ma maksimum
  2. B1
  3. C0,5
  4. D2
5.Ś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²)
6.Średni

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

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

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

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

Jak wykryć, czy lista jednokierunkowa zawiera cykl, używając O(1) dodatkowej pamięci?

  1. APrzesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
  2. BPosortować listę i szukać duplikatów
  3. CLiczyć węzły, aż liczba przekroczy pole z długością listy
  4. DZapisywać każdy odwiedzony węzeł w zbiorze mieszającym

Klucz odpowiedzi

  1. 1. C · Ścieżką, która zaczyna się i kończy w tym samym wierzchołku
  2. 2. B · Kolejki
  3. 3. B · n − 1
  4. 4. B · 1
  5. 5. A · O(V + E)
  6. 6. B · O(log n)
  7. 7. A · Do sprawdzania, czy oba końce krawędzi są już połączone
  8. 8. A · Przesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają

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