BFS i DFS w praktyce

Autor: admin

Quiz sprawdza rozumienie różnic, zastosowań i implementacji algorytmów BFS i DFS opisanych w dokumencie. Pytania odnoszą się do złożoności, kolejności odwiedzin, struktur pomocniczych oraz typowych pułapek.

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

Rozwiąż quiz

Twoje imię

Rozwiąż quiz

1 Jaką strukturę danych używa BFS do przechowywania frontu przeszukiwania?

A kolejka FIFO B drzewo binarne C hasz tablica odwiedzonych wierzchołków D stos LIFO

2 Jaką strukturę danych sugeruje dokument w Pythonie jako standardowy wybór dla BFS?

A słownik mapujący wierzchołki na dystanse B heapq jako priorytetowa kolejka C collections.deque z popleft() D zwykła lista z pop(0) pomimo kosztu przesuwania elementów

3 Jaka jest złożoność czasowa BFS i DFS dla grafu według dokumentu?

A O(N^2) B O(V + E) C O(V^2) D O(E log V)

4 Jak dokument opisuje zachowanie DFS rekurencyjnego względem call stacka?

A stos wywołań przechowuje ścieżkę od korzenia do aktualnego węzła B rekurencja zastępuje visited set i zawsze zapobiega cyklom C call stack mapuje węzły na dystanse od korzenia D call stack przechowuje wszystkie sąsiadujące węzły na danym poziomie

5 Jaka jest kolejność odwiedzin BFS dla przykładowego drzewa z korzeniem A?

A A, B, C, D, E, F B A, D, B, E, C, F C A, C, B, F, D, E D A, B, D, E, C, F

6 Jaka jest kolejność odwiedzin DFS preorder dla tego samego drzewa?

A A, C, F, B, D, E B A, B, D, E, C, F C A, B, C, D, E, F D D, E, B, F, C, A

7 Dlaczego w BFS dla grafu często oznacza się wierzchołek jako odwiedzony już przy dodaniu do kolejki?

A ponieważ oznaczenie przy zdjęciu ze stosu prowadzi do błędów B bo wtedy można policzyć dystans bez parentów C żeby nie włożyć go kilka razy do kolejki D aby zachować porządek LIFO

8 Jaki problem rozwiązuje użycie visited w DFS na grafie skierowanym, oprócz zapobiegania ponownym odwiedzinom?

A pozwala BFS znaleźć najkrótszą ścieżkę w grafie ważonym B umożliwia obliczenie średniej głębokości poziomów C pomaga wykryć cykl rozróżniając wierzchołek na aktualnym stosie D zastępuje potrzebę stosu przy iteracyjnym DFS

9 Jak dokument definiuje sytuację wykrywania cyklu podczas DFS rekurencyjnego?

A gdy stos iteracyjny zawiera duplikaty B trafiasz na wierzchołek, który jest na aktualnym stosie rekurencji C trafiasz na wierzchołek, który jest w visited od dawna D gdy kolejka FIFO staje się pusta przed odwiedzeniem wszystkich wierzchołków

10 Dlaczego użycie list.pop(0) jest wymienione jako pułapka w implementacji BFS w Pythonie?

A bo pop(0) nie zachowuje kolejności FIFO B bo list.pop(0) usuwa losowy element zamiast pierwszego C bo przesuwa elementy i jest gorszym wyborem niż deque D bo lista nie może zawierać obiektów zagnieżdżonych

11 W iteracyjnym DFS, czemu często dodaje się dzieci na stos w odwróconej kolejności?

A żeby uniknąć potrzeby visited w grafie z cyklami B żeby zamienić DFS w BFS przy użyciu stosu C żeby zmniejszyć pamięć przez skalowanie od końca D żeby zachować kolejność zgodną z rekurencyjnym DFS lewy→prawy

12 Co dokument uznaje za naturalny sygnał do użycia BFS w zadaniu?

A walidacja BST i sumy ścieżek B zadania wymagające topologicznego sortowania zależności C problemy z rekurencyjną definicją dla każdego poddrzewa D zapytania o poziomy, minimalną liczbę ruchów lub najbliższy element

13 Co dokument podkreśla jako ograniczenie zwykłego BFS przy krawędziach o różnych wagach?

A BFS zawsze wybierze trasę z najmniejszą liczbą wierzchołków, co jest tym samym co najtańsza trasa B BFS wymaga heapq, by działać poprawnie z wagami C BFS nie da się uruchomić na grafach skierowanych D BFS liczy kroki, nie sumę wag, więc może pominąć tańszą ścieżkę

14 Jakie typowe zadanie dokument przypisuje do DFS na drzewie?

A path sum i liczenie wartości w poddrzewie B znalezienie najkrótszej ścieżki w nieskierowanym grafie o równych wagach C rozwiązywanie minimalnego pokrycia wierzchołków za pomocą kolejki D obliczanie średniej na poziomie szerokości drzewa

15 Jaki wynik wypisze kod BFS z dokumentu dla podanego tree, zgodnie z komentarzem?

A ['A', 'B', 'C', 'D', 'E', 'F'] B ['A', 'B', 'D', 'E', 'C', 'F'] C ['A', 'C', 'B', 'F', 'D', 'E'] D ['F', 'C', 'E', 'D', 'B', 'A']

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 BFS i DFS w praktyce?

Quiz BFS i DFS w praktyce zawiera 15 pytań testowych z możliwością wyboru jednej poprawnej odpowiedzi.

Czy quiz BFS i DFS w praktyce 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...

127 15 pytań

Bosch Motronic — budowa i działanie

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

29 15 pytań

Eksploatacja urządzeń elektroenergetycznych

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

28 15 pytań

Levenshtein — embedding i regresja

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

23 15 pytań

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