Algorytmy i Struktury Danych
Zagadnienia do przećwiczenia na egzamin „0” na 30 stycznia 2015 r.
1. Na wybranym przykładzie pokazać w kolejnych krokach sortowanie: mergesort (przez scalanie), quicksort (szybkie), countingsort (przez zliczanie z obliczaniem pozycji na których mają być wpisane liczby), bucketsort (kubełkowe)
2. Na podstawie podanej tablicy zbuduj kopiec i posortuj jego elementy sortowaniem przez kopcowanie.
3. Na podstawie podanej sekwencji utwórz kodowanie Huffmana
4. Zamień podaną postać grafu na: listę sąsiedztwa, macierz sąsiedztwa i podaj kolejność wierzchołków przy przechodzeniu grafu: wszerz, w głąb.
5. Wykorzystując algorytm Dijkstry znajdź najkrótszą ścieżkę w podanym grafie.
6. Znajdź minimalne drzewo rozpinające wykorzystujące algorytm: Kruskala, Prima.
quicksort (szybkie)
mergesort (przez scalanie)
DZIELENIE
SCALANIE
Bucketsort !
1
2
3
4
5
6
7
8
9
10
A
0,12
0,14
0,24
0,25
0,31
0,32
0,39
0,43
0,75
0,98
B
0
Kodowanie huffmana
tworzenie kopca
Sortowanie przez kopcowanie
Lista sąsiedztwa
Macierz sąsiedztwa
Przechodzenie w głąb-Przykład
Tylko pisać V-wierzchołki
Przechodzenie w wszerz-Przykład
...
RezidentRnR