Ecole Informatique d'Orsay --- Pascal (module 101) --- 1995/96 --- IUP1

Examen

12 février 1996

L'examen se déroule en 2 parties : 3h sur table puis 40mn en salle machines où vous taperez sous vi les Exercices 1, 2 et 3 exactement comme sur votre copie, puis les enverrez par mail. Chaque exercice correspond à un programme, et sera envoye séparément (donc 3 mails au total). Chaque fichier que vous enverrez devra contenir un programme complet correct.

Les Exercices 1, 2 et 3 ne seront pas rendus sur des copies d'examen usuelles mais sur des feuilles blanches standard recto-verso non pliées pour faciliter la photocopie.

Toutes les procédures ou fonctions demandées devront être récursives ; autrement dit, il est interdit d'utiliser une boucle quelconque.

Les 5 exercices sont indépendants. A l'intérieur de chaque exercice les questions sont indépendantes et peuvent être faites dans n'importe quel ordre.

Si certaines procédures ou fonctions ne sont pas écrites, celles de l'enseignant seront utilisées pour corriger (mais vous devez indiquer leurs paramètres et types). Il n'est donc pas indispensable de fournir par exemple les procédures ou fonctions de saisie. De même, pour la Question 4 de l'Exercice 2 on peut utiliser les autres procédures ou fonctions de l'énoncé même si on ne les a pas écrites.

Les 3 exercices de programmation sont classés approximativement (mais ceci est bien sûr subjectif et variera d'une personne à l'autre) par ordre de difficulté ; sauf les Questions 3 et 4 de l'Exercice 2 qui se placent après la 4 de l'Exercice 3. Les Questions 5 à 7 de l'Exercice 3 sont plus intéressantes.

Répondez aux questions sans aucun commentaire (sinon des points seront retirés). Le travail non demandé ne sera pas pris en compte (et éventuellement des points seront retirés).

Les dialogues avec l'utilisateur à réponse oui/non devront obligatoirement être faits avec la fonction suivante pour simplifier la correction. Exemple d'appel : if message('Ok ?') then ... où 'Ok ?' peut être n'importe quelle chaîne d'au plus 80 caractères.

function reponse (s : string(80)) : boolean;
    var x : integer;
    begin
        writeln(s); writeln('oui ssi 1 : '); readln(x);
        reponse := (x=1) 
    end;

Exercice 1

Ecrire un programme qui écrit dans tutu : oui si titi et toto ont exactement le même contenu, et sinon la première différence rencontrée, ainsi que son rang n, c'est-à-dire que le n-ième caractère est le premier sur lequel les deux fichiers diffèrent (l'ancien contenu de tutu sera donc perdu).

Exercice 2

1. le sous-arbre gauche de tout noeud n ne contient que des entiers strictement inférieurs à n; et

2. le sous-arbre droit de tout noeud n ne contient que des entiers strictement supérieurs à n.

                                    Affichage demande en Question 2
                                                     99
Exemple       8                                 13        
             / \                                     10
           5    9                            9
          / \    \                       8    
         4   7    13                             7
        /        /  \                        5   
       1        10   99                          4
                                                      1

1. Déclarer un type Pascal pour représenter les arbres binaires de recherche.

2. Ecrire une procédure ou une fonction récursive affiche d'affichage d'un arbre binaire de recherche comme ci-dessus.

3. Ecrire une procédure ou une fonction récursive insere qui insère un entier comme feuille d'un arbre binaire de recherche en donnant un arbre binaire de recherche (l'entier inséré est supposé distinct de tous ceux de l'arbre).

4. En déduire une procédure ou une fonction récursive saisie_et_tri qui lit des entiers sur l'entrée standard et les trie.

begin
  saisie_et_tri
  affiche
end.

Exercice 3

Exemple      -1       est represente par        -1           
            / | \                            
           2 -3 -4                          2   -3   -4  
             /\  |                         
           -5  6 9                            -5   6  9 
            |                               
            7                                 7       

1. Déclarer ce type Pascal.

2. Ecrire une procédure ou une fonction récursive somme qui calcule la somme des noeuds de l'arbre.

3. Ecrire une procédure ou une fonction récursive somme_1ers_negs qui calcule la somme des premiers fils strictement négatifs. Ci-dessus les premiers fils sont -1, 2, -5, 7, 9, et donc cette somme vaut -6.

4. Ecrire une procédure ou une fonction récursive minimum qui calcule le minimum des noeuds de l'arbre.

5. Ecrire une procédure ou une fonction récursive supprime qui supprime toutes les feuilles d'un arbre.

6. Ecrire la saisie d'un tel arbre par une fonction récursive saisie sans argument qui renvoie un arbre. Elle devra obligatoirement (pour des raisons d'interface pour la correction) saisir d'abord tous les frères, puis pour chacun le sous-arbre issu (c'est-à-dire dont il est la racine). Ci-dessus : -1, puis 2, -3, -4, puis -5, 6, puis 7, puis 9.

7. Ecrire une procédure ou une fonction récursive affiche qui affiche un tel arbre debout, mais sans tenir compte du tout des alignements entre pères et fils ; autrement dit, simplement niveau par niveau. Pour ci-dessus :

   
   -1           
   2  -3  -4  
   -5  6   9
   7       
   

begin
  saisie
  affiche
  minimum
  somme
  somme_1ers_negs
  supprime
  affiche
end.

Exercice 4

1. Donner les commandes vi permettant de

   1. aller au début et à la fin de la ligne courante

   2. aller à la page précédente et à la page suivante

   3. aller au début et à la fin du fichier

   4. aller à la ligne n

   5. copier un bloc d'un endroit à un autre du fichier

   6. éditer un autre fichier (sans sortir de vi)

2. Soit titi un exécutable d'un programme Pascal. Donner les commandes Unix pour que

   1. titi lise dans un fichier f_1 au lieu du clavier

   2. titi écrive dans un fichier f_2 au lieu de l'écran

   3. titi fasse les deux à la fois

Exercice 5

program titi;
var k :  integer;
function f(k :  integer) : integer;
  begin
    while k>0 do
      begin
        k := k - 1; writeln(k);
      end;
    f := k;
  end; 
procedure g(var k :  integer);
  begin
    while k>0 do
      begin
        k := k - 1;
        writeln(k);
      end
  end; 
begin
   k := 4; writeln(k);
   writeln(f(k));
   g(k);
   writeln(f(k));
end.
program toto;
var x,y,k :  integer;
procedure p(var k :  integer);
  function q(x,y :  integer) : integer;
    begin
      x := k + y;
      k := 12;
    end; 
  begin
    x := q(k,y);
    k := 12;
  end; 
begin
   p(k);
   p(y);
   x := q(k,y);
   k := 12;
   writeln(x,y,k);
end.