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 małe omega
  4. DNotacja duże Omega
2.Łatwy

Ile wynosi duże O wyrażenia 3n² + 5n + 2?

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

Jak nazywa się wzrost O(2ⁿ)?

  1. ALogarytmiczny
  2. BWykładniczy
  3. CWielomianowy
  4. DLiniowy
4.Średni

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

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

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

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

Co oznacza, że problem ma optymalną podstrukturę?

  1. AKażdy podproblem ma ten sam rozmiar
  2. BProblem można rozwiązać w czasie stałym
  3. CProblem ma dokładnie jedno rozwiązanie optymalne, wspólne dla wszystkich podproblemów
  4. DOptymalne rozwiązanie można zbudować z optymalnych rozwiązań jego podproblemów
7.Trudny

Algorytm Strassena mnoży macierze, używając 7 zamiast 8 rekurencyjnych mnożeń bloków o połowie rozmiaru. Jaki jest jego czas działania?

  1. AΘ(n³)
  2. BΘ(nlog₂ 7), około n2,81
  3. CΘ(n² log n)
  4. DΘ(n2)
8.Trudny

Jaki jest czas działania algorytmu Dijkstry z kopcem binarnym dla grafu o V wierzchołkach i E krawędziach?

  1. AO(V + E)
  2. BO((V + E) log V)
  3. CO(V³)
  4. DO(V × E)

Klucz odpowiedzi

  1. 1. B · Notacja duże O
  2. 2. C · O(n²)
  3. 3. B · Wykładniczy
  4. 4. A · O(n²)
  5. 5. D · Wywołuje samą siebie, aż przepełni się stos wywołań
  6. 6. D · Optymalne rozwiązanie można zbudować z optymalnych rozwiązań jego podproblemów
  7. 7. B · Θ(nlog₂ 7), około n2,81
  8. 8. B · O((V + E) log V)

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