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. AFunkcją wywołującą samą siebie dla mniejszych danych wejściowych
  2. BMetodą sortowania
  3. CRodzajem struktury danych
  4. DPętlą, która nigdy się nie kończy
2.Łatwy

Czym jest algorytm?

  1. AStrukturą danych przechowującą liczby
  2. BSkończonym ciągiem dobrze określonych kroków rozwiązującym problem
  3. CJęzykiem programowania przeznaczonym do zapisu wzorów matematycznych
  4. DDowolnym programem z interfejsem graficznym
3.Łatwy

Czym jest memoizacja?

  1. AZwalnianiem pamięci po powrocie z funkcji
  2. BAutomatyczną zamianą rekurencji na równoważną pętlę, tak że stos wywołań nie jest potrzebny
  3. CZapamiętywaniem wyników wywołań funkcji, tak by powtórne wywołania były obsługiwane z pamięci
  4. DPisaniem komentarzy obok każdego wiersza kodu
4.Średni

Jaki jest czas działania sortowania pozycyjnego LSD (radix sort) dla n liczb całkowitych o d cyfrach w systemie o podstawie k?

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

Ile pamięci stosu zużywa prosta rekurencyjna funkcja silni fact(n) = n × fact(n − 1)?

  1. AO(1)
  2. BO(log n)
  3. CO(n)
  4. DO(n²)
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(nk)
  2. BO(k n log n)
  3. CO(n + k)
  4. DO(n log n + k log n)
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

Dlaczego wyszukiwanie binarne nie daje czasu O(log n) na liście jednokierunkowej?

  1. AWyszukiwanie binarne wymaga co najmniej dwa razy więcej pamięci
  2. BDotarcie do środkowego elementu wymaga O(n) kroków, bo nie ma bezpośredniego dostępu po indeksie
  3. CPorównania na węzłach listy są wolniejsze
  4. DList nie da się posortować

Klucz odpowiedzi

  1. 1. A · Funkcją wywołującą samą siebie dla mniejszych danych wejściowych
  2. 2. B · Skończonym ciągiem dobrze określonych kroków rozwiązującym problem
  3. 3. C · Zapamiętywaniem wyników wywołań funkcji, tak by powtórne wywołania były obsługiwane z pamięci
  4. 4. B · O(d(n + k))
  5. 5. C · O(n)
  6. 6. D · O(n log n + k log n)
  7. 7. A · Najwyżej dwa razy większe niż minimalne pokrycie wierzchołkowe
  8. 8. B · Dotarcie do środkowego elementu wymaga O(n) kroków, bo nie ma bezpośredniego dostępu po indeksie

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