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. B10
  3. C12
  4. D512
2.Łatwy

Która notacja opisuje górne ograniczenie tempa wzrostu?

  1. ANotacja duże Theta
  2. BNotacja duże O
  3. CNotacja duże Omega
  4. DNotacja małe omega
3.Łatwy

Jaka jest pesymistyczna złożoność czasowa sortowania przez scalanie?

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

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

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

Jaka jest złożoność czasowa: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Jaka jest pesymistyczna złożoność czasowa sortowania szybkiego (quicksort)?

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

Która definicja klasy P jest poprawna?

  1. AProblemy, których rozwiązania można sprawdzić, ale nigdy nie znaleźć w czasie wielomianowym
  2. BProblemy decyzyjne rozwiązywalne przez algorytm deterministyczny w czasie wielomianowym
  3. CProblemy, które można rozwiązać równolegle
  4. DProblemy wymagające czasu wykładniczego na każdym komputerze
8.Trudny

Sortowanie przez wstawianie działa w O(n) dla danych posortowanych. Czy to przeczy dolnemu ograniczeniu Ω(n log n) dla sortowania przez porównania?

  1. ATak, ale tylko dla tablic krótszych niż 100
  2. BNie, dolne ograniczenie dotyczy najgorszego przypadku po wszystkich danych, a nie każdych danych
  3. CTak, więc dolne ograniczenie jest błędne
  4. DNie, bo sortowanie przez wstawianie nie jest sortowaniem przez porównania

Klucz odpowiedzi

  1. 1. B · 10
  2. 2. B · Notacja duże O
  3. 3. B · O(n log n)
  4. 4. A · O(log n)
  5. 5. B · O(n log n)
  6. 6. A · O(n²)
  7. 7. B · Problemy decyzyjne rozwiązywalne przez algorytm deterministyczny w czasie wielomianowym
  8. 8. B · Nie, dolne ograniczenie dotyczy najgorszego przypadku po wszystkich danych, a nie każdych danych

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