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

Czym jest rekurencja?

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

Złożoność pamięciowa mierzy:

1. AIlość pamięci potrzebnej algorytmowi wraz ze wzrostem danych wejściowych
2. BLiczbę linii kodu
3. CFizyczny rozmiar komputera
4. DMiejsce na dysku zajmowane przez plik programu po jego skompilowaniu

Czas działania algorytmu wynosi O(n). Jak nazywa się ten wzrost?

1. AKwadratowy
2. BLiniowy
3. CStały
4. DLogarytmiczny

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

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

Jakie jest rozwiązanie rekurencji T(n) = T(n − 1) + O(n)?

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

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

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

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. AO nieznanej jakości w porównaniu z optimum
2. BZawsze jest minimalnym pokryciem wierzchołkowym
3. CNajwyżej log n razy większe niż minimum
4. DNajwyżej dwa razy większe niż minimalne pokrycie wierzchołkowe

Która technika zapewnia oczekiwany czas działania O(n log n) dla quicksorta na dowolnych danych wejściowych?

1. AStosowanie rekurencji tylko po lewej stronie
2. BPosortowanie danych przed uruchomieniem quicksorta
3. CWybieranie zawsze pierwszego elementu
4. DLosowanie pivota z rozkładem jednostajnym