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

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
2.Łatwy

Co opisuje pesymistyczny czas działania algorytmu?

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

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

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

Które stwierdzenie o funkcji rekurencyjnej bez osiągalnego przypadku bazowego jest poprawne?

  1. AKompilator zawsze zamienia ją na pętlę, która kończy się bezpiecznie
  2. BDziała w czasie O(1)
  3. CWywołuje samą siebie, aż przepełni się stos wywołań
  4. DAutomatycznie zwraca 0
5.Średni

Który algorytm znajduje najkrótsze ścieżki z jednego źródła w grafie o nieujemnych wagach krawędzi?

  1. APrzeszukiwanie w głąb (DFS)
  2. BAlgorytm Kruskala
  3. CWe wszystkich przypadkach wymagany jest algorytm Bellmana–Forda
  4. DAlgorytm Dijkstry
6.Średni

Złożoność czasowa naiwnego rekurencyjnego obliczania ciągu Fibonacciego (fib(n) = fib(n−1) + fib(n−2)) jest:

  1. ALiniowa
  2. BStała
  3. CWykładnicza
  4. DLogarytmiczna
7.Trudny

Jakie dwie rzeczy trzeba wykazać, aby udowodnić, że problem decyzyjny X jest NP-zupełny?

  1. AX należy do NP, a znany problem NP-zupełny redukuje się do X w czasie wielomianowym
  2. BX nie ma algorytmu wielomianowego, a X jest rozstrzygalny
  3. CX redukuje się do problemu z P, a X należy do NP
  4. DX należy do P, a X redukuje się do SAT
8.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(2ⁿ) i pamięć O(1)
  2. BCzas O(log n) i pamięć O(n)
  3. CCzas O(n) i pamięć O(n)
  4. DCzas O(n) i pamięć O(1)

Klucz odpowiedzi

  1. 1. B · Notacja duże O
  2. 2. B · Maksymalny czas po wszystkich danych wejściowych rozmiaru n
  3. 3. C · O(n³)
  4. 4. C · Wywołuje samą siebie, aż przepełni się stos wywołań
  5. 5. D · Algorytm Dijkstry
  6. 6. C · Wykładnicza
  7. 7. A · X należy do NP, a znany problem NP-zupełny redukuje się do X w czasie wielomianowym
  8. 8. D · Czas O(n) i pamięć O(1)

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