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 graf ważony?

  1. AGrafem, w którym niektóre wierzchołki są cięższe od innych, bo mają więcej krawędzi
  2. BGrafem, który ma więcej krawędzi niż wierzchołków
  3. CGrafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
  4. DGrafem przechowywanym na dysku
2.Łatwy

Graf składa się z:

  1. AWyłącznie kluczy i skrótów
  2. BTylko korzenia i liści
  3. CWierszy i kolumn
  4. DWierzchołków (węzłów) połączonych krawędziami
3.Ł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. CListę jego sąsiednich wierzchołków
  4. DNajkrótszą ścieżkę do każdego innego wierzchołka
4.Ś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. CJest zawsze górnotrójkątna
  4. DKażdy wiersz ma dokładnie jedną jedynkę
5.Średni

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

  1. AKolejki FIFO
  2. BStosu
  3. CKolejki priorytetowej typu min
  4. DZbioru bez uporządkowania
6.Ś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)
7.Trudny

Złożoność czasowa operacji decrease-key w kopcu binarnym (przy znanej pozycji elementu) wynosi:

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

Obiekt jest przechowywany jako klucz w mapie mieszającej, a następnie zmienia się pole używane przez jego funkcję mieszającą. Jaki jest prawdopodobny skutek?

  1. AWyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu
  2. BMapa zgłasza błąd w chwili zmiany pola
  3. CMapa automatycznie przenosi klucz do nowego kubełka
  4. DNic się nie zmienia, bo skrót klucza oblicza się tylko raz przy uruchomieniu programu

Klucz odpowiedzi

  1. 1. C · Grafem, w którym każda krawędź ma wartość liczbową, np. koszt lub odległość
  2. 2. D · Wierzchołków (węzłów) połączonych krawędziami
  3. 3. C · Listę jego sąsiednich wierzchołków
  4. 4. B · Jest symetryczna względem głównej przekątnej
  5. 5. C · Kolejki priorytetowej typu min
  6. 6. C · O(V + E)
  7. 7. A · O(log n)
  8. 8. A · Wyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu

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