1) Binääriset hakupuut (2p + 4p + 4p)

a) Binäärinen hakupuu ei välttämättä ole tasapainotettu, vaan sen muoto voi olla hyvinkin vaihteleva. Jos binäärisen hakupuun korkeus on h, niin kuinka monta alkiota puussä vähintään on? Entä enintään?

b) Tarkastellaan tilannetta, jossa n-alkioisesta binäärisestä hakupuusta haetaan sellaista avainta, jota ei ole talletettu puuhun. Mikä on tällöin pahimman tapauksen aikakompleksisuus alkioiden määrän n suhteen käyttäen iso O –notaatiota? Entä parhaan tapauksen? Perustele molemmat vastauksesi.

c) Esitä pseudokoodilla algoritmi TREE-SUCCESSOR(x), joka etsii solmualkion x seuraajan binäärisestä hakupuusta. Solmualkion x seuraaja on sellainen solmualkio y, että key[y] on pienin puuhun talletettu key[x]-arvoa suurempi avain.

2) Hakurakenteet (4p + 4p + 2p + 4p + 4p)

a) Määrittele käsite B-puu.

b) Esitä 2-3-4-puun kehittyminen, kun alun perin tyhjään puuhun talletetaan avaimet F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z ja E. Riittää, kun esität tilanteen ennen kunkin solmun halkaisua ja lopullisen puun.

c) Selvitä lyhyesti mitä hajautuksen yhteydessä tarkoitetaan avoimella osoituksella.

d) Talleta avaimet 13, 47, 20, 4, 96, 65, 11, 60, 33 ja 48 tässä järjestyksessä hajautustauluun käyttämällä kaksoishajautusta. Hajautustaulun koko on m = 13. Hajautusfunktiot ovat h1(k) = (k + 1) mod m ja h2(k) = (k mod (m – 1)) + 1.

e) Pohdi mitä etuja voidaan hakurakenteen toteutuksessa saavuttaa yhdistämällä jokin hakupuu ja hajautusmenetelmä toisiinsa.

3) Verkot (2p + 8p + 4p)

a) Selitä lyhyesti, mitä tarkoitetaan yhtenäisellä suuntaamattomalla verkolla.

b) Kirjoita algoritmi (anna pseudokoodi), joka käy annetun yhtenäisen suuntaamattoman verkon G=(V, E) läpi leveyssuuntaisesti lähtien solmusta s kuuluu joukkoon V.

c) Analysoi algoritmisi pahimman tapauksen aikavaatimus sekä tilankäyttö.

4) Ajankäyttö (0p)

Montako minuuttia käytit tämän välikokeen tekemiseen?