Tietojenkäsittelyopin laboratorio

Tik-76.122 Tietorakenteet ja algoritmit Tentti 27.2.96

Merkitse jokaiseen vastauspaperiisi

- Tik-76.122 Tietorakenteet ja algoritmit tentti 27.2.96

- sukunimi, etunimet, koulutusohjelma

- opintokirjan numero ja allekirjoitus

1) a) Listarakenteiden yhteydessä käytetään usein ylimääräisiä alku- ja loppualkioita

(head- ja z-alkiot). Miksi näin tehdään? Lyhyt vastaus. (2p)

b) Mitä vikaa on seuraavissa O()-notaation merkinnöissä? (4p)

f(x) = 0(x^2+x)

f(x) = O(x/2)

3^x = 0(2^x)

x^2 <= 0(x^3)

2) a) Mitä tarkoittaa abstrakti tietotyyppi? (2p)

b) Esitä merkkijonon ABCCDDDEEEEEFFFFFGGGGGG kirjainten Huffman-oodit. Bittiesitys ilmoitetaan (esimerkiksi) seuraavasti: (4p)

A: 00

B: 010

C: 011

D: 10

E: 11

3) a) Seuraavassa on eräs kasa (heap) esitettynä taulukkomuodossa:

AKEOKKRUTLSUOUZX

Piirrä kasa puumuotoon, poista kasan päällimmäinen alkio ja lisää kasaan F. Esitä välivaihe poiston jälkeen ja lopputulos puumuodossa. (3p)

b) Vertaile tallennusrakenteina keskenään tavallista binääristä hakupuuta (binary search tree) ja tasapainotettuja puita (balanced trees). Mitä hyviä ja huonoja puolia niissä on? Sinun ei tarvitse vertailla eri tasapainotettuja puita keskenään.

(Vastauksen ohjeellinen pituus on noin puoli sivua.) (3p)

4) a) Esitä lajittelun eteneminen lajiteltaessa merkkijonoa HÄÄYÖAIE

aakkosjärjestykseen kun käytetään sijoituslajittelua (insertion sort). (3p)

b) Selitä lyhyesti Quicksort-menetelmän periaate ja luettele perusmenetelmän heikkoudet. Vastaa lyhyesti ja selkeästi. (3p)

5) a) Tarkastellaan suuntaamatonta graafia, johon kuuluvat solmut A - J sekä sännät AF,

AD, DB, BC, FI, FD, CJ, EF, IG, Jl, GH, DG, CH, EH ja JH. Esitä kyseisen graaf in seuraajaluetteloesitys (adjacency list), joka on aakkosjärjestyksessä lähtösolmujen osalta ja seuraajien osalta. Esitä graafi myös matriisimuodossa. (2p)

b) Esitä breadth-first-hakupuu kyseiselle graafille käyttäen pohjana edellä muodostamaasi seuraajaluetteloesitystä. Esitä myös jonon sisältö algoritmin etenemisen aikana. (4p).