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

Problem zwykle nazywa się praktycznie rozwiązywalnym (tractable), jeśli:

  1. ADa się go rozwiązać w czasie stałym
  2. BDa się go rozwiązać w czasie wielomianowym
  3. CNie ma rozwiązania
  4. DDa się go rozwiązać tylko przez sprawdzenie wszystkich możliwości
2.Łatwy

Która z tych funkcji rośnie najwolniej, gdy n staje się duże?

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

Który z tych czasów działania jest wielomianowy?

  1. AO(nⁿ)
  2. BO(2ⁿ)
  3. CO(n!)
  4. DO(n³)
4.Średni

Jaka jest złożoność czasowa: for i = 1 to n: for j = 1 to i: wykonaj pracę O(1)?

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

Ile poziomów ma rekurencja sortowania przez scalanie dla tablicy n elementów?

  1. AOkoło log₂ n
  2. BOkoło n
  3. COkoło √n
  4. DOkoło n / 2
6.Średni

Przeszukiwanie wszerz w grafie nieważonym znajduje:

  1. AMinimalne drzewo rozpinające
  2. BPorządek topologiczny w dowolnym grafie
  3. CNajkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego
  4. DNajkrótsze ścieżki w grafach zawierających ujemne wagi krawędzi
7.Trudny

Jaki jest koszt czasowy i pamięciowy obliczania n-tej liczby Fibonacciego pętlą, która przechowuje tylko dwie ostatnie wartości?

  1. ACzas O(log n) i pamięć O(n)
  2. BCzas O(n) i pamięć O(1)
  3. CCzas O(2ⁿ) i pamięć O(1)
  4. DCzas O(n) i pamięć O(n)
8.Trudny

Jaka jest złożoność czasowa: for i = 1 to n: for (j = i; j ≤ n; j = j + i) wykonaj pracę O(1)?

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

Klucz odpowiedzi

  1. 1. B · Da się go rozwiązać w czasie wielomianowym
  2. 2. B · O(log n)
  3. 3. D · O(n³)
  4. 4. A · O(n²)
  5. 5. A · Około log₂ n
  6. 6. C · Najkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego
  7. 7. B · Czas O(n) i pamięć O(1)
  8. 8. D · O(n log n)

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