Test z Sortowanie przez scalanie (merge sort)

Pytanie 1: W pseudokodzie algorytmu Merge Sort, procedura `MergeSort` wywołuje samą siebie rekurencyjnie.

A. Tak

B. Nie

Wyjaśnienie: Zgodnie z pseudokodem, procedura `MergeSort` zawiera w sobie wywołania `MergeSort(tablica, lewy, srodek)` oraz `MergeSort(tablica, srodek + 1, prawy)`, co oznacza, że jest to wywołanie rekurencyjne. Są to komentarze 'Rekurencyjnie sortuj lewą połowę' i 'Rekurencyjnie sortuj prawą połowę'.

Pytanie 2: Jaka jest złożoność czasowa algorytmu sortowania przez scalanie (Merge Sort) i co jest jedną z jego głównych zalet w tym kontekście?

A. O(n²), ponieważ na każdym poziomie rekurencji elementy są porównywane dwukrotnie.

B. O(n log n) w najlepszym, średnim i najgorszym przypadku, co zapewnia przewidywalną wydajność.

C. O(log n), ponieważ główny koszt wynika z liczby poziomów podziału tablicy.

D. O(n), ponieważ na każdym poziomie scalania operacje trwają czas proporcjonalny do liczby elementów.

Wyjaśnienie: Złożoność czasowa sortowania przez scalanie jest wyrażana jako O(n log n). Jest to prawda dla najlepszego, średniego i najgorszego przypadku, co jest jedną z głównych zalet Merge Sortu, zapewniającą jego przewidywalność i niezawodność.

Pytanie 3: Pominięcie warunku `JEŻELI lewy < prawy` w implementacji funkcji scalającej Merge Sort jest jedyną przyczyną nieskończonej rekurencji i przepełnienia stosu.

A. Tak

B. Nie

Wyjaśnienie: Pominięcie warunku bazowego (`JEŻELI lewy < prawy`) lub jego nieprawidłowe zdefiniowanie może prowadzić do nieskończonej rekurencji i przepełnienia stosu. Materiały wskazują, że zarówno zapomnienie o nim, jak i jego nieprawidłowe zdefiniowanie są problemami, co oznacza, że nie jest to jedyna przyczyna, a błędne zdefiniowanie również może być problemem.

Pytanie 4: Wydajność algorytmu Merge Sort jest stała niezależnie od tego, czy dane wejściowe są już posortowane, posortowane odwrotnie, czy losowe.

A. Tak

B. Nie

Wyjaśnienie: Materiał jasno stwierdza, że Merge Sort zachowuje swoją wydajność niezależnie od tego, czy dane wejściowe są już posortowane, posortowane odwrotnie, czy losowe, zawsze pozostając algorytmem o złożoności O(n log n).

Pytanie 5: Które z poniższych stwierdzeń prawidłowo opisuje lub odnosi się do implementacji funkcji scalającej w algorytmie sortowania przez scalanie, zgodnie z przedstawionymi materiałami?

A. W procesie scalania elementy są przenoszone bezpośrednio z dwóch podtablic do głównej tablicy wynikowej, zawsze bez użycia tymczasowych tablic L[] i R[].

B. Wskaźniki 'i' oraz 'j' służą do śledzenia aktualnej pozycji w tymczasowych podtablicach L[] i R[], natomiast 'k' śledzi pozycję w głównej tablicy wynikowej.

C. Po zakończeniu głównej pętli scalania, konieczne jest skopiowanie pozostałych elementów z jednej lub obu tymczasowych podtablic L[] lub R[] do tablicy głównej.

D. Najczęstszym błędem podczas implementacji funkcji scalającej jest zapomnienie o warunku bazowym rekurencji, co prowadzi do nieskończonej pętli scalania.

Wyjaśnienie: Zgodnie z materiałami, wskaźniki 'i' i 'j' są używane jako 'Początkowy indeks pierwszej podtablicy' i 'Początkowy indeks drugiej podtablicy' (odpowiednio dla L[] i R[]), a 'k' jako 'Początkowy indeks scalanej podtablicy' (czyli w głównej tablicy). Po zakończeniu głównej pętli 'DOPÓKI i < rozmiar_lewej ORAZ j < rozmiar_prawej', materiały wyraźnie wskazują na konieczność 'Skopiuj pozostałe elementy L[], jeśli jakieś są' oraz 'Skopiuj pozostałe elementy R[], jeśli jakieś są'. Opcja 0 jest błędna, ponieważ materiały pokazują użycie tymczasowych tablic L[] i R[] ('L[i] = tablica[lewy + i]', 'R[j] = tablica[srodek + 1 + j]'). Opcja 3 jest błędna; choć błędy indeksowania są powszechne, a warunek bazowy jest ważny w rekurencji, materiały wskazują, że 'Błędy indeksowania (tzw. off-by-one errors) są bardzo powszechne podczas implementacji funkcji Merge', a zapomnienie o warunku bazowym rekurencji odnosi się do błędów w ogólnej strukturze algorytmu, a nie konkretnie funkcji scalającej.