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

Jaką złożoność ma zwykle algorytm z dwiema zagnieżdżonymi pętlami, z których każda wykonuje się n razy?

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

Czym jest rekurencja?

  1. AMetodą sortowania
  2. BPętlą, która nigdy się nie kończy
  3. CFunkcją wywołującą samą siebie dla mniejszych danych wejściowych
  4. DRodzajem struktury danych
3.Łatwy

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

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

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

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

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

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

Jaka jest zamortyzowana złożoność czasowa dodawania elementu na koniec tablicy dynamicznej, która podwaja swoją pojemność, gdy się zapełni?

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

Które stwierdzenie dotyczące P i NP jest prawdziwe?

  1. AKażdy problem z klasy P należy również do NP
  2. BNP oznacza „niewielomianowy” (not polynomial)
  3. CRozwiązań problemów NP nie da się szybko zweryfikować
  4. DUdowodniono, że P ≠ NP
8.Trudny

Jakie jest rozwiązanie rekurencji T(n) = 2T(n/2) + n log n?

  1. AΘ(n log² n)
  2. BΘ(n²)
  3. CΘ(n log n)
  4. DΘ(n)

Klucz odpowiedzi

  1. 1. A · O(n²)
  2. 2. C · Funkcją wywołującą samą siebie dla mniejszych danych wejściowych
  3. 3. A · O(log n)
  4. 4. D · O(log n)
  5. 5. C · Około log₂ n
  6. 6. C · O(1)
  7. 7. A · Każdy problem z klasy P należy również do NP
  8. 8. A · Θ(n log² n)

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