Algorytmy i struktury danych: zestaw na powtórkę

Wzory, najważniejsze kroki metod dla każdego tematu i 6 zadań do ćwiczenia, z pełnymi rozwiązaniami na końcu.

Nowe zadaniaWróć do przedmiotu

W oknie drukowania wybierz „Zapisz jako PDF”, aby zachować kopię na swoim urządzeniu.

1Wzory i metody

Teoria grafów

Lemat o uściskach dłoni
Σ deg(v) = 2|E|
Grafy pełne
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Graf regularny
|E| = n·k/2
Drzewo i las
|E| = n − 1, |E| = n − c
Liście drzewa
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
cykl: wszystkie stopnie parzyste; ścieżka: dokładnie 2 stopnie nieparzyste
Cykle Hamiltona w Kn
(n − 1)!/2
Aktualizacja w algorytmie Dijkstry
d(v) = min(d(v), d(u) + w(u, v))
Marsze o długości L
(Mᴸ)ij

Metoda

  1. Zapisz stopień każdego wierzchołka; suma stopni jest równa dwukrotności liczby krawędzi.
  2. W zadaniach o grafach eulerowskich sprawdź, czy graf jest spójny, i policz wierzchołki o nieparzystym stopniu.
  3. Dla drzew użyj n − 1 krawędzi i lematu o uściskach dłoni.
  4. W algorytmie Dijkstry prowadź tabelę tymczasowych odległości i w każdej rundzie zatwierdzaj niezatwierdzony wierzchołek o najmniejszej odległości.
  5. Dla minimalnego drzewa rozpinającego posortuj krawędzie według wagi i pomijaj każdą krawędź zamykającą cykl (Kruskal) albo rozbudowuj jedno drzewo od wierzchołka startowego (Prim).

2Zadania do ćwiczenia

1.Algorytmy i złożonośćŚredni

Przeszukiwanie wszerz w grafie nieważonym znajduje:

  1. AMinimalne drzewo rozpinające
  2. BPorządek topologiczny w dowolnym grafie
  3. CNajkrótsze ścieżki w grafach zawierających ujemne wagi krawędzi
  4. DNajkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego
2.Algorytmy i złożonośćTrudny

Które ograniczenie jest poprawne dla log(n!)?

  1. AΘ(n log n)
  2. BΘ(n)
  3. CΘ(n²)
  4. DΘ(log n)
3.Struktury danychŚredni

Jak znaleźć najmniejszy klucz w binarnym drzewie poszukiwań?

  1. AIść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
  2. BSprawdzić tylko korzeń
  3. CIść od korzenia do prawych dzieci, aż zabraknie prawego dziecka
  4. DOdwiedzić każdy liść i porównać je
4.Struktury danychTrudny

Jak wykryć, czy lista jednokierunkowa zawiera cykl, używając O(1) dodatkowej pamięci?

  1. AZapisywać każdy odwiedzony węzeł w zbiorze mieszającym
  2. BPrzesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
  3. CPosortować listę i szukać duplikatów
  4. DLiczyć węzły, aż liczba przekroczy pole z długością listy
5.Teoria grafówŚredni

Graf spójny: liczba wierzchołków 19, liczba krawędzi 20. Ile krawędzi k trzeba usunąć, aby zostało drzewo rozpinające?

|V| = 19|E| = 20
k =
6.Teoria grafówTrudny
921113151561ABCDEF

Użyj algorytmu Dijkstry, aby znaleźć długość d(F) najkrótszej ścieżki z A do F w grafie ważonym.

start: Akoniec: F
d(F) =

3Roztwory

1.Algorytmy i złożoność

Odpowiedź: D · Najkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego

Dlaczego to jest odpowiedź

BFS odwiedza wierzchołki w kolejności odległości (w krawędziach) od źródła, więc znajduje najkrótsze ścieżki w grafie nieważonym w czasie O(V + E).

Odpowiedź

D · Najkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego
2.Algorytmy i złożoność

Odpowiedź: A · Θ(n log n)

Dlaczego to jest odpowiedź

log(n!) ≤ n log n, a n / 2 największych czynników daje log(n!) ≥ (n / 2) log(n / 2); dlatego sortowanie przez porównania wymaga Ω(n log n).

Odpowiedź

A · Θ(n log n)
3.Struktury danych

Odpowiedź: A · Iść od korzenia do lewych dzieci, aż zabraknie lewego dziecka

Dlaczego to jest odpowiedź

W drzewie nie ma klucza mniejszego niż w skrajnie lewym węźle, więc jest on minimum; koszt jest proporcjonalny do wysokości.

Odpowiedź

A · Iść od korzenia do lewych dzieci, aż zabraknie lewego dziecka
4.Struktury danych

Odpowiedź: B · Przesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają

Dlaczego to jest odpowiedź

W algorytmie Floyda, jeśli jest cykl, szybki wskaźnik w końcu dogania wolny; w przeciwnym razie szybki wskaźnik dochodzi do null.

Odpowiedź

B · Przesuwać jeden wskaźnik o jeden krok, a drugi o dwa i sprawdzać, czy się spotkają
5.Teoria grafów

Odpowiedź: k = 2

Euler, Hamilton i drzewa: graf spójny ma cykl Eulera (każda krawędź raz, powrót do startu), gdy każdy wierzchołek ma stopień parzysty, oraz ścieżkę Eulera, która nie jest cyklem, gdy dokładnie dwa wierzchołki mają stopień nieparzysty; ścieżka biegnie wtedy od jednego wierzchołka nieparzystego do drugiego. Cykl Hamiltona odwiedza każdy wierzchołek raz; Kn ma ich (n − 1)!/2. Drzewo o n wierzchołkach ma n − 1 krawędzi, a graf spójny o m krawędziach zachowuje drzewo rozpinające po usunięciu m − n + 1 krawędzi.

Krawędzie drzewa rozpinającego

19 − 1 = 18

Krawędzie do usunięcia

k = 20 − 18 = 2

Odpowiedź

k = 2
6.Teoria grafów

Odpowiedź: d(F) = 10

Najkrótsze ścieżki i drzewa rozpinające: algorytm Dijkstry zatwierdza jeden wierzchołek na rundę: niezatwierdzony wierzchołek o najmniejszej tymczasowej odległości. Jego odległość jest wtedy ostateczna, a każdy sąsiad v dostaje d(v) = min(d(v), d(u) + w(u, v)). Algorytm Kruskala buduje minimalne drzewo rozpinające, biorąc krawędzie od lekkich do ciężkich i pomijając każdą, która zamknęłaby cykl; algorytm Prima rozbudowuje jedno drzewo od wierzchołka startowego, zawsze dodając najlżejszą krawędź wychodzącą z niego. Drzewo rozpinające o n wierzchołkach ma n − 1 krawędzi.

Algorytm Dijkstry runda po rundzie

Każdy wiersz: zatwierdzony wierzchołek, jego ostateczna odległość oraz sąsiedzi, których odległość się poprawia.

A (0): B: 9, C: 2
C (2): B: 3, E: 15
B (3): D: 4, E: 4
D (4): F: 19
E (4): F: 10
F (10)

Najkrótsza ścieżka

A → C → B → E → F
d(F) = 10

Odpowiedź

d(F) = 10

ExamProblems · examproblems.com/courses/data-structures-and-algorithms