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

Który algorytm sortowania wybiera element osiowy (pivot) i dzieli tablicę na elementy mniejsze i większe?

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

Czym jest przypadek bazowy funkcji rekurencyjnej?

1. AWywołaniem zużywającym najwięcej pamięci
2. BPierwszym wierszem funkcji
3. CPrzypadkiem z największymi danymi wejściowymi, który obsługuje się przed jakimikolwiek wywołaniami rekurencyjnymi
4. DPrzypadkiem, na który odpowiada się bezpośrednio, bez kolejnego wywołania rekurencyjnego

Ile wynosi log₂ 1024?

1. A512
2. B10
3. C32
4. D12

Które stwierdzenie o funkcji rekurencyjnej bez osiągalnego przypadku bazowego jest poprawne?

1. AAutomatycznie zwraca 0
2. BWywołuje samą siebie, aż przepełni się stos wywołań
3. CKompilator zawsze zamienia ją na pętlę, która kończy się bezpiecznie
4. DDziała w czasie O(1)

Dlaczego w notacji dużego O zwykle pomija się podstawę logarytmu, jak w O(log n)?

1. APodstawa ma znaczenie tylko dla małych n
2. BLogarytmy zawsze zaokrągla się do liczb całkowitych
3. CWszystkie logarytmy w informatyce mają podstawę 10, więc jest ona domyślna
4. DLogarytmy o różnych podstawach różnią się tylko stałym czynnikiem

Ile pamięci stosu zużywa prosta rekurencyjna funkcja silni fact(n) = n × fact(n − 1)?

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

Jak porównują się n! i 2ⁿ dla dużych n?

1. ARosną w tym samym tempie
2. B2ⁿ rośnie szybciej niż n!
3. Cn! jest O(n²)
4. Dn! rośnie szybciej niż 2ⁿ

Dla którego wariantu problemu plecakowego reguła zachłanna „bierz przedmioty według wartości na jednostkę wagi" zawsze daje optymalną odpowiedź?

1. AŻadnego z wariantów
2. BObu wariantów
3. CCiągłego (ułamkowego) problemu plecakowego, w którym przedmioty można dzielić
4. DDyskretnego problemu plecakowego 0/1, w którym przedmioty zawsze trzeba brać w całości