Algorytmy i złożoność: karta pracy z odpowiedziami

Czym jest rekurencja?

1. AFunkcją wywołującą samą siebie dla mniejszych danych wejściowych
2. BMetodą sortowania
3. CPętlą, która nigdy się nie kończy
4. DRodzajem struktury danych

Czym jest algorytm siłowy (brute force)?

1. AAlgorytmem, który sprawdza wszystkie możliwe rozwiązania kandydujące
2. BAlgorytmem, który zawsze używa rekurencji
3. CAlgorytmem, który losowo zgaduje odpowiedź
4. DAlgorytmem działającym na wielu procesorach

Problem zwykle nazywa się praktycznie rozwiązywalnym (tractable), jeśli:

1. ADa się go rozwiązać w czasie wielomianowym
2. BDa się go rozwiązać w czasie stałym
3. CDa się go rozwiązać tylko przez sprawdzenie wszystkich możliwości
4. DNie ma rozwiązania

Quicksort zawsze używa pierwszego elementu jako elementu osiowego. Dla jakich danych wykazuje zachowanie pesymistyczne?

1. ADla tablicy, w której wszystkie elementy są różne
2. BDla tablicy o długości 2
3. CDla tablicy w losowej kolejności
4. DDla tablicy już posortowanej

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

1. AWybierz najpierw najkrótsze zajęcie
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 zajęcie z najmniejszą liczbą kolizji, a potem powtarzaj dla zgodnych zajęć

Jaka jest złożoność czasowa obliczania n-tej liczby Fibonacciego za pomocą tablicy wypełnianej wstępująco (bottom-up)?

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

Które stwierdzenie o wyborze k-tego najmniejszego elementu nieposortowanej tablicy jest poprawne?

1. AWybór jest możliwy tylko w O(n²)
2. BQuickselect działa w O(log n) w najgorszym przypadku, bo schodzi rekurencyjnie tylko po jednej stronie piwota
3. CQuickselect działa w oczekiwanym czasie O(n), a mediana median gwarantuje O(n) w najgorszym przypadku
4. DWybór zawsze wymaga Ω(n log n), bo wymaga sortowania

Co trzeba zrobić, aby wykazać, że nowy problem X jest NP-trudny?

1. AWykazać, że X można zweryfikować w czasie wielomianowym
2. BZredukować znany problem NP-trudny do X w czasie wielomianowym
3. CWykazać, że X nie ma algorytmu wielomianowego dla małych danych
4. DZredukować X do znanego problemu NP-trudnego w czasie wielomianowym