Kirjoita JOKAISEEN palauttamaasi paperiin nimesi, opintokirjan numero, myös tarkistuskirjain, "Tietotekniikka B, tentti 15.12.97" sekä allekirjoituksesi. Jätä paperin yläreunaan vähintään 3 riviä tyhjää pisteytystä varten. Vastaa tehtäviin 1, 2 ja 3 yhdelle paperille ja tehtäviin 4, 5 ja 6 toiselle paperille. Sinun täytyy palauttaa kaksi eri paperia, omiin pinoihinsa.

Kaikissa ohjelmointitehtävissä on käytettävä ANSI-C-kieltä (C++ ei kelpaa).

1a)  Mitä seuraava ohjelma tulostaa? (2p)

#include <stdio.h>

void func(char *s1, char *s2, char *s)
{
  while ((*s = *s1) != '\0')
    {
      s++; s1++;
      *s = *s2;
      s++; s2++;
    }
}

int main(void)
{
  char s1[] = "12345";
  char s2[] = "98765";
  char s3[50];
  func(s1, s2, s3);
  printf("%s\n", s3);
}

1b)  Mitä ohjelma tulostaa, jos s1 ja s2 on alustettu seuraavasti: (1p)

char s1[] = "123";
char s2[] = "98765";

1c)  Mitä ohjelma tulostaa, jos s1 ja s2 on alustettu seuraavasti: (1p)

char s1[] = "12345";
char s2[] = "987";

2)  Seuraavalla sivulla olevan ohjelman tarkoituksena on lukea päätteeeltä joukko lukuja ja tulostaa niiden summa. Tutki ohjelman toimintaa, kun sille annetaan syötteet

12
23
END

Mitä tapahtuu? Toimiiko ohjelma oikein? Jos ei toimi oikein, niin selitä syy(t), miksi se toimii virheellisesti. (4p)

Funktio atoi saa argumenttina merkkijonon ja muuntaa sen vastaavaksi kokonaisluvuksi. Esim. atoi("234") palauttaa arvon 234.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  int luku, summa = 0;
  char s[80];
  printf("Anna lukuja ja viimeiselle riville END\n");
  do {
    scanf("%s", s);
    luku = atoi(s);
    summa += luku;
  } while (s != "END");
  printf("Summa = %d\n", summa);
}

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. (4p)

4a)  Esitä otsikkotiedosto stack.h, jossa on tarpeelliset määrittelyt sellaiselle pinolle, johon voidaaan tallettaa korkeintaan 100 merkkijonoa sekä prototyypit funktioille, joilla annettuun pinoon voidaan lisätä uusi merkkijono ja annetusta pinosta voidaan poistaa merkkijono. Voit olettaa, että merkkijonoilla on jokin maksimipituus. (2p)

4b)  Esitä tiedosto stack.c, missä toteutat em. lisäys- ja poistofunktiot pinolle. (3p)

4c)  Kirjoita pääohjelma, joka lukee käyttäjän antamasta tiedostosta 100 merkkijonoa ja tulostaa ne näkyviin käänteisessä järjestyksessä. Käytä hyäksi edellä määrittelemääsi pinorakennetta. Voit olettaa, että tiedostossa on riittävästi merkkijonoja ja että niiden pituus noudattaa edellä asettamaasi maksimipituutta. (4p)

5a)  Esitä tietue, joka kuvaa binäärisen hakupuun solmua, kun solmuun voidaan tallettaa yksi kokonaisluku. Määrittele myös tyyppi, joka on osoitin tällaiseen solmuun. (2p)

5b)  Oletetaan, että alunperin tyhjään binääriseen hakupuuhun on talletettu luvut 5, 3, 8, 4, 9, 1, 7 ja 6 tässä järcjestyksessä. Piirrä tietorakenne tämän jälkeen. (2p)

5c)  Kirjoita funktio insert, joka saa argumenttina osoitteen binäärisen hakupuun juureen ja kokonaisluvun. Funktio lisää puuhun uuden solmun, johon on talletettu argumenttina annettu kokonaisluku ja palauttaa osoitteen muuttuneen puun juureen. Käsittele myös tapaus, jossa puu voi olla alunperin tyhjä. (4p)

6)  Arvioi tehtäviin vastaamiseen käyttämäsi kokonaisaika 30 minuutin tarkkuudella.