Algorytmy i Struktury Danych

Zad.1.

Rozmieścić: nazwy dni tygodnia:

PON, WTO, SRO, CZW, PIA, SOB, NIE

w tablicy rozproszonej o wielkości n=9, z funkcją haszującą:

h_i = (Code(klucz) + i ) mod n

Funkcja Code sumuje numery liter nazwy:

A= 1, B= 2, C= 3, D= 4, E= 5, F= 6, G= 7, H= 8, I= 9, J=10, K=11, L=12, M=13, N=14, O=15, P=16, Q=17, R=18, S=19, T=20, U=21, V=22, W=23, X=24, Y=25, Z=26

Zad.2.

Zrealizować operację:

1. Push, Eject

2. Pop, Inject

dla listy zapisanej w reprezentacji dowiązaniowej.

Zad.3.

Dla podanego grafu:

• znaleźć wszystkie minimalne drzewa rozpinające

• utworzyć macierz sąsiedztwa

Zad.4.

Dla ciągu liczb:

20, 30, 50, 40, 70, 60, 100, 90, 80, 150

utworzyć BST, a następnie drzewo to zapisać w postaci leworekursywnej.

Zad.5.

Dla ciągu liczb:

20, 30, 50, 40, 70, 60, 100, 90, 80, 150

utworzyć stóg:

• w postaci drzewa

• w tablicy jednowymiarowej.

Zad.6.

Dla ciągu liczb:

20, 30, 50, 40, 70, 60, 100, 90, 80, 150

utworzyć drzewo sortujące.

Zad.7.

Wyznaczyć złożoność obliczeniową algorytmu sortowania bąbelkowego dla operacji porównywania elementów tablicy.