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

Co oznacza f(n) = Θ(g(n))?

  1. Af rośnie ściśle szybciej niż g
  2. Bf rośnie w tym samym tempie co g, ograniczona z góry i z dołu stałymi wielokrotnościami g
  3. Cf jest zawsze mniejsza niż g dla każdego n, więc g ogranicza ją od góry, lecz nigdy od dołu
  4. Df rośnie ściśle wolniej niż g
2.Łatwy

Czego wyszukiwanie binarne wymaga od danych wejściowych?

  1. ADługość tablicy musi być potęgą dwójki
  2. BTablica może mieć najwyżej 1000 elementów
  3. CTablica może zawierać tylko liczby dodatnie
  4. DTablica musi być posortowana
3.Łatwy

Co opisuje średni czas działania?

  1. ACzas dla danych o przeciętnej długości
  2. BOczekiwany czas przy danym rozkładzie danych wejściowych rozmiaru n
  3. CCzas na najpopularniejszym komputerze
  4. DWartość pośrodku między czasami działania w przypadku optymistycznym a pesymistycznym
4.Średni

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

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

Jaka jest złożoność czasowa mnożenia dwóch macierzy n × n standardową potrójną pętlą?

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

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

  1. AAlgorytm Kruskala
  2. BWe wszystkich przypadkach wymagany jest algorytm Bellmana–Forda
  3. CAlgorytm Dijkstry
  4. DPrzeszukiwanie w głąb (DFS)
7.Trudny

Co ustaliło twierdzenie Cooka–Levina?

  1. AKażdy problem NP można rozwiązać w czasie wykładniczym
  2. BP nie jest równe NP
  3. CProblem stopu jest nierozstrzygalny
  4. DProblem spełnialności formuł logicznych (SAT) jest NP-zupełny
8.Trudny

Dla którego wariantu problemu plecakowego reguła zachłanna „bierz przedmioty według wartości na jednostkę wagi" zawsze daje optymalną odpowiedź?

  1. AŻadnego z wariantów
  2. BDyskretnego problemu plecakowego 0/1, w którym przedmioty zawsze trzeba brać w całości
  3. CCiągłego (ułamkowego) problemu plecakowego, w którym przedmioty można dzielić
  4. DObu wariantów

Klucz odpowiedzi

  1. 1. B · f rośnie w tym samym tempie co g, ograniczona z góry i z dołu stałymi wielokrotnościami g
  2. 2. D · Tablica musi być posortowana
  3. 3. B · Oczekiwany czas przy danym rozkładzie danych wejściowych rozmiaru n
  4. 4. B · O(n²)
  5. 5. B · O(n³)
  6. 6. C · Algorytm Dijkstry
  7. 7. D · Problem spełnialności formuł logicznych (SAT) jest NP-zupełny
  8. 8. C · Ciągłego (ułamkowego) problemu plecakowego, w którym przedmioty można dzielić

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