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 dodatkowej pamięci używa standardowe sortowanie przez scalanie oparte na tablicach?

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

Czym jest algorytm?

  1. AJęzykiem programowania przeznaczonym do zapisu wzorów matematycznych
  2. BStrukturą danych przechowującą liczby
  3. CSkończonym ciągiem dobrze określonych kroków rozwiązującym problem
  4. DDowolnym programem z interfejsem graficznym
3.Łatwy

Jaka jest optymistyczna złożoność czasowa sortowania przez wstawianie dla już posortowanej tablicy?

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

Sortujesz raz tablicę n elementów, a potem odpowiadasz na k zapytań o przynależność za pomocą wyszukiwania binarnego. Jaki jest łączny koszt?

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

Dlaczego programowanie dynamiczne nie daje realnego przyspieszenia sortowania przez scalanie?

  1. AJego podproblemy się nie nakładają, więc nie ma czego ponownie wykorzystać
  2. BSortowanie przez scalanie już jest O(n)
  3. CProgramowanie dynamiczne działa tylko na problemach grafowych, a nie na tablicach
  4. DSortowanie przez scalanie nie ma struktury rekurencyjnej
6.Średni

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

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(log n)
7.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)
8.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Θ(n2)
  2. BΘ(n³)
  3. CΘ(n² log n)
  4. DΘ(nlog₂ 7), około n2,81

Klucz odpowiedzi

  1. 1. A · O(n)
  2. 2. C · Skończonym ciągiem dobrze określonych kroków rozwiązującym problem
  3. 3. D · O(n)
  4. 4. C · O(n log n + k log n)
  5. 5. A · Jego podproblemy się nie nakładają, więc nie ma czego ponownie wykorzystać
  6. 6. C · O(n²)
  7. 7. A · Θ(n log² n)
  8. 8. D · Θ(nlog₂ 7), około n2,81

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