Sprawdzian z algorytmiki

Poprawna odpowiedź: C

Funkcja liczy silnię: $g(5)=5\cdot 4\cdot 3\cdot 2\cdot 1\cdot g(0)=120$. Warunek $g(0)=1$ zatrzymuje rekurencję. Wynik 24 to $g(4)$, a 720 to $g(6)$.

Poprawna odpowiedź: (1) dziel i zwyciężaj; (2) zachłannym

Metodą „dziel i zwyciężaj” działają m.in. sortowanie przez scalanie i szybkie. Algorytm zachłanny podejmuje decyzje bez patrzenia w przyszłość, np. wydaje resztę zawsze największym pasującym nominałem. Jest szybki, ale nie dla każdego problemu daje wynik optymalny.

Poprawna odpowiedź: 1–B, 2–D, 3–A, 4–C

• 1. $O(1)$ → B. Dostęp do elementu tablicy po indeksie
• 2. $O(\log n)$ → D. Wyszukiwanie binarne w posortowanej tablicy
• 3. $O(n\log n)$ → A. Sortowanie przez scalanie (merge sort)
• 4. $O(n^2)$ → C. Dwie zagnieżdżone pętle for, każda od 1 do n

Indeks pozwala od razu obliczyć adres elementu, więc to $O(1)$. Wyszukiwanie binarne w każdym kroku połowi przedział, stąd $O(\log n)$. Merge sort ma około $\log n$ poziomów podziału, a na każdym scala $n$ elementów. Dwie pełne pętle zagnieżdżone wykonują $n\cdot n$ obrotów.

Poprawna odpowiedź: F, F, F, P

DFS korzysta ze stosu albo z rekurencji, kolejki FIFO używa BFS. BFS przegląda każdy wierzchołek i każdą krawędź, więc działa w czasie $O(V+E)$. Dijkstra zakłada nieujemne wagi; przy ujemnych stosuje się np. algorytm Bellmana-Forda. BFS odwiedza wierzchołki warstwami, więc do każdego dochodzi najkrótszą drogą.

Poprawna odpowiedź: B

Kolejne kroki: $252\mathrm{mod}198=54$, $198\mathrm{mod}54=36$, $54\mathrm{mod}36=18$, $36\mathrm{mod}18=0$. Po czwartej operacji reszta jest zerem, więc $\mathrm{NWD}(252,198)=18$, czyli ostatni niezerowy dzielnik.