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 optymistyczna złożoność czasowa sortowania przez wstawianie dla już posortowanej tablicy?

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

Który algorytm sortowania wielokrotnie zamienia miejscami sąsiednie elementy ustawione w złej kolejności?

  1. ASortowanie przez scalanie
  2. BSortowanie bąbelkowe
  3. CSortowanie przez kopcowanie
  4. DSortowanie szybkie (quicksort)
3.Łatwy

Ile wynosi log₂ 1024?

  1. A32
  2. B512
  3. C10
  4. D12
4.Średni

Przeszukiwanie wszerz w grafie nieważonym znajduje:

  1. AMinimalne drzewo rozpinające
  2. BPorządek topologiczny w dowolnym grafie
  3. CNajkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego
  4. DNajkrótsze ścieżki w grafach zawierających ujemne wagi krawędzi
5.Średni

Które stwierdzenie o funkcji rekurencyjnej bez osiągalnego przypadku bazowego jest poprawne?

  1. AKompilator zawsze zamienia ją na pętlę, która kończy się bezpiecznie
  2. BAutomatycznie zwraca 0
  3. CDziała w czasie O(1)
  4. DWywołuje samą siebie, aż przepełni się stos wywołań
6.Ś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(k n log n)
  2. BO(n log n + k log n)
  3. CO(n + k)
  4. DO(nk)
7.Trudny

Wzięcie obu końców każdej krawędzi w skojarzeniu maksymalnym (w sensie zawierania) daje pokrycie wierzchołkowe. Jak dobre jest to pokrycie?

  1. ANajwyżej dwa razy większe niż minimalne pokrycie wierzchołkowe
  2. BZawsze jest minimalnym pokryciem wierzchołkowym
  3. CO nieznanej jakości w porównaniu z optimum
  4. DNajwyżej log n razy większe niż minimum
8.Trudny

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

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

Klucz odpowiedzi

  1. 1. D · O(n)
  2. 2. B · Sortowanie bąbelkowe
  3. 3. C · 10
  4. 4. C · Najkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego
  5. 5. D · Wywołuje samą siebie, aż przepełni się stos wywołań
  6. 6. B · O(n log n + k log n)
  7. 7. A · Najwyżej dwa razy większe niż minimalne pokrycie wierzchołkowe
  8. 8. D · 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.