Test z Algorytmy sortowania i wyszukiwania
Algorytmy Sortowania i Wyszukiwania: Kompletny Przewodnik
Test: Algorytmy
20 pytań
Pytanie 1: Sortowanie przez wstawianie polega na braniu kolejnego elementu z nieposortowanej części listy i wstawianiu go w odpowiednie miejsce w już posortowanej części.
A. Tak
B. Nie
Wyjaśnienie: Algorytm sortowania przez wstawianie działa poprzez branie kolejnego elementu z nieposortowanej części listy i wstawianie go w odpowiednie miejsce w już posortowanej części. Jest to zasada działania opisana w materiałach.
Pytanie 2: Złożoność czasowa wyszukiwania liniowego w najlepszym przypadku wynosi O(n).
A. Tak
B. Nie
Wyjaśnienie: Zgodnie z materiałami, złożoność czasowa wyszukiwania liniowego w najlepszym przypadku wynosi O(1), a nie O(n). O(n) to złożoność w najgorszym i średnim przypadku.
Pytanie 3: W interaktywnej symulacji algorytmów sortowania nie można zauważyć drastycznej różnicy w liczbie porównań i zamian elementów między algorytmami sortowania o złożoności O(n²) a tymi o złożoności O(n log n) dla większych zbiorów danych.
A. Tak
B. Nie
Wyjaśnienie: W interaktywnej symulacji można zauważyć drastyczną różnicę w liczbie porównań i zamian elementów między algorytmami sortowania o złożoności O(n²) (np. sortowanie bąbelkowe) a tymi o złożoności O(n log n) (np. sortowanie przez scalanie), zwłaszcza dla większych zbiorów danych. Algorytmy O(n²) wykonują znacznie więcej kroków.
Pytanie 4: Sortowanie przez scalanie działa poprzez wielokrotne znajdowanie najmniejszego elementu z nieposortowanej części listy i zamienianie go miejscami z pierwszym elementem tej części.
A. Tak
B. Nie
Wyjaśnienie: Sortowanie przez scalanie działa na zasadzie „dziel i zwyciężaj”: dzieli listę na dwie połowy, rekurencyjnie sortuje każdą z nich, a następnie scala posortowane połowy w jedną posortowaną listę. Opisany mechanizm (znajdowanie najmniejszego elementu i zamienianie go z pierwszym) to zasada działania sortowania przez wybieranie.
Pytanie 5: Interaktywna symulacja algorytmów wyszukiwania liniowego i binarnego wizualnie demonstruje przewagę złożoności O(log n) nad O(n).
A. Tak
B. Nie
Wyjaśnienie: W sekcji 'Obserwacje w Symulacji Interaktywnej' materiały stwierdzają, że wizualizacja wyszukiwania binarnego, działając na posortowanych danych, szybko eliminuje duże części listy, redukując przestrzeń poszukiwań o połowę w każdym kroku. Materiały podają: 'To wizualnie demonstruje przewagę O(log n) nad O(n)' dla wyszukiwania binarnego w porównaniu do liniowego.