Tietojenkäsittelyopin laboratorio

Tik-76.122 Tietorakenteet ja algoritmit Tentti 28.11.95

Merkitse jokaiseen vastauspaperiisi

- Tik-76.122 Tietorakenteet ja algoritmit tentti 28.11.95

- sukunimi, etunimet, koulutusohjelma

- opintokirjan numero ja allekirjoitus

1) a) Järjestä seuraavat funktiot Big-Oh-notaation mukaiseen kasvujarjestykseen. (3p)

n n^1,01 n^2 n log n

n log log n n (log n)^2 2^n log n

b) Mikä on seuraavan, postfix-muodossa olevan lausekkeen arvo?

8 3 1 2 * + 4 + 6 + + 7 5 * *

Huom. syötettävät operandit ovat yksinumeroisia. (3p)

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 yleisen puurakenteen binääripuun avulla? (lp)

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

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

K,L,J,M,I,N,H,O,C,P,F (lp)

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

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 merkkijonoVILLEKIPPAASUOLAA nousevaan aakkosjärjestykseen käyttäen

a) quicksort- algoritmia (valitse pivot-alkio aina alueen oikeasta laidasta), kirjoita välivaiheet näkyviin. (3p)

b) sijoituslajittelua (insertion sort) Kirjoita välivaiheet näkyviin. (3p)

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ä depth-first-hakupuu kyseiselle graafille käyttäen pohjana edellä muodostamaasi seuraajaluetteloesitystä. Reunus on esitettävä pinona. Esitä myös pinon sisältö algoritmin etenemisen aikana. (4p).