Algorytmy i złożoność: karta pracy z odpowiedziami

Darmowa karta pracy do druku – Algorytmy i złożoność: 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

Ile wynosi log₂ 1024?

  1. A32
  2. B512
  3. C12
  4. D10
2.Łatwy

Ile wynosi duże O wyrażenia 3n² + 5n + 2?

  1. AO(3n²)
  2. BO(n²)
  3. CO(5n)
  4. DO(n³)
3.Łatwy

Dostęp do elementu tablicy po indeksie zajmuje:

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

Jakie jest rozwiązanie rekurencji T(n) = T(n − 1) + O(1)?

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

Jaka jest złożoność czasowa obliczania n-tej liczby Fibonacciego za pomocą tablicy wypełnianej wstępująco (bottom-up)?

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

Ile pamięci stosu zużywa prosta rekurencyjna funkcja silni fact(n) = n × fact(n − 1)?

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

Jaki jest czas działania algorytmu Dijkstry z kopcem binarnym dla grafu o V wierzchołkach i E krawędziach?

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

Dlaczego algorytm Dijkstry może dawać błędne wyniki, gdy niektóre wagi krawędzi są ujemne?

  1. ADziała tylko na grafach nieskierowanych
  2. BWierzchołek jest zatwierdzany przy pobraniu, a późniejsza ujemna krawędź mogłaby jeszcze dać mu krótszą ścieżkę
  3. CLiczb ujemnych nie można przechowywać w kolejce priorytetowej
  4. DNa każdej ujemnej krawędzi wpada w nieskończoną pętlę

Klucz odpowiedzi

  1. 1. D · 10
  2. 2. B · O(n²)
  3. 3. C · O(1)
  4. 4. C · O(n)
  5. 5. D · O(n)
  6. 6. B · O(n)
  7. 7. A · O((V + E) log V)
  8. 8. B · Wierzchołek jest zatwierdzany przy pobraniu, a późniejsza ujemna krawędź mogłaby jeszcze dać mu krótszą ścieżkę

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