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. BPętlą, która nigdy się nie kończy
3. CMetodą sortowania
4. DRodzajem struktury danych

Co oznacza, że operacja działa w czasie O(1)?

1. AJej czas działania nie rośnie wraz z rozmiarem danych wejściowych
2. BMożna ją wykonać tylko raz
3. CZawsze trwa dokładnie jedną sekundę
4. DPrzetwarza dokładnie jeden element na sekundę czasu działania

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

1. AStały
2. BLiniowy
3. CKwadratowy
4. DLogarytmiczny

Który algorytm sortowania jest stabilny?

1. ASortowanie szybkie (typowa wersja w miejscu)
2. BSortowanie przez scalanie
3. CSortowanie przez wybieranie (typowa wersja)
4. DSortowanie przez kopcowanie

Który algorytm znajduje najkrótsze ścieżki z jednego źródła w grafie o nieujemnych wagach krawędzi?

1. AAlgorytm Kruskala
2. BPrzeszukiwanie w głąb (DFS)
3. CAlgorytm Dijkstry
4. DWe wszystkich przypadkach wymagany jest algorytm Bellmana–Forda

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

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

Które stwierdzenie o notacji małego o jest poprawne?

1. An² = o(n)
2. B2n = o(n), bo 2n rośnie wolno
3. Cn = o(n²), ale n nie jest o(n)
4. Dn = o(n), bo każda funkcja jest małym o samej siebie

Który algorytm znajduje minimalne drzewo rozpinające, wielokrotnie dodając najtańszą krawędź, która nie tworzy cyklu?

1. AAlgorytm Kruskala
2. BAlgorytm Dijkstry
3. CAlgorytm Floyda–Warshalla
4. DAlgorytm Prima startujący z jednego wierzchołka