Zadania grupa A:

1. Podaj ilustrację podstawowych etapów sortowania elementów tablicy A = [7,3,2,5,5,2,3,7] wg. alg. quicksort. Rozważyć przypadki wyboru elementu podziału:

a) pierwszy element tablicy

b) środkowy element tablicy

Określić czasową złożoność obliczeniową. Porównać schematy wyboru elementu osiowego, oraz podać przypadki ich zastosowania.

 

2. Na rysunku przedstawione jest drzewo binarne z etykietowanymi węzłami.

a) podać rekurencyjny algorytm przechodzenia drzewa metodą preorder.

b) zakładając że "odwiedzanie" węzłów wiąże się z wyprowadzaniem wartości etykiet, podać ich kolejność preorder.

c) Czy rozpatrywane drzewo jest zrównoważonym drzewem AVL? Dowód przeprowadź przez wyznaczenie wspólnego zrównoważenia dla każdego węzła.

 

3. Miasta ABCDE są połączone siecią dróg (mogą być dwukierunkowe lub jednokierunkowe).

układ topologiczny przedstawia graf.

a) zbudować macierz sąsiedztwa węzłów (miast)

b) przedstawić las z wyeksponowanym drzewem (poprzez pogrubienie gałęzi) trawersowania grafu zgodnie z techniką przeszukiwania "w głąb".

c) podać podstawową regułę takiego przeszukiwania.

 

4. Metodą łańcuchową utworzyć tablicę haszowaną (m-elementową) stosując modularną funkcję haszującą postaci h(key) = key mod m. Podać postać tablicy haszowanej dla ustawień ciągu elementów o wartościach: {70, 30, 44, 18, 42, 35, 32, 63, 4, 26}. Założyć 6-el tablicę haszowaną.

 

5. Zastosowanie konstrukcji algorytmów: iteracji, rekurencji oraz metod: przyrostowej, "dziel i rządź", programowania dynamicznego w projektowaniu i specyfikacji algorytmów. Przybliżyć pojęcia, dokonać porównania pod względem uzyskiwanej złożonosci obliczeniowej, prostoty, powszechności w stosowaniu itp. Wnioski oprzeć na przykładach.

 

6. Korzystając z def. Notacji asymptotycznych : O, W, Q wykonać:

a)      pokazać że T(n) = 6n² + 20n = O(n³) oraz T(n) = 6n² + 20n ¹ W(n³)

b)      dla funkcji T(n) = 5n⁵ + 4n⁴ + 6n³ + 2n² +n +7, określić (jeżeli jest) rząd w notacji O, W, Q.

 

7. Dla tablicowej reprezentacji kolejki cyklicznej (bufor kołowy) wykonać następujące operacje: wstawić element o wartości klucza y na koniec kolejki, a następnie przenieść 3 elementy z początku kolejki na jej koniec.

 

8. Dana jest liniowa, jednokierunkowa lista o reprezentacji dowiązaniowej. Zbuduj algorytm który dokona podziału tej listy na dwie części i utworzy z jednej części listę liniową a z drugiej cykliczną. Punkt podziału listy wyjściowej wyznacza pierwsze wystąpienie elementu o wartości klucza x (założyć można ze taki element istnieje). Oszacować złożoność czasową przeprowadzonej operacji.