Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie
Zestaw: "Algorytmy sortujące - sortowanie przez scalanie, sortowanie przez zliczanie"
Sortowanie przez scalanie to inaczej:
merge sort
counting sort
bucket sort
comb sort
Operacja połączenia dwóch uporządkowanych rosnąco ciągów elementów w jeden ciąg wynikowy, również uporządkowany rosnąco to:
scalanie ciągów
regeneracja ciągów
implementacja ciągów
rekurencja ciągów
Odkrywcą algorytmu sortowania przez scalanie był
Pierre Bouchard
Donald Knuth
John von Neumann
Rob Box
Sortowanie przez scalanie to:
indukcyjny algorytm sortowania danych
rekurencyjny algorytm sortowania danych
iteracyjnym algorytmem sortowania danych
wszystkie odpowiedzi są poprawne
Klasa złożoności obliczeniowej algorytmu sortowania przez scalanie to:
O(n!)
O(n log n)
O(n2)
O(n)
Algorytm sortowania przez scalanie opiera się na zasadzie:
ograniczonej racjonalności
dziel i zwyciężaj
drzewa gier
graj i wygrywaj
Podstawową operacją algorytmu merge sort jest scalanie dwóch zbiorów uporządkowanych w jeden zbiór również uporządkowany.
prawda
fałsz
Operację scalania realizujemy wykorzystując pomocniczy zbiór, w którym tymczasowo znajdują się scalane elementy dwóch zbiorów.
prawda
fałsz
Sortowanie przez zliczanie to inaczej:
merge sort
counting sort
bucket sort
comb sort
Klasa złożoności obliczeniowej algorytmu sortowania przez zliczanie to:
O(n+k)
O(n log n)
O(n2)
O(n!)
Wadą algorytmu sortowania przez zliczanie jest:
potrzeba dodatkowej pamięci n+k
możliwość sortowania tylko liczb całkowitych z ograniczonego zakresu
nie jest to sortowanie w miejscu
wszystkie odpowiedzi są prawidłowe
W metodzie sortowania przez zliczanie:
algorytm jest stabilny, sortowanie nie odbywa się w miejscu
algorytm jest niestabilny, sortowanie odbywa się w miejscu
algorytm jest niestabilny, sortowanie nie odbywa się w miejscu
algorytm jest stabilny, sortowanie odbywa się w miejscu
Ogólnie idea algorytmu przez zliczanie polega na:
dzieleniu sortowanego zbioru na podzbiory, których elementy są odległe od siebie w sortowanym zbiorze o pewien odstęp h
cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru
sprawdzeniu ile wystąpień danego klucza występuje w sortowanej tablicy
dzieleniu sortowanego zbioru na dwa podzbiory, które są niezależnie sortowane
Aby algorytm sortowania przez zliczanie był stabilny podczas sortowania wartości kluczy musimy wykonać:
obieg liniowy
obieg dystrybucyjny
dodatkowe dzielenie zbioru sortowanego
obieg iteracyjny
Wartości klucze to:
wartości, które są przypisane pewnym większym strukturom danych
podzbiory sortowanych danych
zmienne sortowania danych
wszystkie odpowiedzi są poprawne
Obieg dystrybucyjny ma za zadanie:
wykonać operację sortowania przez wstawianie
obliczyć ilość elementów mniejszych lub równych od danej wartości
obliczyć ilość elementów większych od danej wartości
obliczyć ilość elementów równych danej wartości
Sortowanie przez zliczanie nie wykonuje żadnych porównań elementów sortowanych
prawda
fałsz
W algorytmach stabilnych:
elementy w zbiorach sortowanych, o tych samych wartościach występują w tablicy wynikowej w odwrotnej kolejności jak w tablicy wejściowej
elementy w zbiorach sortowanych, o tych samych wartościach występują w tablicy wynikowej w różnej kolejności jak w tablicy wejściowej
elementy w zbiorach sortowanych, o tych samych wartościach występują w tablicy wynikowej w takiej samej kolejności jak w tablicy wejściowej
elementy w zbiorach sortowanych, o różnych wartościach występują w tablicy wynikowej w takiej samej kolejności jak w tablicy wejściowej




Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie