Tietorakenteet / syksy 2009 / Linna

Harjoitus 3, viikko 39

1. Laadi ohjelma, joka kääntää jonon alkiot päinvastaiseksi pinon avulla.

2. a) Tee ei-rekursiivinen ohjelma Fibonaccin lukujen laskemiseksi.

b) Vertaa rekursiivisen (luennolla esitetyn) ja ei-rekursiivisen ohjelman suoritta-mien yhteenlaskuoperaatioiden määrää laskettaessa Fibonaccin luku F(8).

3. Tee selkoa miten yksisuuntainen lista voitaisiin toteuttaa taulukon avulla. Miten voitaisiin toteuttaa operaatiot Alkion_lisäys ja Alkion_poisto ja kuinka tehokkaasti ne voidaan toteuttaa? Tutki myös tapausta, missä alkiot pidetään koko ajan suuruusjärjestyksessä.

4. Laadi jono-operaatioita käyttäen algoritmi Join(Q1,Q2), joka tyhjentää jonon

Q2 ja liittää kaikki sen sisältämät alkiot jonon Q1 häntään.

5. Muunna seuraavat sisämerkintäiset lausekkeet a) postfix-muotoon, b) prefix-

muotoon:

a) a+b*c+d, b) a*b*c+d*e, c) (a+b)*(c+d*e)