Klasy algorytmów sortowania

Quiz sprawdza wiedzę o właściwościach i implementacjach popularnych algorytmów sortowania opisanych w dokumencie. Pytania obejmują stabilność, złożoności, implementacje w Pythonie oraz pułapki praktyczne.

Ten quiz zawiera 15 pytań i wymaga włączonego JavaScript do interaktywnego rozwiązywania.

Przeglądaj quizy

Pytanie 1 z 15

Klasy algorytmów sortowania

Autor: justine

8 wyświetleń 0 ukończeń 15 pytań

Rozwiąż quiz

Twoje imię

Rozwiąż quiz

1 Co nazywamy kluczem w sortowaniu?

A dodatkowa pamięć pomocnicza wykorzystywana podczas sortowania fragmentów tablicy B wartość używana do porównania elementów, np. liczba, napis, data lub wynik funkcji C parametr algorytmu sterujący kierunkiem porównań i liczbą iteracji D unikalny identyfikator każdego rekordu, konieczny do zachowania porządku po sortowaniu

2 Dlaczego counting sort i radix sort omijają dolne ograniczenie Ω(n log n)?

A wybierają losowy pivot, by zredukować liczbę porównań do liniowej B stosują rekurencyjne dzielenie wejścia na połowy i scalanie bez porównań C używają stabilnych wewnętrznych sortowań o złożoności O(n) dla każdego poziomu D korzystają ze struktury kluczy zamiast polegać wyłącznie na porównaniach

3 Co oznacza, że algorytm jest in-place?

A tworzy nową strukturę danych równoległą do wejściowej B używa małej pamięci pomocniczej poza wejściem C zachowuje kolejność elementów o równych kluczach D dzieli dane rekurencyjnie, potrzebując O(n) dodatkowej pamięci

4 Czym jest stabilny sort?

A usuwa duplikaty o takim samym kluczu podczas scalenia B wykonuje minimalną liczbę zamian i porównań C zawsze działa w czasie O(n log n) niezależnie od danych D zachowuje kolejność elementów o równych kluczach

5 Jaki wynik skryptu z sorted(records, key=lambda record: record[1]) według przykładu?

A [("Ewa", 'algo', 3), ("Ben", 'math', 1), ("Ada", 'math', 2)] B [("Ben", 'math', 1), ("Ada", 'math', 2), ("Ewa", 'algo', 3)] C [("Ewa", 'algo', 3), ("Ada", 'math', 2), ("Ben", 'math', 1)] D [("Ada", 'math', 2), ("Ben", 'math', 1), ("Ewa", 'algo', 3)]

6 Jak działa pojedyncza pełna iteracja w bubble sort?

A po jednej iteracji tablica jest już w pełni posortowana B po jednej iteracji wszystkie elementy z duplikatami są scalane C po jednej iteracji najmniejszy element trafia na początek D po jednej iteracji największy element trafia na koniec

7 Jaka jest złożoność średnia i pesymistyczna bubble sort?

A O(n² log n) gdy tablica zawiera duplikaty i wymaga stabilności B O(n log n) dzięki podziałowi i scalaniu fragmentów C O(n) dla dowolnego wejścia, gdy użyta jest flaga swapped D O(n²) ze względu na wiele lokalnych porównań

8 Co robi flaga swapped w wariancie bubble sort?

A umożliwia zakończenie po jednym przejściu dla już posortowanych danych B zmniejsza pamięć dodatkową, czyniąc algorytm out-of-place C gwarantuje stabilność przez śledzenie pozycji elementów o równych kluczach D zapobiega tworzeniu nowych runów wymaganych przez Timsort

9 Jak insertion sort umieszcza kolejny element w porządku?

A zamienia zawsze element z jego prawym sąsiadem aż osiągnie początek B tworzy listy mniejszych, równych i większych względem pivotu C dzieli tablicę na połowy i rekurencyjnie scala elementy D przesuwa element w lewo aż znajdzie miejsce po mniejszych lub równych i przed większymi

10 Kiedy insertion sort działa w czasie O(n)?

A gdy sortowanie wykonuje dwukrotne scalanie runów przy użyciu O(n) pamięci B gdy algorytm stosuje losowy wybór pivotu dla każdego elementu C dla danych prawie posortowanych, gdy liczba przesunięć jest mała D gdy wejście jest losowe i nie zawiera duplikatów

11 Od czego zależy stabilność insertion sort w implementacji z while?

A od wyboru pivota i losowości w pętli głównej B od wykrywania naturalnych runów przed wykonaniem przesunięć C od ilości pamięci O(n) użytej do scalenia przesunięć D od warunku przesuwania; użycie '>=' zamiast '>' może złamać stabilność

12 Jak merge sort scala dwie posortowane sekwencje, zgodnie z opisem?

A stosuje partycjonowanie wokół pivota, aby osobno posortować fragmenty B najpierw konkatenatuje sekwencje, potem usuwa duplikaty i sortuje wynik C przepisuje elementy do oryginalnej tablicy bez użycia dodatkowej pamięci D porównuje czołowe elementy i wybiera z lewej, gdy jest mniejsze lub równe

13 Dlaczego standardowy merge sort potrzebuje dodatkowej pamięci O(n)?

A bo na scalenie fragmentów używa dodatkowej tablicy do przechowywania merged B bo wykrywa naturalne runy i przechowuje je w strukturach pomocniczych o rozmiarze O(log n) C bo wybiera pivot i buduje trzy listy smaller/equal/larger wymagające O(n) pamięci D bo dokonuje lokalnych zamian między sąsiadami bez tworzenia nowej listy

14 Co powoduje pesymistyczne O(n²) w quicksort?

A brak stabilności spowodowany użyciem dodatkowej pamięci O(n) przy scalaniu B zły wybór pivota, np. zawsze pierwszy element dla już posortowanych danych C użycie flaga swapped, która kończy sortowanie zbyt wcześnie D wykrywanie i rozszerzanie naturalnych runów podobnie jak w Timsort

15 Jak randomizacja pivota wpływa na quicksort?

A gwarantuje liniowy czas działania O(n) dla wszystkich możliwych wejść B zapewnia stabilność przez zachowanie oryginalnej kolejności równych elementów C sprawia, że algorytm działa wyłącznie out-of-place i używa O(n) pamięci D zmniejsza ryzyko deterministycznego przypadku prowadzącego do O(n²), ale nie usuwa go matematycznie

0 z 15 odpowiedzi

Nie odpowiedziano na 15 z 15 pytań. Wróć i uzupełnij brakujące odpowiedzi.

Często zadawane pytania

Ile pytań zawiera quiz Klasy algorytmów sortowania?

Quiz Klasy algorytmów sortowania zawiera 15 pytań testowych z możliwością wyboru jednej poprawnej odpowiedzi.

Czy quiz Klasy algorytmów sortowania jest darmowy?

Tak, wszystkie quizy na Odpytywarka.pl są całkowicie darmowe. Możesz rozwiązywać dowolną liczbę quizów bez żadnych opłat.

Jak mogę stworzyć własny quiz?

Wgraj plik PDF na stronie głównej, a nasz system AI automatycznie wygeneruje pytania testowe. Po wygenerowaniu możesz edytować treść pytań i odpowiedzi w panelu quizu.

Podobne quizy

Techniki projektowania algorytmów

Quiz sprawdza znajomość podstawowych technik projektowania algorytmów, takich...

128 15 pytań

Bosch Motronic — budowa i działanie

Quiz sprawdza znajomość budowy, odmian i zasad działania elementów systemu Bo...

30 15 pytań

Eksploatacja urządzeń elektroenergetycznych

Quiz sprawdza wiedzę z zakresu eksploatacji i bezpieczeństwa urządzeń elektro...

29 15 pytań

Levenshtein — embedding i regresja

Krótkie pytania sprawdzające zrozumienie artykułu o osadzeniu odległości Leve...

24 15 pytań

Wróć do panelu | Stwórz własny quiz