Université Sidi Mohamed Ben Abdellah Année Universitaire 2018/2019
Faculté des Sciences Dhar El Mahraz, Fés Semestre 4- SMI
Session de printemps
Module Structure de Données
Epreuve de Structure de Données
Exercice 1 : L’évaluation d’expressions (6pts)
On considère les parenthèses et les crochets comme seuls symboles de parenthésage.
Dans une expression, chaque signe de parenthésage ouvert doit correspondre à un signe
de parenthésage fermé de même forme et les correspondances ne se croisent pas.
L’expression X = 5×(x + (a +2)/3) est bien parenthésée,
L’expression Y = 5×(x + (a +2/3) ne l’est pas, Mauvais parenthésage.
Les expressions sont stockées dans des tableaux d’objets. Ainsi (((5+15)× (−3 + 6)) − 5)
est représentée par :
On utilisera la structure Pile, Écrire une fonction qui retourne True si la chaîne donnée
en argument est bien parenthésée et qui retourne False dans le cas contraire.
Exercice 2 : (6pts)
Soit l’arbre binaire de recherche suivant
1- Donner la liste des entiers en ordre préfixe, en ordre infixe et en ordre suffixe. (1pts)
2- Donnez l’arbre après insertion de 10, on expliquera comment il est obtenu. (1pts)
3- Donnez l’arbre après suppression de 9, on expliquera comment il est obtenu. (1pts)
4- On considère la suite des clés dans l’ordre hiérarchique construire le tas min
correspondant. On dessinera le tas après chaque insertion d’une clé. (2pts)
5- Donnez un tas-max contenant les mêmes entiers (1pts)
Page 1 sur 2
Université Sidi Mohamed Ben Abdellah Année Universitaire 2018/2019
Faculté des Sciences Dhar El Mahraz, Fés Semestre 4- SMI
Session de printemps
Exercice 3 : Arbre de codage (8pts)
Chaque feuille d'un arbre binaire correspond à un unique chemin de la racine à celle-ci.
On peut ainsi associer un code à chaque feuille de l'arbre. La procédure est simple, en
partant de la racine on crée une chaine de caractères à laquelle on concatène un 0 si on
emprunte le fils gauche et un 1 si on emprunte le fils droit.
Nous nous intéressons à des arbres dont les feuilles contiennent une lettre et aucune
feuille ne contient la même lettre, ainsi il n'y a pas d'ambiguïté. En suivant le chemin
menant de la racine à une feuille et la procédure de codage décrite, on obtient le code
associe à cette feuille. Sur l'exemple suivant, la lettre C aura pour code 110 :
1- Donnez le code associe à chaque feuille de l'arbre ci-dessus. (1,5pts)
Il est facile de voir qu'il existe une bijection entre un code et un caractère. Cela signifie
qu'à partir d'une suite de 0 et de 1 on obtient une et une seule lettre (et réciproquement).
Une chaine de caractères peut donc être codée de manière unique en associant à chaque
lettre son code et en concaténant les codes.
2- Donnez le mot associe au codage 101100101100. (1pts)
3- Donnez le code associe au mot EVADE. (1,5pts)
On utilisera le type suivant :
typedef char Element;
typedef struct noeud *Pnoeud;
typedef struct noeud {
Element val;
Pnoeud fg;
Pnoeud fd;
} Noeud;
typedef Noeud *Arbre_Binaire;
et la valeur n'aura de signification que pour les feuilles.
On utilisera les fonctions :est_vide(Arbre_Binaire A) et est_feuille(Arbre_Binaire A)
4- Ecrire une fonction récursive décode qui transforme une chaine formée de 0 et de 1
en le mot associe suivant les codes donnes par l'arbre passe en paramètre. (4pts)
Page 2 sur 2
