Podgląd pytania

Pojedyncze pytanie z bazy egzaminacyjnej wraz z poprawną odpowiedzią i wyjaśnieniem. Przeglądaj bez logowania, a gdy będziesz gotowy, sprawdź się w pełnym teście próbnym.

ID: 2736 Algorytmy Średnie
INF.04

Źródło: Arkusze CKE

Jaką strukturę danych stosuje się w algorytmie BFS (przeszukiwanie wszerz)?

Warianty odpowiedzi

  1. A

    Zbiór
  2. B

    Graf
  3. C

    Kolejka
  4. D

    Tablica

Wyjaśnienie

Algorytm BFS działa trochę jak fala rozchodząca się po wodzie. Najpierw odwiedza wszystkich bezpośrednich sąsiadów punktu startowego, potem sąsiadów tych sąsiadów i tak dalej.

Żeby nie pogubić się w kolejności odwiedzania węzłów, BFS musi stosować zasadę FIFO, czyli pierwszy na wejściu jest pierwszym do przetworzenia.

Dokładnie do tego służy struktura kolejki. Wrzucasz do niej sąsiadów do odwiedzenia na koniec, a wyciągasz do przetworzenia zawsze z samego początku.

Sprawdź się w praktyce

Rozwiąż pełny test próbny INF.04 albo wylosuj pojedyncze pytanie na szybką powtórkę.

Test próbny INF.04 Jedno pytanie Własny test

Podobne pytania — Algorytmy

Wszystkie pytania INF.04