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

Jaka jest złożoność czasowa wyszukiwania liniowego w nieposortowanej tablicy n elementów (w najgorszym przypadku)?

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

Czego wyszukiwanie binarne wymaga od danych wejściowych?

1. ATablica może zawierać tylko liczby dodatnie
2. BDługość tablicy musi być potęgą dwójki
3. CTablica może mieć najwyżej 1000 elementów
4. DTablica musi być posortowana

Która z tych funkcji rośnie najwolniej, gdy n staje się duże?

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

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

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

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

1. AWe wszystkich przypadkach wymagany jest algorytm Bellmana–Forda
2. BAlgorytm Kruskala
3. CPrzeszukiwanie w głąb (DFS)
4. DAlgorytm Dijkstry

Przeszukiwanie wszerz w grafie nieważonym znajduje:

1. AMinimalne drzewo rozpinające
2. BPorządek topologiczny w dowolnym grafie
3. CNajkrótsze ścieżki w grafach zawierających ujemne wagi krawędzi
4. DNajkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego

Sortowanie przez wstawianie działa w O(n) dla danych posortowanych. Czy to przeczy dolnemu ograniczeniu Ω(n log n) dla sortowania przez porównania?

1. ATak, ale tylko dla tablic krótszych niż 100
2. BNie, dolne ograniczenie dotyczy najgorszego przypadku po wszystkich danych, a nie każdych danych
3. CTak, więc dolne ograniczenie jest błędne
4. DNie, bo sortowanie przez wstawianie nie jest sortowaniem przez porównania

Korzystając z twierdzenia o rekurencji uniwersalnej (master theorem), rozwiązaniem T(n) = 8T(n/2) + O(n²) jest:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)