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

Co opisuje pesymistyczny czas działania algorytmu?

  1. AMaksymalny czas po wszystkich danych wejściowych rozmiaru n
  2. BOczekiwany czas dla losowych danych wejściowych o rozmiarze n
  3. CCzas dla najmniejszych danych wejściowych
  4. DCzas na wolnym komputerze
2.Łatwy

Czym jest algorytm siłowy (brute force)?

  1. AAlgorytmem działającym na wielu procesorach
  2. BAlgorytmem, który zawsze używa rekurencji
  3. CAlgorytmem, który sprawdza wszystkie możliwe rozwiązania kandydujące
  4. DAlgorytmem, który losowo zgaduje odpowiedź
3.Łatwy

Jaką strategię projektowania stosuje sortowanie przez scalanie?

  1. AWybór zachłanny
  2. BProgramowanie dynamiczne
  3. CDziel i zwyciężaj
  4. DSiłę brutalną (przegląd zupełny)
4.Średni

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

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

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

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

Ile mniej więcej porównań potrzebuje wyszukiwanie binarne w najgorszym przypadku w posortowanej tablicy 1,000,000 elementów?

  1. AOkoło 100
  2. BOkoło 20
  3. COkoło 1,000
  4. DOkoło 500,000
7.Trudny

Algorytm programowania dynamicznego Helda–Karpa rozwiązuje dokładnie problem komiwojażera. Jaki jest jego czas działania dla n miast?

  1. AO(n³)
  2. BO(n² 2ⁿ)
  3. CO(2n²)
  4. DO(n!)
8.Trudny

Która definicja klasy NP jest poprawna?

  1. AProblemy, które nie są wielomianowe
  2. BProblemy, których nie rozwiązuje żaden algorytm
  3. CProblemy decyzyjne, których odpowiedzi „tak" można zweryfikować w czasie wielomianowym na podstawie certyfikatu
  4. DProblemy, których nie da się rozwiązać w czasie wielomianowym

Klucz odpowiedzi

  1. 1. A · Maksymalny czas po wszystkich danych wejściowych rozmiaru n
  2. 2. C · Algorytmem, który sprawdza wszystkie możliwe rozwiązania kandydujące
  3. 3. C · Dziel i zwyciężaj
  4. 4. D · O(n)
  5. 5. B · O(n²)
  6. 6. B · Około 20
  7. 7. B · O(n² 2ⁿ)
  8. 8. C · Problemy decyzyjne, których odpowiedzi „tak" można zweryfikować w czasie wielomianowym na podstawie certyfikatu

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