Przejdź do treści
Matura 2027 • Zadania praktyczne

Wyszukiwanie i sortowanie

Przed Tobą 10 zadań testowych. Sprawdź, czy Twoja wiedza z działu Wyszukiwanie i sortowanie wystarczy, by zdobyć komplet punktów na maturze.

Pytanie 1 / 10Programowanie
Jaka jest średnia złożoność czasowa najpopularniejszych algorytmów sortowania (takich jak Merge Sort czy Timsort wbudowany w Pythona), w porównaniu do powolnego sortowania bąbelkowego O(n2)O(n^2)?
▸ Wszystkie 10 pytań z wyjaśnieniamiRozwiń, jeśli wolisz przejrzeć zestaw bez rozwiązywania testu.

Zrozumienie złożoności, korzystanie z wyszukiwania binarnego, kluczy sortowania, poprawnej rekurencji i potężnych technik optymalizacji.

1.Jaka jest średnia złożoność czasowa najpopularniejszych algorytmów sortowania (takich jak Merge Sort czy Timsort wbudowany w Pythona), w porównaniu do powolnego sortowania bąbelkowego O(n2)O(n^2)?

  • A.O(1)O(1)
  • B.O(log⁡n)O(\log n)
  • C.O(nlog⁡n)O(n \log n)— poprawna
  • D.O(n)O(n)
Dlaczego: Najlepsze uniwersalne algorytmy sortowania działają w czasie O(nlog⁡n)O(n \log n), co jest znacznie szybsze niż kwadratowe O(n2)O(n^2) dla dużych zbiorów danych (np. dla maturalnych 100 000 elementów). Język Python pod spodem używa zoptymalizowanego algorytmu Timsort o właśnie takiej złożoności.

2.Czym dokładnie różni się wywołanie metody listy `.sort()` od użycia wbudowanej funkcji `sorted()` w Pythonie?

  • A.`.sort()` tworzy nową posortowaną listę, a `sorted()` sortuje listę w miejscu.
  • B.`.sort()` sortuje listę w miejscu (modyfikując ją), a `sorted()` zwraca nową posortowaną kopię.— poprawna
  • C.Nie ma między nimi żadnej różnicy, to absolutne synonimy.
  • D.`.sort()` działa tylko na liczbach, a `sorted()` na tekstach i liczbach.
Dlaczego: Metoda `.sort()` modyfikuje oryginalną listę trwale i zwraca `None` (działa w miejscu, z ang. in-place). Funkcja `sorted()` pobiera listę, pozostawia ją bez najmniejszych zmian i zwraca zupełnie nową, już posortowaną strukturę.

3.Chcesz posortować listę słów `L` nie standardowo (alfabetycznie), lecz po ich długości rosnąco. Jakiego zapisu użyjesz?

  • A.`L.sort(len)`
  • B.`L.sort(key=len)`— poprawna
  • C.`sorted(L, length=True)`
  • D.`L.sort(lambda x: length(x))`
Dlaczego: Parametr nazwany `key` przyjmuje nazwę funkcji (np. wbudowanej funkcji `len`), która zostaje najpierw wywołana dla każdego elementu. Elementy są ostatecznie układane na podstawie wartości zwróconych przez tę podaną funkcję klucza.

4.Jaki jest bezwzględny, krytyczny warunek początkowy, aby móc bezpiecznie i prawidłowo zastosować algorytm wyszukiwania binarnego (dychotomii) na tablicy?

  • A.Tablica musi mieć parzystą liczbę elementów.
  • B.Tablica musi zawierać wyłącznie liczby całkowite.
  • C.Tablica musi być z góry (wcześniej) posortowana.— poprawna
  • D.Wszystkie elementy w przeszukiwanej tablicy muszą być unikalne (brak duplikatów).
Dlaczego: Wyszukiwanie binarne opiera się na odrzucaniu całej połowy przedziału w jednym kroku. Jest to możliwe tylko i wyłącznie wtedy, gdy wiemy, że dane są ściśle uporządkowane (posortowane), dzięki czemu wiemy w którą stronę się kierować (lewo czy prawo).

5.Jeśli tablica ma około miliona (n=1 000 000n=1\ 000\ 000) posortowanych elementów, maksymalnie ile sprawdzeń (w przybliżeniu) wykona wyszukiwanie binarne w najgorszym przypadku?

  • A.Około 1 000 000.
  • B.Około 500 000.
  • C.Około 20.— poprawna
  • D.Około 1 000.
Dlaczego: Złożoność wyszukiwania binarnego to O(log⁡2n)O(\log_2 n). Logarytm o podstawie 2 z miliona wynosi w przybliżeniu zaledwie 20. Oznacza to, że po zaledwie 20 podziałach na pół znajdziemy szukany element lub upewnimy się, że go nie ma.

6.Co jest najczęstszą przyczyną otrzymania na maturze okienka z błędem `RecursionError: maximum recursion depth exceeded` podczas pisania algorytmu rekurencyjnego (np. silni)?

  • A.Próba wyliczenia wyniku z bardzo dużej liczby na raz.
  • B.Brak instrukcji `return` na samym końcu całego kodu.
  • C.Użycie pętli `while` zamiast pętli `for` we wnętrzu funkcji.
  • D.Brak lub błędnie zapisany warunek stopu (tzw. przypadek bazowy).— poprawna
Dlaczego: Każda poprawna funkcja rekurencyjna w programowaniu musi posiadać na górze tzw. warunek stopu (np. `if n <= 1: return n`), który nie zmusza jej do dalszego wywoływania samej siebie. Bez niego program ugrzęźnie w nieskończoności, aż przepełni limit stosu wywołań (call stack).

7.Dlaczego naiwna, klasyczna implementacja rekurencyjna Ciągu Fibonacciego (zwracająca podwójnie `fib(n-1) + fib(n-2)`) jest ekstremalnie nieoptymalna dla dużych wartości `n`?

  • A.Ponieważ zajmuje za dużo cennego miejsca na dysku twardym.
  • B.Ponieważ wykonuje lawinowo w tle mnóstwo powtarzających się obliczeń dokładnie tych samych, mniejszych podproblemów.— poprawna
  • C.Ponieważ w Pythonie rekurencja zawsze dzieli przez zero dla potęg.
  • D.Ponieważ wymaga niepotrzebnego użycia modułu `math` i operacji zmiennoprzecinkowych.
Dlaczego: Klasyczna rekurencja Fibonacciego posiada złożoność aż O(2n)O(2^n). Na przykład chcąc policzyć `fib(6)`, program wywołuje wielokrotnie wyliczenia dla `fib(4)`, `fib(3)`, itd., marnując czas na to, co policzył już chwilę wcześniej. Konieczne jest użycie pętli lub memoizacji (słownika).

8.Masz podaną olbrzymią tablicę i program w tysiącach pętli każe podawać sumy jej przedziałów od indeksu `A` do indeksu `B`. Jaka technika maturalna zapobiegnie tu błędom limitu czasu (TLE)?

  • A.Sortowanie bąbelkowe.
  • B.Metoda dwuwymiarowej gąsienicy.
  • C.Tablica sum prefiksowych.— poprawna
  • D.Rozszerzony Algorytm Euklidesa.
Dlaczego: Sumy prefiksowe to technika jednorazowego, początkowego wyliczenia rosnącej sumy całej tablicy w pomocniczej liście. Dzięki temu późniejsza odpowiedź na zapytanie o to, jaka jest suma z przedziału `[A, B]` polega tylko na błyskawicznym i pojedynczym odjęciu `S[B] - S[A-1]` w czasie O(1)O(1).

9.Na czym polega ogólne podejście zachłanne (z ang. greedy algorithms) używane np. w popularnym algorytmie wydawania reszty z użyciem najmniejszej liczby banknotów?

  • A.Na wstępnym wygenerowaniu wszystkich możliwych kombinacji wydań i przefiltrowaniu ich w celu znalezienia najkrótszej.
  • B.Na ucinaniu resztek do wydania i ich matematycznym zaokrąglaniu.
  • C.Na całkowicie losowym wybieraniu banknotów aż do zrównania się z resztą.
  • D.Na zawsze wybieraniu lokalnie najlepszego, dopuszczalnego i największego nominału w danym kroku, powtarzając to do wyzerowania kwoty.— poprawna
Dlaczego: Algorytm zachłanny zawsze i na bieżąco podejmuje w danym kroku operację, która tu i teraz wydaje mu się najkorzystniejsza (wydaje największy z możliwych banknot który mieści się w pozostałej kwocie), bez powrotów do sprawdzania globalnych decyzji wstecz.

10.W jakiego typu maturalnych zadaniach z tablicami (lub napisami) idealnie sprawdza się technika dwóch wskaźników, tzw. metoda gąsienicy?

  • A.Błyskawiczne szukanie na dużych ciągach spójnego podciągu spełniającego określony warunek (np. konkretną sumę), eliminujące powolne używanie dwóch zagnieżdżonych pętli for.— poprawna
  • B.Sortowanie dużych tablic złożonych wyłącznie ze zagnieżdżonych stringów.
  • C.Konwersja na inne systemy liczbowe bezpośrednio w pamięci dla oszczędności czasu.
  • D.Symulacja operacji bankowych w zadaniach bazodanowych SQL.
Dlaczego: Metoda gąsienicy eliminuje potęgującą się złożoność czasową O(n2)O(n^2) wchodzącą z użycia dwóch zagnieżdżonych pętli dla spójnych przedziałów. Polega na stworzeniu dwóch zmiennych (tzw. głowa i ogon), które pełzają po liście wyłącznie do przodu w czasie liniowym O(n)O(n) i badają dany podciąg.

O czym musisz pamiętać w zadaniach z Programowania?

Zadania z programowania na maturze to sprawdzian logicznego myślenia, znajomości klasycznych algorytmów (np. sortowania, wyszukiwania, operacji na liczbach i napisach) oraz czytania ze zrozumieniem.

  • ✓ Pamiętaj, że w Pythonie indeksowanie struktur (jak listy czy napisy) zaczyna się od 0, natomiast w pseudokodzie CKE najczęściej od 1.
  • ✓
    Zwracaj szczególną uwagę na poprawne wczytywanie danych – pamiętaj o rzutowaniu na odpowiednie typy (np. int()) i pozbywaniu się białych znaków (strip()).
  • ✓ Dbaj o złożoność obliczeniową. Jeśli to możliwe, unikaj wielokrotnie zagnieżdżonych pętli, aby Twój program zdążył się wykonać w regulaminowym czasie.

Strategia Maturalna (Python / Algorytmy):

"Zanim rzucisz się do pisania kodu na komputerze, zrozum problem na kartce papieru. Zawsze korzystaj z danych z pliku przyklad.txtw trakcie testowania swoich rozwiązań. Jeśli odpowiedź zgadza się z plikiem z odpowiedziami do przykładu, masz ogromne szanse, że Twój kod zadziała poprawnie również dla głównych danych z arkusza."

To nie koniec powtórki!

Przećwicz kolejny zestaw pytań i utrwal składnię oraz algorytmy.

Dalej: Fundamenty i Składnia Pythona →
Wolisz zadania przy komputerze? Zobacz Pewniaki Algorytmiczne →