IUP 2

Examen d'informatique

seconde session 1997 (26/6/97)

Durée 2h, documents autorisés : cours manuscrit et documents fournis en cours, tout autre étant interdit.

Partie A : analysez ce programme :

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

typedef struct noeud
 {
  int val;
  struct noeud *g;
  struct noeud *d;
 }noeud;
typedef noeud * pointeur;

pointeur sssss(void)
 {
  pointeur p;
  p=(pointeur)malloc(sizeof(noeud));
  printf("vvvvv ? ");
  scanf("%d",&(p->val));
  if(p->val)
    p->g=p->d=NULL;
  else
   {
    printf("ggggg ? \n");
    p->g=sssss();
    printf("ddddd ? \n");
    p->d=sssss();
   }
  return(p);
 }
int eeeee(pointeur x)
 {
  if(x->val)return(x->val);
  else return(eeeee(x->g)+eeeee(x->d));
 }
void main(void)
 {
  pointeur rrrrr;
  rrrrr=sssss();
  printf("résultat : %d\n",eeeee(rrrrr));
 }

Question A1 : Que fait la fonction sssss ? Vous pouvez supposer que l'on entre, dans l'ordre, les données suivantes au clavier (séparées par des return) :

cas A : 3
cas B : 0 1 2
cas C : 0 0 2 0 -5 3 0 5 -2

précisez dans les 3 cas l'état de la mémoire après l'appel de la fonction sssss par le programme principal.

Question A2 : Que fait la fonction eeeee ? Et qu'affiche dans les trois cas précédents le programme principal ?

Partie B : Tableau de chaînes de caractères

On désire traiter un tableau T contenant N chaînes de caractères. On dispose du texte ci-dessous :


#include <stdio.h>
#define LONG 40
#define DIM 100
typedef char chaine[LONG];
typedef chaine tableau[DIM];

int lecture(tableau T)
/* lecture fichier, stockage dans T */
/* retour : nombdre de lignes lues */
 {
  int nb=0;
  FILE*fic;
  fic=fopen("MONFIC.DAT","r");
  while(!feof(fic))
    fscanf(fic,"%s",T[nb++]);
  fclose(fic);
  return(nb);
 }
void main(void)
 {
  tableau T;
  int N;
  N=lecture(T);
 }

La fonction lecture lit dans un fichier N chaînes de caractères (des noms par exemple) et les stocke dans le tableau T, aux positions 0 à N-1 comprises, et retourne N

Question B1 : écrire la fonction void trier(tableau T, int N) qui trie le tableau par ordre alphabétique (on utilisera la fonction strcmp). On suppose que les données sont le plus souvent disponibles initialement à peu près classées par ordre alphabétique, excepté les dernières données qui sont dans un ordre aléatoire, et peuvent contenir des noms du début de l'alphabet. Choisissez un algorithme qui, sans être nécessairement le meilleur, est suffisamment adapté à ces conditions.

Question B2 : écrire une fonction qui demande à l'utilisateur un nom, et recherche le plus rapidement possible ce nom dans le tableau T (T a été trié auparavant). La fonction doit retourner un entier valant la position de ce nom dans le tableau (entre 0 et N-1) s'il a été trouvé, ou doit retourner -1 si le nom proposé n'est pas dans le tableau.

Question B3 : écrire une fonction qui affiche les noms suivant leur longueur effective (40 maxi), du plus long au plus court. Les noms de même longueur peuvent être affichés dans n'importe quel ordre. Attention, l'ordre dans le tableau T ne doit pas être modifié par cette fonction ! La rapidité de l'algorithme n'est pas obligatoire.

pour voir les réponses, ne cliquez pas encore ici

Patrick TRAU, ULP - IPST 4/7/97