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

Co oznacza f(n) = Θ(g(n))?

1. Af jest zawsze mniejsza niż g dla każdego n, więc g ogranicza ją od góry, lecz nigdy od dołu
2. Bf rośnie ściśle szybciej niż g
3. Cf rośnie ściśle wolniej niż g
4. Df rośnie w tym samym tempie co g, ograniczona z góry i z dołu stałymi wielokrotnościami g

Czego wyszukiwanie binarne wymaga od danych wejściowych?

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

Czym jest algorytm siłowy (brute force)?

1. AAlgorytmem, który sprawdza wszystkie możliwe rozwiązania kandydujące
2. BAlgorytmem, który losowo zgaduje odpowiedź
3. CAlgorytmem, który zawsze używa rekurencji
4. DAlgorytmem działającym na wielu procesorach

Co mierzy analiza zamortyzowana?

1. AKoszt pojedynczej najdroższej operacji w dowolnym miejscu ciągu
2. BKoszt algorytmu dla najlepszych danych
3. CŚredni koszt na operację w pesymistycznym ciągu operacji
4. DOczekiwany koszt dla losowych danych wejściowych

Jaka jest zamortyzowana złożoność czasowa dodawania elementu na koniec tablicy dynamicznej, która podwaja swoją pojemność, gdy się zapełni?

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

Programowanie dynamiczne jest przydatne, gdy problem ma:

1. AWyłącznie losowe dane wejściowe
2. BPojedynczą pętlę
3. CŻadnych podproblemów, więc można go rozwiązać w jednym kroku
4. DNakładające się podproblemy i optymalną podstrukturę

Jaka jest złożoność czasowa: for i = 1 to n: for (j = i; j ≤ n; j = j + i) wykonaj pracę O(1)?

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

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. CWierzchołek jest zatwierdzany przy pobraniu, a późniejsza ujemna krawędź mogłaby jeszcze dać mu krótszą ścieżkę
4. DNa każdej ujemnej krawędzi wpada w nieskończoną pętlę