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

Czym jest rekurencja?

  1. APętlą, która nigdy się nie kończy
  2. BFunkcją wywołującą samą siebie dla mniejszych danych wejściowych
  3. CMetodą sortowania
  4. DRodzajem struktury danych
2.Ł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 log₂ n
  2. BOkoło n / 2
  3. COkoło n
  4. DOkoło n²
3.Łatwy

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

  1. AO(n)
  2. BO(1)
  3. CO(n²)
  4. DO(n log n)
4.Ś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 2
  2. BZachłanna używa 4 monet; optimum to 3
  3. CZachłanna używa 2 monet; optimum to 2
  4. DZachłanna używa 3 monet; optimum to 3
5.Średni

W posortowanej tablicy szukasz dwóch elementów o sumie równej celowi, przesuwając po jednym wskaźniku z każdego końca do środka. Jaka jest złożoność czasowa?

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

Programowanie dynamiczne jest przydatne, gdy problem ma:

  1. ANakładające się podproblemy i optymalną podstrukturę
  2. BWyłącznie losowe dane wejściowe
  3. CŻadnych podproblemów, więc można go rozwiązać w jednym kroku
  4. DPojedynczą pętlę
7.Trudny

Które ograniczenie jest poprawne dla log(n!)?

  1. AΘ(log n)
  2. BΘ(n²)
  3. CΘ(n)
  4. DΘ(n log n)
8.Trudny

Jak algorytm Bellmana–Forda wykrywa cykl o ujemnej wadze osiągalny ze źródła?

  1. ASprawdza, czy któraś krawędź ma ujemną wagę
  2. BZlicza cykle za pomocą przeszukiwania w głąb
  3. CPo V − 1 rundach sprawdza, czy którąś krawędź można jeszcze zrelaksować
  4. DUruchamia dwukrotnie algorytm Dijkstry i porównuje oba wyniki odległości

Klucz odpowiedzi

  1. 1. B · Funkcją wywołującą samą siebie dla mniejszych danych wejściowych
  2. 2. A · Około log₂ n
  3. 3. A · O(n)
  4. 4. A · Zachłanna używa 3 monet; optimum to 2
  5. 5. B · O(n)
  6. 6. A · Nakładające się podproblemy i optymalną podstrukturę
  7. 7. D · Θ(n log n)
  8. 8. C · Po V − 1 rundach sprawdza, czy którąś krawędź można jeszcze zrelaksować

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