Losowanie pytań na lekcję albo imprezę: zakręć kołem, przeczytaj pytanie na głos i odsłoń odpowiedź.
11 kart z quizu „Algorytmy — informatyka, liceum”: na każdej pytanie i odpowiedź.
- Algorytm sortowania bąbelkowego porównuje i w razie potrzeby zamienia miejscami sąsiednie elementy tablicy.
- PrawdaSortowanie bąbelkowe polega na wielokrotnym porównywaniu sąsiednich elementów i zamianie ich, gdy są w złej kolejności.
- Który algorytm sortowania polega na wielokrotnym wyszukiwaniu najmniejszego elementu w nieposortowanej części tablicy i przestawianiu go na jej początek?
- Sortowanie przez wybórSortowanie przez wybór znajduje minimum w nieposortowanej części i umieszcza je na właściwym miejscu.
- Jak nazywa się algorytm wyszukiwania, który sprawdza kolejno każdy element listy od początku, aż znajdzie szukany? (dwa słowa)
- wyszukiwanie linioweWyszukiwanie liniowe (sekwencyjne) przegląda elementy po kolei, nie wymagając posortowania danych.
- Jaki warunek musi spełniać tablica, aby można było zastosować do niej wyszukiwanie binarne?
- Musi być posortowanaWyszukiwanie binarne opiera się na porównaniu ze środkowym elementem, więc dane muszą być uporządkowane.
- W wyszukiwaniu binarnym po każdym porównaniu ze środkowym elementem zakres poszukiwań zmniejsza się mniej więcej o połowę.
- PrawdaDzięki porównaniu ze środkiem odrzucana jest około połowa elementów, stąd złożoność logarytmiczna.
- Funkcja silnia jest zdefiniowana rekurencyjnie: 0! = 1, n! = n · (n−1)!. Ile wynosi 5!?
- 1205! = 5·4·3·2·1 = 120.
- Jak nazywa się warunek w funkcji rekurencyjnej, który kończy wywołania i nie powoduje kolejnego wywołania funkcji?
- Warunek stopu (przypadek bazowy)Przypadek bazowy (warunek stopu) przerywa rekurencję, dzięki czemu funkcja nie wywołuje się w nieskończoność.
- Jak nazywa się w schemacie blokowym blok w kształcie rombu, w którym sprawdzany jest warunek? (np. „blok …”)
- decyzyjnyRomb w schemacie blokowym oznacza blok decyzyjny (warunkowy) z dwiema ścieżkami: „tak” i „nie”.
- Algorytm o złożoności czasowej O(n²) dla dużych danych działa zwykle szybciej niż algorytm o złożoności O(n log n).
- FałszDla dużych n funkcja n² rośnie szybciej niż n log n, więc algorytm O(n²) jest zwykle wolniejszy.
- Jaka jest typowa złożoność czasowa algorytmu sortowania bąbelkowego dla n elementów w najgorszym przypadku?
- O(n²)Sortowanie bąbelkowe wykonuje dwie zagnieżdżone pętle po około n elementów, więc ma złożoność O(n²).
- Każda poprawna funkcja rekurencyjna musi mieć warunek zakończenia, czyli przypadek bazowy.
- PrawdaBez przypadku bazowego funkcja wywoływałaby samą siebie bez końca, aż do przepełnienia stosu.