- w razie pytań i/lub wątpliwości -> mejle na eskę
- nulle na drzewkach to nulle, a nie wierzchołki z etykietą null
- wersja .doc by Rappen (niezsynchronizowana z tą stroną): tutaj
- UWAGA: jako że pytania typu złożoność obliczeniowa i pamięciowa budzą trochę kontrowersji, piszę na wstępie: są one zrobione z założeniem że: złożoność obliczeniowa = max(złożoność czasowa, złożoność pamięciowa). W wykładzie dr. Chrząstowskiego i na wiki złożoność obliczeniowa składa się ze złożoności czasowej i pamęciowej, więc siłą rzeczy musi być co najmniej tak duża, jak jej składowe (choć i tak w sumie sa nieporównywalne)... Jeśli jest to złe założenie, to we wszystkich tego typu pytaniach jedyną poprawną odpowiedzią jest podpunkt, że mogą być sobie równe. Tyle.
przydatne linki:
- B-drzewo:
* wg niektórych źródeł 'b' w 'b-drzewie' znaczy balanced (zrównoważone). B-drzewo z definicji jest zrównoważone. Szczególną własnością b-drzewa jest jego szerokość/rozłożystośc. W b-drzewie każdy wierzchołek poza korzeniem musi mieć n...2n+1 węzłów potomnych. Wierzchołek drzewa binarnego z definicji ma <= 2 węzły potomne, a drzewo AVL z definicji jest drzewem binarnym
- Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi: a->b, a->c, b->a, b->c, c->a, c->b. Jest on:
* wiki: Graf nazywamy spójnym, jeśli dla każdej pary wierzchołków istnieje marszruta je łącząca. Zatem nie jest spójny (z powodu wierzchołka D)
wiki: Graf pełny jest grafem prostym, w którym dla każdej pary węzłów istnieje krawędź je łącząca. Zatem nie jest pełny (jw.).
Drzewo to graf spójny bez cykli, więc dany graf również nie jest drzewem - Wstawiamy do pustego drzewa BST kolejno: 6 0 5 3 1 4 2. Wypisując wartości węzłów przy przejściu tego drzewa w porządku postorder, otrzymamy:
- Listę, ze zmodyfikowaną operacją get, która przesuwa żądany element na początek listy:
* szukając na liście elementu, trzeba ją całą przeszukiwać od początku, zatem im częściej będziemy szukali elementu (grupy elementów) znajdującego się na początku, tym lepiej dla nas. Wrzucanie wszystkich elementów na początek nam nic nie da, bo średnio i tak będzie dany element w środku.
- Wyznaczenie operacji(i) dominującej/ych jest potrzebne do określenia:
* złożoność pamięciowa raczej nie jest określona przez operacje dominujące. Wyjątkiem są algorytmy rekurencyjne. Biorąc je pod uwagę zaznaczyłbym wszystko.
- Wstawiamy do pustego drzewa BST kolejno: 1 0 3 4 6 2 5. Wypisując wartości węzłów przy przejściu drzewa w porządku inorder, otrzymamy:
* inOrder jest zawsze posortowany
- Mamy graf nieskierowany: a--b, b--c, c--a. Wykonujemy na nim DFS z punktu "a" i oznaczamy czasy rozpoczęcia i zakończenia. Notując x (p/f), gdzie x-wierzchołek, p-czas rozpoczęcia, f-czas zakończenia przetwarzania, możemy otrzymać:
* jak dla mnie a(0,5), b(1,4), c(2,3)
- Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, b->c, c->d, d->a.
* ma cykl, więc nie jest acykliczny i nie jest drzewem. Na graf pełny trochę mu brakuje krawędzi
- Mamy graf skierowany złożony z wierzchołków {a,b} i krawędzi a->b, b->a. Jest on:
* jest pełny i spójny, ma cykl
- Mamy graf skierowany złożony z wierzchołków {a} i krawędzi a->a. Jest on:
* za wiki: Graf pełny jest grafem prostym, w którym dla każdej pary węzłów istnieje krawędź je łącząca. Graf prosty - graf bez pętli i krawędzi wielokrotnych. Zatem nie jest grafem pełnym (ale chyba trzeba jeszcze zajrzeć do wykładu dr Chrzastowskiego)
- Mamy graf skierowany złożony z wierzchołków {a,b,c,d} i krawędzi a->b, b->a, c->d, d->c. Jest on:
* graf jest dwudzielny, więc nie jest spójny, więc nie jest drzewem i tym bardziej nie jest pełny
- Listę, ze zmodyfikowaną operacją get, który przesuwa żądany element na koniec listy:
* Jak w przypadku przesuwania na początek, tyle że na odwrót;) generalnie opłaca się, jesli dzięki temu już nie będziemy musieli przez nie 'przechodzić' przeszukując listę. Dzieje się tak wyłacznie w przypadku, gdy szukamy różnych elementów
- Które z niżej wymienionych wymagają co najmniej O(n) dodatkowej pamięci:
- Porównując (dla danego algorytmu) złożoność pesymistyczną pamięciową z oczekiwaną obliczeniową:
- Porównując (dla danego algorytmu) złożoność pesymistyczną pamięciową z oczekiwaną pamięciową:
-
