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

Jaka jest złożoność czasowa znalezienia największej wartości w nieposortowanej tablicy n liczb?

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

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

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

Jaka jest złożoność czasowa przeszukiwania w głąb grafu zapisanego jako listy sąsiedztwa?

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

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

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

Jak algorytm Prima buduje minimalne drzewo rozpinające?

  1. AUsuwa najdroższą krawędź, dopóki nie znikną cykle
  2. BUruchamia przeszukiwanie wszerz i zachowuje drzewo BFS
  3. CRozrasta jedno drzewo od wierzchołka startowego, dodając najtańszą krawędź wychodzącą z drzewa
  4. DSortuje wszystkie krawędzie według wagi i dodaje każdą, o ile nie utworzy cyklu w lesie
6.Średni

Co mierzy analiza zamortyzowana?

  1. AOczekiwany koszt dla losowych danych wejściowych
  2. BKoszt algorytmu dla najlepszych danych
  3. CKoszt pojedynczej najdroższej operacji w dowolnym miejscu ciągu
  4. DŚredni koszt na operację w pesymistycznym ciągu operacji
7.Trudny

Czy 22n należy do O(2ⁿ)?

  1. ATak, bo obie funkcje są wykładnicze
  2. BNie, bo 22n rośnie wolniej niż 2ⁿ
  3. CNie, bo 22n = 4ⁿ, a 4ⁿ / 2ⁿ = 2ⁿ rośnie nieograniczenie
  4. DTak, bo stałe czynniki w wykładniku zawsze się pomija w notacji dużego O
8.Trudny

Która definicja klasy P jest poprawna?

  1. AProblemy decyzyjne rozwiązywalne przez algorytm deterministyczny w czasie wielomianowym
  2. BProblemy, których rozwiązania można sprawdzić, ale nigdy nie znaleźć w czasie wielomianowym
  3. CProblemy wymagające czasu wykładniczego na każdym komputerze
  4. DProblemy, które można rozwiązać równolegle

Klucz odpowiedzi

  1. 1. D · O(n)
  2. 2. A · f rośnie w tym samym tempie co g, ograniczona z góry i z dołu stałymi wielokrotnościami g
  3. 3. D · O(V + E)
  4. 4. B · Wybierz zajęcie, które kończy się najwcześniej, i powtórz dla zgodnych z nim
  5. 5. C · Rozrasta jedno drzewo od wierzchołka startowego, dodając najtańszą krawędź wychodzącą z drzewa
  6. 6. D · Średni koszt na operację w pesymistycznym ciągu operacji
  7. 7. C · Nie, bo 22n = 4ⁿ, a 4ⁿ / 2ⁿ = 2ⁿ rośnie nieograniczenie
  8. 8. A · Problemy decyzyjne rozwiązywalne przez algorytm deterministyczny w czasie wielomianowym

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