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

Co opisuje średni czas działania?

1. AOczekiwany czas przy danym rozkładzie danych wejściowych rozmiaru n
2. BCzas dla danych o przeciętnej długości
3. CWartość pośrodku między czasami działania w przypadku optymistycznym a pesymistycznym
4. DCzas na najpopularniejszym komputerze

Który z tych czasów działania jest wielomianowy?

1. AO(2ⁿ)
2. BO(n³)
3. CO(nⁿ)
4. DO(n!)

Jaka jest złożoność czasowa przeszukiwania w głąb grafu zapisanego jako listy sąsiedztwa?

1. AO(V × E)
2. BO(E log V)
3. CO(V + E)
4. DO(V²)

Dlaczego wiele bibliotecznych procedur sortowania przełącza się na sortowanie przez wstawianie dla bardzo małych podtablic?

1. AAlgorytmy rekurencyjne nie radzą sobie z tablicami poniżej 10 elementów
2. BSortowanie przez wstawianie ma mały narzut i jest szybkie dla małych lub prawie posortowanych danych
3. CSortowanie przez wstawianie zużywa mniej pamięci niż każdy inny algorytm sortowania dla dużych danych
4. DSortowanie przez wstawianie jest O(n log n) w najgorszym przypadku

Funkcja wykonuje jedną pętlę n iteracji, a potem osobno drugą pętlę n iteracji. Jaka jest jej złożoność czasowa?

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

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

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

Dlaczego algorytm Dijkstry może dawać błędne wyniki, gdy niektóre wagi krawędzi są ujemne?

1. ADziała tylko na grafach nieskierowanych
2. BLiczb ujemnych nie można przechowywać w kolejce priorytetowej
3. CNa każdej ujemnej krawędzi wpada w nieskończoną pętlę
4. DWierzchołek jest zatwierdzany przy pobraniu, a późniejsza ujemna krawędź mogłaby jeszcze dać mu krótszą ścieżkę

Które ograniczenie jest poprawne dla log(n!)?

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