Ohjelmistotekniikan linja

Johdatus tietojenkäsittelytieteeseen 1 15.10.2001

1. Kirjoita moduuli Valintalajittelu(T, n), joka lajittelee (järjestää aakkosjärjestykseen) n nimeä sisältävän listan T.

2.. Fibonacci:n jonolla tarkoitetaan kokonaislukujen muodostamaa lukujonoa, jossa kaksi ensimmäistä lukua annetaan lähtötietoina, ja sen jälkeen lukujonon muut luvut voidaan laskea niin, että lukujonon luku on kahden edeltävän luvun summa. Jos Fibonacci:n lukujonon kaksi ensimmäistä lukua ovat 0 ja 1, niin silloin lukujonon alku nämä kaksi ensimmäistä mukaan luettuna on:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 jne.

Kirjoita funktiotyyppinen moduuli Fibonacci(f1, f2, n) , joka palauttaa funktion arvona lukujonon n:nnen luvun arvon, lukujonon kaksi ensimmäistä lukua ovat f1 ja f2 (näiden järjestysnumerot ovat 1 ja 2).

3. Millaisia tietorakenteita ovat pino ja jono ? Miten niiden määrittelyssä tulee esille abstraktin tietotyypin abstraktisuus ?

4. Esitä kuvion muodossa, millainen järjestetty binääripuu syntyy, kun siihen viedään alkiot listasta

9, 4, 15, 1, 7, 10

listan mukaisessa järjestyksessä. Muodosta tästä järjestetystä binääripuusta listat, kun puu käydään läpi

a) esijärjestyksessä

b) välijärjestyksessä

c) jälkijärjestyksessä.

5. Kirjoita funktiomoduuli OnPuussa(p, x), joka ilmoittaa, löytyykö arvo x järjestetystä binääripuusta p . Jos haettu arvo x löytyy, funktio palauttaa arvon TRUE, muuten arvon FALSE.

Käytä merkintöjä

- p.arvo on solmun p arvokenttä

-         p.vasen on solmun p vasen poikapuu

-         p.oikea on solmun p oikea poikapuu