Algorytm sekwencyjnego wyszukiwania elementu z wartownikiem polega na założeniu, że
Algorytm sekwencyjnego wyszukiwania elementu z wartownikiem polega na założeniu, że
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź: A
Uzasadnienie i szersze wyjaśnienie:
Wyszukiwanie z wartownikiem (sentinel search) to optymalizacja klasycznego wyszukiwania liniowego (sekwencyjnego). Jej główna idea polega na tym, aby na końcu przeszukiwanej kolekcji tymczasowo umieścić szukany element, czyli „wartownika”. Dzięki temu mamy gwarancję, że pętla przeszukująca zawsze znajdzie szukany element, co pozwala wyeliminować z pętli drugi warunek – sprawdzający, czy nie wyszliśmy poza zakres tablicy. To minimalnie zmniejsza liczbę operacji w każdej iteracji, co może być zauważalne przy bardzo dużych zbiorach danych.
Dlaczego pozostałe odpowiedzi są nieprawidłowe?
- B: Wymóg posortowania dotyczy znacznie szybszego wyszukiwania binarnego. Wyszukiwanie liniowe (z wartownikiem lub bez) działa na zbiorach nieposortowanych.
- C i D: Algorytm działa dla zbiorów o dowolnej wielkości i nie ma żadnych wymagań co do powtarzalności elementów.
Chcesz poćwiczyć całą kwalifikację INF.04?
Egzamin próbny na czas, nauka działami, losowe pytanie albo przegląd całej bazy — wszystko w przeglądarce i bez zakładania konta.
Pojęcia z tego pytania
- Wyszukiwanie liniowe i z wartownikiem (Linear Search)Podstawowy algorytm przeszukiwania tablicy sprawdzający elementy kolejno od początku do końca o złożoności O(n), nie wymagający posortowania danych.
- Wyszukiwanie binarne (Binary Search)Algorytm wyszukiwania w posortowanej tablicy o złożoności O(log n), porównujący szukaną wartość ze środkowym elementem i odrzucający połowę zbioru.
- Pojęcie i Cechy AlgorytmuUporządkowany, skończony i jednoznaczny ciąg instrukcji i kroków postępowania prowadzący do rozwiązania określonego problemu obliczeniowego dla poprawnych danych wejściowych.
Podobne pytania z działu „Algorytmy sortowania i wyszukiwania”
Ten sam obszar materiału z kwalifikacji INF.04. W całej bazie znajdziesz 23 pytań z tego działu.
- #93
Aby zaprojektować zestaw danych do zainicjowania algorytmu sortowania bąbelkowego tablicy, należy zastosować przynajmniej typy:
- #103
Metoda poszukiwań w tablicach posortowanych, która polega na podzieleniu tablicy na kilka bloków i wyszukaniu liniowym tylko w tym bloku, w którym docelowy element może się znajdować, w języku angielskim nosi nazwę
- #129
Który z wymienionych algorytmów działających na tablicy jednowymiarowej ma złożoność obliczeniową O(n2)?
- #143
Strategia budowania algorytmu poprzez podział na dwa lub więcej mniejszych podproblemów tak długo, aż fragmentu staną się proste do bezpośredniego rozwiązania jest metodą:
- #144
Z tabeli przedstawiającej złożoność obliczeniową algorytmów sortowania na dowolnym, dużym, zbiorze wejściowym (ponad 100 elementów) wynika, że najszybszą metodą jest algorytm sortowania: