Wskaż jakiemu przechodzeniu drzewa binarnego odpowiada algorytm DFS? Możliwe odpowiedzi: 1. pre-order, 2. post-order, 3. in-order, 4. level-order
R5qLUiA0lAtnE1
Ćwiczenie 2
Ile wynosi złożoność pamięciowa algorytmu przeszukiwania grafu w głąb. Możliwe odpowiedzi: 1. , 2. , 3. , 4.
2
Ćwiczenie 3
RLzJa31NstcGf
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wersja rekurencyjna:
Linia 1. funkcja drzewoBinarneDFS otwórz nawias okrągły korzeń zamknij nawias okrągły.
Linia 2. jeżeli korzeń wykrzyknik znak równości null dwukropek.
Linia 3. oznacz węzeł cudzysłów korzeń cudzysłów jako odwiedzony.
Linia 4. drzewoBinarneDFS otwórz nawias okrągły lewe dziecko korzenia zamknij nawias okrągły.
Linia 5. drzewoBinarneDFS otwórz nawias okrągły prawe dziecko korzenia zamknij nawias okrągły.
funkcja drzewoBinarneDFS(korzeń)
jeżeli korzeń != null:
oznacz węzeł "korzeń" jako odwiedzony
drzewoBinarneDFS(lewe dziecko korzenia)
drzewoBinarneDFS(prawe dziecko korzenia)
Wersja iteracyjna:
Linia 1. funkcja iteracyjneDrzewoBinarneDFS otwórz nawias okrągły korzeń zamknij nawias okrągły.
Linia 2. utwórz pusty stos cudzysłów stos cudzysłów.
Linia 3. dodaj wierzchołek cudzysłów korzeń cudzysłów na stos.
Linia 4. dopóki rozmiar otwórz nawias okrągły stos zamknij nawias okrągły zamknij nawias ostrokątny 0 wykonuj dwukropek.
Linia 5. v ← zdejmij wierzchołek z góry stosu.
Linia 6. oznacz węzeł cudzysłów v cudzysłów jako odwiedzony.
Linia 7. jeżeli istnieje prawe dziecko węzła cudzysłów v cudzysłów dwukropek.
Linia 8. dodaj prawe dziecko węzła cudzysłów v cudzysłów na stos.
Linia 9. jeżeli istnieje lewe dziecko węzła cudzysłów v cudzysłów dwukropek.
Linia 10. dodaj lewe dziecko węzła cudzysłów v cudzysłów na stos.
funkcja iteracyjneDrzewoBinarneDFS(korzeń)
utwórz pusty stos "stos"
dodaj wierzchołek "korzeń" na stos
dopóki rozmiar(stos) > 0 wykonuj:
v ← zdejmij wierzchołek z góry stosu
oznacz węzeł "v" jako odwiedzony
jeżeli istnieje prawe dziecko węzła "v":
dodaj prawe dziecko węzła "v" na stos
jeżeli istnieje lewe dziecko węzła "v":
dodaj lewe dziecko węzła "v" na stos
1
RVRgheiNKi5tU21
Ćwiczenie 4
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.
2
Ćwiczenie 4
Opisz krótko, na czym polega algorytm przeszukiwania w głąb (DFS).
R8LDFyNivBV15
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
2
Ćwiczenie 5
R1RzPvNgEELyk2
Uporządkuj fragmenty pseudokodu iteracyjnego algorytmu DFS. Elementy do uszeregowania: 1. dopóki stack.size() > 0 wykonuj, 2. visited[v] ← True, 3. stack.push(start), 4. utwórz pusty stos "stack", 5. jeżeli visited[v] == False, 6. dla każdego "w" z adjList[v] wykonuj, 7. v ← stack.pop(), 8. stack.push(w)<, 9. Funkcja IterativeDFS(start)
Uporządkuj fragmenty pseudokodu iteracyjnego algorytmu DFS. Elementy do uszeregowania: 1. dopóki stack.size() > 0 wykonuj, 2. visited[v] ← True, 3. stack.push(start), 4. utwórz pusty stos "stack", 5. jeżeli visited[v] == False, 6. dla każdego "w" z adjList[v] wykonuj, 7. v ← stack.pop(), 8. stack.push(w)<, 9. Funkcja IterativeDFS(start)
R178h8Gl2W1uO3
Ćwiczenie 6
Kiedy algorytm przeszukiwania grafu w głąb jest kompletny? Możliwe odpowiedzi: 1. Nie zawsze, 2. Zawsze, 3. Nigdy
R4nvnNGZQ70VV3
Ćwiczenie 7
Uzupełnij tekst tak, aby powstało stwierdzenie zawsze prawdziwe. Jeśli algorytm przeszukiwania w głąb oznaczył wszystkie 10 wierzchołków grafu jako odwiedzone, oznacza, to że graf zawierz co najmniej Tu uzupełnij krawędzi.
Uzupełnij tekst tak, aby powstało stwierdzenie zawsze prawdziwe. Jeśli algorytm przeszukiwania w głąb oznaczył wszystkie 10 wierzchołków grafu jako odwiedzone, oznacza, to że graf zawierz co najmniej Tu uzupełnij krawędzi.
3
Ćwiczenie 8
Zapisz za pomocą pseudokodu algorytm, który metodą DFS znajdzie dowolny cykl w grafie skierowanym.
Specyfikacja:
Dane:
listaSasiedztwa – lista sąsiedztwa reprezentująca przeszukiwany graf skierowany
V – liczba naturalna dodatnia; liczba wierzchołków grafu
Wynik:
Program na wyjście standardowe wypisuje kolejno wierzchołki znalezionego cyklu, lub komunikat: „Nie ma cyklu w podanym grafie skierowanym”, jeżeli żaden cykl nie zostanie znaleziony.
Rauk0Qxf9JHuQ
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Linia 1. graf reprezentuje lista sąsiedztwa cudzysłów listaSasiedztwa cudzysłów.
Linia 2. utwórz tablicę cudzysłów odwiedzone cudzysłów o V elementach.
Linia 4. funkcja znajdzCykl otwórz nawias okrągły start zamknij nawias okrągły dwukropek.
Linia 6. ustaw wszystkie elementy tablicy cudzysłów odwiedzone cudzysłów na fałsz.
Linia 7. utwórz tablicę cudzysłów poprzednie cudzysłów o V elementach.
Linia 8. utwórz pusty stos cudzysłów stos cudzysłów.
Linia 9. dodaj wierzchołek cudzysłów start cudzysłów na stos.
Linia 11. start ← minus 1.
Linia 13. dopóki rozmiar otwórz nawias okrągły stos zamknij nawias okrągły zamknij nawias ostrokątny 0 wykonuj dwukropek.
Linia 14. v ← zdejmij wierzchołek z góry stosu.
Linia 15. jeżeli odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości prawda dwukropek.
Linia 16. start ← v.
Linia 17. przerwij pętlę.
Linia 18. jeżeli odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości fałsz dwukropek.
Linia 19. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy ← prawda.
Linia 20. dla każdego cudzysłów w cudzysłów z listaSasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy wykonuj dwukropek.
Linia 21. poprzednie otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości v.
Linia 22. dodaj wierzchołek cudzysłów w cudzysłów na stos.
Linia 24. jeżeli start wykrzyknik znak równości minus 1 dwukropek.
Linia 25. v ← start.
Linia 26. wykonuj dwukropek.
Linia 27. wypisz v plus cudzysłów otwórz nawias ostrokątny minus cudzysłów.
Linia 28. v ← poprzednie otwórz nawias kwadratowy v zamknij nawias kwadratowy.
Linia 29. dopóki v wykrzyknik znak równości start.
Linia 30. w przeciwnym razie dwukropek.
Linia 31. print otwórz nawias okrągły cudzysłów Nie ma cyklu w podanym grafie skierowanym cudzysłów zamknij nawias okrągły.
graf reprezentuje lista sąsiedztwa "listaSasiedztwa"
utwórz tablicę "odwiedzone" o V elementach
funkcja znajdzCykl(start):
ustaw wszystkie elementy tablicy "odwiedzone" na fałsz
utwórz tablicę "poprzednie" o V elementach
utwórz pusty stos "stos"
dodaj wierzchołek "start" na stos
start ← -1
dopóki rozmiar(stos) > 0 wykonuj:
v ← zdejmij wierzchołek z góry stosu
jeżeli odwiedzone[v] = prawda:
start ← v
przerwij pętlę
jeżeli odwiedzone[v] = fałsz:
odwiedzone[v] ← prawda
dla każdego "w" z listaSasiedztwa[v] wykonuj:
poprzednie[w] = v
dodaj wierzchołek "w" na stos
jeżeli start != -1:
v ← start
wykonuj:
wypisz v + "<-"
v ← poprzednie[v]
dopóki v != start
w przeciwnym razie:
print("Nie ma cyklu w podanym grafie skierowanym")