Tietojenkäsittelyopin laboratorio

Tik-76.122 Tietorakenteet ja algoritmit Tentti 2.10.95

Merkitse jokaiseen vastauspaperiisi

- Tik-76.122 Tietorakenteet ja algoritmit tentti 2.10.95

- 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) = O(x^2+x)

f(x) = O(x/2)

O(f(x))- O(f(x)) = 0

f(x) < O(x^3)

2) Seuraava C-funktio korottaa luvun x kokonaislukupotenssiin n. Mikä on ohjelman aikakompleksisuus n:n suhteen? Kirjoita rekursioyhtälö, ratkaise se ja ilmoita lopputulos O()-notaatiolla. Pelkkä oikea vastaus ei riitä. (6p)

integer pow(int x, int n) {

switch (n) {

case 0: return 1; break;

case l: return x; break;

default:

if (n&l) /* parillinen tai pariton

return pow(sqr(x), n/2)*x;

else

return pow(sqr(x), n/2);

/* esim. x^9 = (x^2)^4x =((x^2)2)2x

3) a) Miten esittäisit alla olevan puurakenteen binääripuun avulla? (lp)

b) Kirjoita edellisen kohdan yleisen puun solmut jälkijärjestyksessä (Postorder).(lp)

c) Talleta alunperin tyhjään binääriseen hakupuuhun järjestyksessä seuraavat alkiot:

K,L,J,M,I,N,H,O,G,P,F (1p)

d) Kirjoita nyt saadun binäärisen hakupuun puun solmut sisäjärjestyksessä (Inorder). (lp)

e) Oletetaan alunperin tyhjä binäärinen hakupuu. Puuhun pitäisi tallettaa alkiot A,B,C,D,E,F,G,H,I,J,K,L,M,N,O. Missä järjestyksessä alkiot pitäisi tallettaa

jotta lopputuloksena oleva binäärinen hakupuu olisi mahdollisimman tasapainoinen? (2p)

4) Lajittele merkkijono HEPPUHEI nousevaan aakkosjärjestykseen käyttäen kasalajittelua. Esitä kasan sisältö jokaisen operaation jälkeen. (6p)

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

AD, DB, BC, FI, FD, CJ, EF, IG, JI, GH, DG, CH, EH ja JH. Esitä kyseisen graafin 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).