Galop d’essai en vu de la préparation à la session normale prochaine
Sujet de : programmation fonctionnelle et Programmation Orientée Objet
Durée : 1h 00 min
Exercice 1 : 10 pts
Un arbre binaire de recherche est une structure de données basée sur des noeuds avec
chaque noeud qui contient une étiquette et deux sous arbres : le gauche et le droit. Pour
chaque noeud, l’étiquette de la sous-aborescence gauche doit être inférieure à l’étiquette du
noeud actuel, et l’étiquette du sous-arbre droit doit être supérieure à l’étiquette du noeud. Ces
sous arbres doivent être des arbres binaires de recherche.
La structure de donnée est la suivante :
data (Ord a) => Stree a = Null | Fork (Stree a) (Stree a) a
1) Écrivez une fonction récursive preordre qui effectue un parcours en pré-ordre (visite d'abord
la racine, puis le sous-arbre gauche et enfin le sous-arbre droit) d'un arbre binaire. La fonction
doit retourner une liste des valeurs dans l'ordre du parcours.
2) Écrivez une fonction récursive ordre qui effectue un parcours en ordre (d'abord le sous-arbre
gauche, puis la racine, puis le sous-arbre droit) d'un arbre binaire. La fonction doit retourner une
liste des valeurs dans l'ordre du parcours.
3) Écrivez une fonction récursive postordre qui effectue un parcours en post-ordre (d'abord le
sous-arbre gauche, puis le sous-arbre droit, puis la racine) d'un arbre binaire. La fonction doit
retourner une liste des valeurs dans l'ordre du parcours.
4) Écrivez une fonction récursive rechercher qui prend une valeur et un arbre binaire de
recherche (ABR) et retourne True si la valeur est présente dans l'arbre, sinon False.
5) Écrivez une fonction récursive listeVersArbre qui prend une liste triée et construit un arbre
binaire de recherche (ABR) équilibré.
6) Écrivez une fonction somme qui calcule la somme des valeurs dans un arbre. Vous pouvez
supposer que l'arbre contient des entiers.
Exercice 2 : Tri par insertion (4 pts)
On désire trier une liste d’éléments numériques à fin que ceux ci soient rangés par
ordre croissant. La méthode choisie est celle du tri par insertion. lle consiste à
insérer un élément dans une liste déjà rangée par ordre croissant, et à répéter cette
opération jusqu’à obtenir la liste triée
Insertion : Écrire la fonction qui insère un élément à sa place dans une liste. On
suppose que cette liste est déjà rangée par ordre croissant de ces
élé[Link] : Insertion 2 [] donne [2] et (Insertion 2 [1, 4] ) donne [1, 2, 4]
Tri Insertion : Écrire la fonction triInsertion qui trie une liste par ordre croissant,
par insertion successives. On insère un à un les éléments de la liste initiale dans
une liste déjà triée.
Exemples : triInsertion [] donne []et triInsertion [4,6,2,8,1,3] donne [1,2,3,4,6,8]
Exercice 3 : Programmation Orientée Objet (6 pts)
On souhaite implémenter une classe Point3D comportant trois attributs privés de type Double,
et les fonctions membres suivantes :
Initialise : pour attribuer des valeurs aux attributs
Homothetie : pour multiplier les attributs par une valeur fournie en arguments
Affiche : Pour afficher les attributs.
1) Proposer un modèle UML pour cette classe
2) Écrire le programme java correspondant
3) Proposer une fonction main pour exécuter cette classe
Soit le diagramme UML suivant :
Compte
– Num : int
– Solde : int
– Plancher : int
+ Compte (n : int , s : int , p : int)
+ consulterSolde () : int
+ crediterCompte (montant : int) : void
+ debiterCompte (montant : int) : bool
1) Donner le code JAVA de cette classe
2) Écrire une fonction main pour exécuter cette classe
