Ecole Informatique d'Orsay - Introduction aux techniques de programmation (module 101) - IUP1 95/96 EXAMEN 10 septembre 1996 4 pages - Responsable : Emmanuel Waller - Duree 4h - Aucun document autorise L'examen se deroule en 2 parties : 1h45 sur table puis 2h sur machine. Les exercices des Parties I, II et IV seront rendus sur des feuilles format A4, en ecrivant d'un seul cote pour faciliter la photocopie ; puis tapes sur machine. Pour ces Parties I, II et IV, vous rendrez par email a ``waller'' (sans utiliser applix) : 1. un programme tape comme sur votre copie : vous corrigerez les erreurs de syntaxe (faute d'orthographe, point-virgule, variable oubliee, etc.), mais pas les erreurs de conception ; 2. si ce programme ne tourne pas correctement, vous le debuggerez et rendrez une version qui tourne (bien sur, dans ce cas, on ne comptera pas tous les points). Seuls les programmes apparaissant sur votre copie pourront etre tapes sur machine. Le but de l'examen est de faire tourner correctement des programmes ; seules les fonctions qui tournent comptabiliseront des points. Les 4 parties sont independantes. La Partie I est immediate, la Partie II va de immediat a normal (mais pas forcement dans l'ordre des exercices), la IV est beaucoup plus interessante. L'examen est concu pour obtenir la moyenne par exemple en faisant, lentement (pas trop) mais surement, uniquement les Parties I et II, et en les faisant tourner sur machine correctement. ------------------------------------------------------------------------ Partie I (1,5 points) -------- 1. (1,5 points) On suppose qu'il existe deux fichiers "toto" et "titi", qu'il n'existe pas de fichier "tutu", et que "toto" contient au moins 3 caracteres. Ecrire un programme qui : a. lit le 3eme caratere de "toto" ; b. compte le nombre de fois que ce caractere apparait dans "titi" ; c. si ce nombre est pair, il ecrit dans "tutu" : ce caractere suivi de "pair" (on rappelle que 0 est pair) ; si ce nombre est impair, il ecrit dans "tutu" : ce caractere suivi de "impair". ------------------------------------------------------------------------ Partie II (10 points) --------- Definition : un "arbre binaire de recherche positif decroissant" (appele simplement "arbre" dans le reste de l'examen), est un arbre tel que : a. chaque noeud a 0, 1 ou 2 enfants (un noeud avec 0 enfant est appele une "feuille") ; b. chaque noeud a pour valeur un entier positif ou nul ; c. la valeur d'un enfant gauche est superieure ou egale a celle de son parent ; ex : 3 3 / / 3 4 d. la valeur d'un enfant droit est strictement inferieure a celle de son parent. ex : 3 \ 2 Remarque : un arbre peut etre vide. Ex : 7 / \ 11 4 / \ / \ 12 9 5 1 \ / 8 2 IMPORTANT : Du point de vue du langage Pascal, le but de cette partie est d'utiliser uniquement des procedures recursives, avec passage par variable quand il y a un resultat a renvoyer, et sans variable globale, DANS TOUTES LES QUESTIONS. (Bien sur, ce ne sera pas necessairement la procedure principale qui sera recursive, mais eventuellement une procedure qu'elle appellera pour faire le gros du travail ; mais toutes deux renverront les resultats par variable.) Toutefois, vous pourrez utiliser une fonction a la place, mais il sera retire 1 point pour la question correspondante. La question 3 utilise la 2, puis 3, 4, 5 et 6 sont independantes les unes des autres. 1. (0,5 point) Declarer un ou des types avec pointeurs pour representer ces arbres. 2. (1,5 points) Ecrire une procedure "insere" qui prend en argument un entier et un arbre, et insere cet entier a sa place dans cet arbre, selon l'algortihme simple et naturel decoulant de la definition (pas de piege). 3. (3 points) Ecrire une procedure "saisit" qui lit au clavier des entiers separes par des blancs et renvoie l'arbre qui les contient ; elle s'arrete quand elle lit un entier strictement negatif. (Il est rappele que cette procedure, ou une qu'elle appelle, doit etre recursive, sinon 2 points seront retires.) Remarque : s'il n'y a qu'un entier negatif sur la ligne, elle doit renvoyer un arbre vide. Remarque : surtout pas de dialogue interactif a cause des tests automatiques ; de plus, les entiers lus par cette procedure seront sur une seule ligne : faire "read" directement. 4. (0,5 point) Ecrire un procedure "affiche" qui ecrit a l'ecran le contenu d'un arbre, sur une seule ligne, par ordre decroissant. Pour l'exemple ci-dessus, elle ecrit : 12 11 9 8 7 5 4 2 1 5. (1,5 points) Ecrire une procedure "parite" qui pour un arbre affiche "pair" si l'arbre a un nombre pair de noeud, "impair" sinon. Pour l'exemple ci-dessus : "impair", car il y a 9 noeuds. 6. (3 points) Ecrire une procedure "fusionne" qui prend en arguments deux arbres, et modifie le premier en y inserant les elements du second. 7. Le corps de votre programme principal devra avoir en gros l'allure suivante, pour les tests automatiques. Vous ne le rendrez pas sur votre copie. begin writeln('saisie arbre 1 :'); saisit; writeln('affichage arbre 1 :'); affiche; writeln('parite arbre 1 :'); parite; writeln('saisie arbre 2 :'); saisit; writeln('affichage arbre 2 :'); affiche; writeln('fusion des arbres 1 et 2 :'); fusionne; writeln('affichage de la fusion :'); affiche; end. ----------------------------------------------------------------------- Partie III (1,5 points) ---------- 1. (1,5 points) Donner sans commentaire ce que ce programme affiche sur l'ecran lors de son execution (il est evident qu'il compile et tourne correctement). program toto; var k : integer; procedure f (var k : integer); var n : integer; procedure g (var K : integer); begin if k<0 then begin k := k+1; writeln('1 : ', n, k); g(k) end end; begin n := k; g(n); writeln('2 : ', n, k); end; begin k := -2; f(k); writeln('3 : ', k) end. ----------------------------------------------------------------------- Partie IV (10 points) --------- Dans cette partie aussi on demande des procedures recursives avec resultats passes par variable. Dans cette partie on suppose que tous les entiers d'un arbre sont distincts. 1. (1 point) Ecrire une procedure qui affiche le minimum d'un arbre. Il ne s'agit bien sur pas de parcourir systematiquement l'arbre, mais de voir simplement ou se trouve exactement ce minimum (vous l'indiquerez precisement sur votre copie), et d'aller le chercher. 2. (5 points) Ecrire une procedure qui prend un arbre, et le modifie en en retirant le noeud contenant le minimum, et en reorganisant l'arbre pour qu'il reste un arbre binaire de recherche positif decroissant ; de plus elle renvoie aussi ce noeud. Indication : supposons qu'on supprime la racine d'un arbre (ou d'un sous-arbre) ; en gros, quel noeud faut-il oter de l'arbre pour le mettre comme nouvelle racine ? Utilliser bien sur la question 1. 3. (4 points) Ecrire une procedure qui prend un entier et un arbre ; si cet entier apparait dans l'arbre, elle retire de l'arbre le noeud qui le contient, en reorganisant l'arbre pour qu'il reste binaire de recherche positif decroissant. Indication : utiliser bien sur la question 2.