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 zadania Wróć 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(K_n)| = n(n − 1)/2, |E(K_m,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 K_n: (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

Zapisz stopień każdego wierzchołka; suma stopni jest równa dwukrotności liczby krawędzi.
W zadaniach o grafach eulerowskich sprawdź, czy graf jest spójny, i policz wierzchołki o nieparzystym stopniu.
Dla drzew użyj n − 1 krawędzi i lematu o uściskach dłoni.
W algorytmie Dijkstry prowadź tabelę tymczasowych odległości i w każdej rundzie zatwierdzaj niezatwierdzony wierzchołek o najmniejszej odległości.
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

Dlaczego programowanie dynamiczne nie daje realnego przyspieszenia sortowania przez scalanie?

ASortowanie przez scalanie nie ma struktury rekurencyjnej
BProgramowanie dynamiczne działa tylko na problemach grafowych, a nie na tablicach
CSortowanie przez scalanie już jest O(n)
DJego podproblemy się nie nakładają, więc nie ma czego ponownie wykorzystać

2.Algorytmy i złożonośćTrudny

Dla którego wariantu problemu plecakowego reguła zachłanna „bierz przedmioty według wartości na jednostkę wagi" zawsze daje optymalną odpowiedź?

AŻadnego z wariantów
BCiągłego (ułamkowego) problemu plecakowego, w którym przedmioty można dzielić
CDyskretnego problemu plecakowego 0/1, w którym przedmioty zawsze trzeba brać w całości
DObu wariantów

3.Struktury danychŚredni

Która metoda rozwiązywania kolizji przechowuje kolidujące klucze w liście w tym samym kubełku?

AŁańcuchowanie (separate chaining)
BSondowanie kwadratowe
CHaszowanie podwójne
DSondowanie liniowe

4.Struktury danychTrudny

Obiekt jest przechowywany jako klucz w mapie mieszającej, a następnie zmienia się pole używane przez jego funkcję mieszającą. Jaki jest prawdopodobny skutek?

AWyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu
BNic się nie zmienia, bo skrót klucza oblicza się tylko raz przy uruchomieniu programu
CMapa zgłasza błąd w chwili zmiany pola
DMapa automatycznie przenosi klucz do nowego kubełka

5.Teoria grafówŚredni

Czy graf spójny ma cykl Eulera, ścieżkę Eulera, która nie jest cyklem, czy żadne z nich? Kliknij odpowiedź.

|V| = 5|E| = 5

1Cykl Eulera
2Ścieżka Eulera, bez cyklu
3ani jedno, ani drugie

6.Teoria grafówTrudny

Ile jest marszów zamkniętych o długości 3, które zaczynają się i kończą w E? Marsz może powtarzać wierzchołki i krawędzie. Nazwij tę liczbę N.

M = macierz sąsiedztwaL = 3

N =

3Roztwory

1.Algorytmy i złożoność

Odpowiedź: D · Jego podproblemy się nie nakładają, więc nie ma czego ponownie wykorzystać

Dlaczego to jest odpowiedź

Połowy w sortowaniu przez scalanie są rozłączne i każdą rozwiązuje się raz; DP pomaga tylko, gdy podproblemy się powtarzają, jak przy liczbach Fibonacciego.

Odpowiedź

D · Jego podproblemy się nie nakładają, więc nie ma czego ponownie wykorzystać

2.Algorytmy i złożoność

Odpowiedź: B · Ciągłego (ułamkowego) problemu plecakowego, w którym przedmioty można dzielić

Dlaczego to jest odpowiedź

Gdy przedmioty można dzielić, wybór najpierw najlepszego stosunku jest optymalny; w problemie 0/1 przedmiot o wysokim stosunku może zablokować lepszą kombinację, więc potrzebne jest programowanie dynamiczne.

Odpowiedź

B · Ciągłego (ułamkowego) problemu plecakowego, w którym przedmioty można dzielić

3.Struktury danych

Odpowiedź: A · Łańcuchowanie (separate chaining)

Dlaczego to jest odpowiedź

Łańcuchowanie utrzymuje listę wiązaną (lub inną strukturę) dla każdego kubełka; adresowanie otwarte szuka innego wolnego miejsca w samej tablicy.

Odpowiedź

A · Łańcuchowanie (separate chaining)

4.Struktury danych

Odpowiedź: A · Wyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu

Dlaczego to jest odpowiedź

Położenie klucza wybrano na podstawie jego starego skrótu; przy nowym skrócie wyszukiwanie przeszukuje niewłaściwy kubełek, więc klucze powinny być niezmienne.

Odpowiedź

A · Wyszukanie obiektu może się nie powieść, bo leży on w kubełku dla starego skrótu

5.Teoria grafów

Odpowiedź: Cykl Eulera

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; K_n 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.

Stopnie

deg(A) = 2, deg(B) = 2, deg(C) = 2, deg(D) = 2, deg(E) = 2

Wierzchołki nieparzyste

Cykl Eulera

Odpowiedź

Cykl Eulera

6.Teoria grafów

Odpowiedź: N = 4

Stopnie: stopień wierzchołka to liczba krawędzi, które się w nim stykają. Każda krawędź ma dwa końce, więc stopnie sumują się do dwukrotności liczby krawędzi: Σ deg(v) = 2|E| (lemat o uściskach dłoni). Liczba wierzchołków o nieparzystym stopniu jest zatem parzysta. K_n ma n(n − 1)/2 krawędzi, graf k-regularny o n wierzchołkach ma nk/2, a drzewo o n wierzchołkach ma n − 1 krawędzi.

Macierz sąsiedztwa

A: 0 0 1 0 0 0

B: 0 0 1 1 1 0

C: 1 1 0 0 1 0

D: 0 1 0 0 1 0

E: 0 1 1 1 0 1

F: 0 0 0 0 1 0

Jeszcze jeden krok

(M³)_EE = 1·0 + 2·1 + 1·1 + 1·1 + 4·0 + 0·1 = 4

Odpowiedź

N = 4

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