TENTTI
08.04.97
Kaikissa ohjelmointitehtävissä on käytettävä ANSI-C-kieltä (C++ ei kelpaa).
la) Kirjoita funktio, joka saa argumenttina positiivisen kokonaisluvun N ja palauttaa kokonaisluvun k siten , että 2^(k-1) < N <= 2^k. (2 p)
lb) Kirjoita funktio, joka saa argumenttina merkin ja merkkijonon ja palauttaa tiedon, kuinka monta kertaa annettu merkki esiintyy annetussa merkkijonossa
lc) Anna esimerkki kummankin funktion käytöstä. Esitä myös tarpeelliset määrittelyt. (2p)
2) Tutkitaan seuraavaa C-ohjelmaa. Mikä on muuttujien n, total ja i status ohjelman kohdissa 1, 2, 3 ja 4? Selitä kussakin kohdassa kunkin muuttujan osalta seuraavat asiat: Onko muuttujalle varattu muistitilaa? Onko muuttujalla yksiselitteistä arvoa ja mikä ko. arvo
on, jos muuttujalla sellainen on? (6p)
3) Fibonaccin luvut määritellään seuraavasti: F(1) = F(2) = 1, ja F(N) = F(N-1) + F(N-2), kun N > 2. Kirjoita täydellinen C-ohjelma, joka tulostaa taulukossa N:n ensimmäisen Fibonaccin luvun arvon. Luvun N arvo kysytään ohjelman käyttäjältä. Ratkaisusi arvostelussa otetaan huomioon paitsi ohjelman oikea toiminta myös sen tehokkuus. (5p)
4) Esitä lyhyet esimerkit seuraavien C-kielen rakenteiden käytöstä. Pidä huoli, että esimerkissäsi käyvät ilmi sekä tarpeelliset mäanttelyt että rakenteiden käyttötapa.
5a) Määrittele tietue tnode, joka esittää binäärisen hakupuun solmua, kun puuhun voidaan tallettaa kokonaislukuja. Esitä myös tietotyyppi
Tree, joka on osoitin ko. solmuun. (2p)
6) Arvioi kysymyksiin vastaamiseen käyttämäsi yhteisaika puolen tunnin tarkkuudella.
#include
/* sum: compute the sum 1 + 2 + ... + n */
int sum(int n)
{
int total;
/* 1 */
for (total = 0; n > 0; n--)
total += n;
/* 2 */
return total;
}
int main(void)
{
int i = 5; /* 3 */ printf("%d\n", sum(i)); /* 4 */
return O;
}
a) Yksidimensioiset taulukot (2p)
b) Makrot (2p)
c) Komentorivin argumentit (3p)
5b) Kirjoita funktio, joka lisää argumenttinsa annetun solmun argumenttina annettuun binääriseen hakupuuhun. (2p)
5c) Kirjoita funktio, joka tulostaa kaikki puussa olevat kokonaisluvut suuruusjärjestyksessä. (2p)