Module 101 --- Examen

IUP1

3 février 1995

3 pages -- Responsable : Emmanuel Waller -- Durée : 3 heures -- Aucun document autorisé

Exercice 1

On considère des listes simplement chaînées d'entiers positifs.

  1. Ecrire une ou des déclarations de type permettant de représenter de telles listes.

  2. Ecrire une fonction max qui prend en entrée un pointeur sur une liste et renvoie comme valeur de retour le plus grand entier de cette liste.

  3. Ecrire une procédure pop (pas une fonction) qui prend comme unique argument un pointeur sur une liste. Si le premier élément de cette liste est zéro, elle le retire de la liste ( proprement) et renvoie la nouvelle liste ; sinon, elle renvoie la liste inchangée. Exemple : [0,2,3,4] -> [2,3,4] et [2,3,4] -> [2,3,4].

  4. Ecrire un programme qui

    1. lit des entiers positifs sur l'entrée et les range par insertion en tête dans une liste chaînée qu'il construit au fur et à mesure ;

    2. effectue ensuite un appel à max et à pop.

Exercice 2

On considère deux fichiers existants titi et toto contenant des caractères.

  1. Ecrire un programme qui affiche oui si le premier caractère de titi est le même que le deuxième caractère de toto, et non sinon.

  2. Ecrire un programme qui affiche oui si titi et toto ont exactement le même contenu, et sinon la première différence rencontrée.

Exercice 4

On considère des arbres dont chaque noeud possède 0,1,2 ou 3 fils, et contient de plus un entier, comme dans l'exemple suivant. 

          1
         / \
       -2   -3
      / \    |
     4   0  -3
     |     / | \
     1    2  0  -1

  1. Ecrire une ou des déclarations de type permettant de représenter de tels arbres.

  2. Ecrire une fonction récursive som qui prend en entrée un pointeur sur un arbre et renvoie la somme de tous les entiers de l'arbre. Dans l'exemple ci-dessus, elle renvoie -1.

  3. Ecrire une fonction récursive neg qui prend en entrée un pointeur sur un arbre et renvoie la somme des entiers négatifs. Dans l'exemple ci-dessus, elle renvoie -9.

  4. Ecrire une fonction récursive max qui prend en entrée un pointeur sur un arbre et renvoie le plus grand entier. On supposera que l'arbre passé en argument ne contient que des entiers positifs.

Exercice 5

On considère les deux programmes suivants. Indiquer s'ils sont acceptés à la compilation. Si oui, indiquer ce qui s'affiche sur la sortie. Si non, indiquer pourquoi. 

program tutu;
var x,y,k :  integer;
procedure p(var k :  integer);
  function q(x,y :  integer) : integer;
    begin
      x := k + y;
      k := 12;
    end; { q }
  begin
    x := q(k,y);
    k := 12;
  end; { p }
begin
   p(k);
   p(y);
   x := q(k,y);
   k := 12;
   writeln(x,y,k);
end.

program tata;
var k :  integer;
function f(k :  integer) : integer;
  begin
    while k>0 do
      begin
        k := k - 1;
        writeln(k);
      end;
    f := k;
  end; { f }
procedure g(var k :  integer);
  begin
    while k>0 do
      begin
        k := k - 1;
        writeln(k);
      end
  end; { g }
begin
   k := 4; writeln(k);
   writeln(f(k));
   g(k);
   writeln(f(k));
end.