Rozwiąż quiz: Informatyka - Algorytmy i struktury danych | Zestly

Question 1

Na jakiej głównej strategii projektowania algorytmów opiera się algorytm Quicksort?

Accepted Answer

Dziel i zwyciężaj

Answer

Programowanie dynamiczne

Answer

Zachłanna

Answer

Przeszukiwanie z nawrotami

Question 2

Które z poniższych stwierdzeń poprawnie opisują rolę elementu centralnego (pivota) w algorytmie Quicksort?

Accepted Answer

Służy jako punkt odniesienia do podziału elementów na dwie grupy

Accepted Answer

Wokół niego następuje przestawianie elementów mniejszych i większych

Answer

Zawsze musi być elementem o największej wartości w tablicy

Answer

Jest zawsze elementem znajdującym się na środku indeksowym tablicy

Question 3

Jaka jest złożoność obliczeniowa algorytmu Quicksort w przypadku średnim?

Accepted Answer

$O(n \log n)$

Answer

$O(n)$

Answer

$O(n^2)$

Answer

$O(\log n)$

Question 4

W jakiej sytuacji algorytm Quicksort osiąga swoją pesymistyczną złożoność obliczeniową $O(n^2)$?

Answer

Gdy tablica jest całkowicie losowa

Answer

Gdy pivot jest zawsze najmniejszym lub największym elementem w podzbiorze

Answer

Gdy tablica zawiera tylko dwa unikalne elementy

Answer

Gdy tablica jest posortowana w kolejności malejącej, a pivotem jest zawsze środkowy element

Question 5

Które z poniższych cech charakteryzują algorytm Quicksort?

Answer

Jest algorytmem niestabilnym

Answer

Wymaga dodatkowej pamięci proporcjonalnej do $n$

Answer

Jest zazwyczaj szybszy od sortowania przez scalanie (Merge Sort) w pamięci operacyjnej

Answer

Działa w miejscu (in-place)