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

Który algorytm sortowania wielokrotnie zamienia miejscami sąsiednie elementy ustawione w złej kolejności?

1. ASortowanie bąbelkowe
2. BSortowanie szybkie (quicksort)
3. CSortowanie przez scalanie
4. DSortowanie przez kopcowanie

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

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

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

Ile mniej więcej porównań potrzebuje wyszukiwanie binarne w najgorszym przypadku w posortowanej tablicy 1,000,000 elementów?

1. AOkoło 100
2. BOkoło 20
3. COkoło 500,000
4. DOkoło 1,000

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

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

Złożoność czasowa naiwnego rekurencyjnego obliczania ciągu Fibonacciego (fib(n) = fib(n−1) + fib(n−2)) jest:

1. ALogarytmiczna
2. BWykładnicza
3. CStała
4. DLiniowa

Dlaczego średni czas wyszukiwania w tablicy mieszającej wynosi O(1), a w najgorszym przypadku O(n)?

1. AFunkcje skrótu są wolne
2. BWiele kluczy może kolidować i trafić do tego samego kubełka
3. CDostęp do tablic ma złożoność O(n)
4. DKlucze muszą być najpierw posortowane

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 log n)
2. BO(n)
3. CO(n √n)
4. DO(n²)