Przystąp do egzaminu: Informatyka - Algorytmy i struktury danych | Zestly

Question 1

Co dzieje się z elementami równymi wartości pivota podczas partycjonowania w standardowej implementacji Quicksort?

Accepted Answer

Mogą znaleźć się po dowolnej stronie pivota lub obok niego

Answer

Są zawsze usuwane z tablicy

Answer

Muszą być zawsze przesunięte na sam początek tablicy

Answer

Zawsze są ignorowane przez algorytm

Question 2

Które z poniższych metod wyboru pivota pomagają uniknąć pesymistycznego przypadku $O(n^2)$?

Accepted Answer

Wybór losowego elementu jako pivota

Accepted Answer

Metoda 'mediany z trzech' (pierwszy, środkowy, ostatni)

Answer

Zawsze wybieranie pierwszego elementu tablicy

Answer

Wybieranie zawsze najmniejszego elementu

Question 3

Jaka jest złożoność pamięciowa algorytmu Quicksort (uwzględniając stos rekurencyjny)?

Accepted Answer

$O(\log n)$

Answer

$O(n^2)$

Answer

$O(n)$

Answer

$O(1)$

Question 4

Dlaczego Quicksort jest często preferowany w praktycznych zastosowaniach mimo istnienia algorytmów o gwarantowanej złożoności $O(n \log n)$ (np. HeapSort)?

Answer

Posiada bardzo małą stałą ukrytą w notacji O

Answer

Lepiej wykorzystuje pamięć podręczną procesora (cache)

Answer

Zawsze gwarantuje najszybszy czas wykonania

Answer

Jest prostszy w implementacji niż każdy inny algorytm

Question 5

W jakim przypadku algorytm Quicksort kończy swoje działanie?

Answer

Gdy podzbiór ma 0 lub 1 element

Answer

Gdy pivot jest równy 0

Answer

Gdy wszystkie elementy są równe

Answer

Gdy liczba porównań przekroczy $n^2$