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

Ile dodatkowej pamięci używa standardowe sortowanie przez scalanie oparte na tablicach?

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

Jaką strategię projektowania stosuje sortowanie przez scalanie?

1. AWybór zachłanny
2. BDziel i zwyciężaj
3. CSiłę brutalną (przegląd zupełny)
4. DProgramowanie dynamiczne

Jak działa sortowanie przez wybieranie?

1. ADzieli tablicę na połowy i je scala
2. BWielokrotnie zamienia sąsiednie elementy w złej kolejności
3. CWstawia każdy element do rosnącej posortowanej części przez przesuwanie
4. DWielokrotnie znajduje minimum nieposortowanej części i zamienia je na początek

Jaka jest złożoność czasowa: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Algorytm zachłanny:

1. AUżywa wyłącznie rekurencji
2. BSprawdza każde możliwe rozwiązanie
3. CZawsze daje rozwiązanie optymalne
4. DW każdym kroku dokonuje lokalnie najlepszego wyboru

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 w losowej kolejności
3. CDla tablicy już posortowanej
4. DDla tablicy o długości 2

Problem jest NP-zupełny, jeśli:

1. ANależy do NP i każdy problem z NP sprowadza się do niego w czasie wielomianowym
2. BNie da się go rozwiązać
3. CDa się go rozwiązać w czasie wielomianowym
4. DLeży poza NP, ale jest trudniejszy od wszystkich problemów NP, jak problem stopu

Która definicja klasy P jest poprawna?

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