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óry z tych czasów działania jest wielomianowy?

  1. AO(nⁿ)
  2. BO(n³)
  3. CO(2ⁿ)
  4. DO(n!)
2.Łatwy

Co opisuje pesymistyczny czas działania algorytmu?

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

Pętla zaczyna od i = 1 i w każdej iteracji podwaja i, aż do chwili, gdy i > n. Ile iteracji wykona?

  1. AOkoło n / 2
  2. BOkoło log₂ n
  3. COkoło n
  4. DOkoło n²
4.Średni

Rozwiązaniem rekurencji T(n) = 2T(n/2) + O(n) jest:

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

Która reguła zachłanna w problemie wyboru zajęć zawsze daje maksymalną liczbę nienakładających się zajęć?

  1. AWybierz najpierw najkrótsze zajęcie
  2. BWybierz zajęcie, które zaczyna się najwcześniej
  3. CWybierz najpierw zajęcie z najmniejszą liczbą kolizji, a potem powtarzaj dla zgodnych zajęć
  4. DWybierz zajęcie, które kończy się najwcześniej, i powtórz dla zgodnych z nim
6.Średni

Przy monetach 1, 3 i 4 oraz kwocie 6, ile monet używa zachłanna metoda „najpierw największa moneta" w porównaniu z optimum?

  1. AZachłanna używa 3 monet; optimum to 3
  2. BZachłanna używa 3 monet; optimum to 2
  3. CZachłanna używa 2 monet; optimum to 2
  4. DZachłanna używa 4 monet; optimum to 3
7.Trudny

Co trzeba zrobić, aby wykazać, że nowy problem X jest NP-trudny?

  1. AZredukować znany problem NP-trudny do X w czasie wielomianowym
  2. BZredukować X do znanego problemu NP-trudnego w czasie wielomianowym
  3. CWykazać, że X nie ma algorytmu wielomianowego dla małych danych
  4. DWykazać, że X można zweryfikować w czasie wielomianowym
8.Trudny

Dlaczego każde wyszukiwanie oparte na porównaniach w posortowanej tablicy wymaga w najgorszym przypadku Ω(log n) porównań?

  1. ADrzewo decyzyjne z n możliwymi wynikami musi mieć głębokość co najmniej log₂ n
  2. BKażdy element musi być porównany co najmniej raz
  3. CKażde porównanie zajmuje czas logarytmiczny
  4. DWyszukiwanie binarne jest jedynym możliwym algorytmem i wymaga log₂ n porównań

Klucz odpowiedzi

  1. 1. B · O(n³)
  2. 2. C · Maksymalny czas po wszystkich danych wejściowych rozmiaru n
  3. 3. B · Około log₂ n
  4. 4. D · O(n log n)
  5. 5. D · Wybierz zajęcie, które kończy się najwcześniej, i powtórz dla zgodnych z nim
  6. 6. B · Zachłanna używa 3 monet; optimum to 2
  7. 7. A · Zredukować znany problem NP-trudny do X w czasie wielomianowym
  8. 8. A · Drzewo decyzyjne z n możliwymi wynikami musi mieć głębokość co najmniej log₂ n

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