Université Mohammed V Année Universitaire 2022/2023

Faculté des Sciences de Rabat MODULE SD

Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°1 : " Types Abstraits de Données :Vecteurs et Listes ‘’]

Objectifs : - Initier à la manipulation des types abstraits de données (TADs).

- Application aux TAD : Vecteurs et Listes

Exercice 1
On désire implanter, en langage C, le type abstrait de données Vecteur, défini dans le cours. On
rappelle, ci-dessous, une spécification minimale du TAD Vecteur :

Type Vecteur
Utilise Entier, Elément
Opérations
vect : Entier → Vecteur
changer_ième: Vecteur x Entier x Elément → Vecteur
ième : Vecteur x Entier → Elément
taille : Vecteur → Entier
Préconditions
vect(i) est_défini_ssi i ≥ 0
ième(v,i) est_défini_ssi 0 ≤ i < taille(v)
changer_ième(v,i,e) est_défini_ssi 0 ≤ i < taille(v)
Axiomes
Soit, i, j : Entier, e : Elément, v : Vecteur
si 0 ≤ i < taille(v) alors ième(changer_ième(v,i,e),i) = e
si 0 ≤ i < taille(v) et 0 ≤ j < taille(v) et i ≠ j
alors ième(changer_ième(v,i,e),j) = ième(v,j)
taille(vect(i)) = i
taille(changer_ième(v,i,e)) = taille(v)

Il existe plusieurs méthodes pour représenter les vecteurs. Parmi celles-ci une méthode qui consiste à
représenter un vecteur sous la forme d'un tableau. On considère ici, un vecteur comme est une structure
regroupant un entier, pour la taille, et un pointeur sur les éléments du vecteur.
a)- Donner la déclaration complète, en C, de la structure de données représentant le TAD Vecteur
d'entiers, c-à-d :
- Donner les déclarations nécessaires pour définir le type Vecteur d'entiers ;
- Donner les déclarations, en C, des primitives du TAD Vecteur d'entiers.
b)- Définir les primitives (ou opérations de base) du TAD Vecteur d'entiers, c'est à dire : pour chaque
primitive, écrire la fonction C correspondante.
c)- Au TAD Vecteur d'entiers on ajoute les deux opérations auxiliaires suivantes:
- produit_scalaire qui calcule le produit scalaire de deux vecteurs d'entiers.
- decalage_circulaire qui prend un vecteur et retourne le vecteur dans lequel tous les
éléments sont décalés d'une place vers la droite (le dernier est inséré à la 1ère place).
Ecrire en langage C les deux opérations ci-dessus.

- 1/2 -
 TD n°1 : [ Types Abstraits de Données]

Exercice2
On considère la représentation simplement chaînée pour le TAD Liste défini en cours pour une liste
de nombres entiers.
a)- Ecrire la fonction affiche qui affiche les éléments d'une liste chaînée L.
b)- Ecrire la fonction copie qui crée une copie d'une liste chaînée L.
c)- Ecrire la fonction concat qui concatène deux listes L1 et L2 (sans qu'elles soient modifiées).
d)- Ecrire la fonction supprime_occur qui supprime toutes les occurrences d'une valeur val dans
une liste L.
e)- Ecrire la fonction récursive compte_occur qui calcule le nombre d'occurrences d'un élément e
dans une liste L
f)- Ecrire la fonction purge qui purge une liste L (i.e., enlève les doublons).
g) -Ecrire la fonction récursive inverse qui crée la liste miroir LM d'une liste L.
Exercice 3
Une liste triée est une liste dont les éléments sont toujours rangés dans un ordre défini par une clé (un
champ ou une combinaison de champs d'un élément). Pour simplifier, on considère des listes de nombres
entiers.
a)- Ecrire la fonction insere_tri qui insère un élément dans une liste triée LT.
b)- Ecrire la fonction fusion_tri qui fusionne deux listes triées LT1 et LT2 (sans qu'elles soient
modifiées).

Exercice 4
a)- Ecrire la fonction insere_avant qui insère, dans une liste doublement chaînée Ld, un entier e
avant un noeud d'adresse pN.
b)- (Question facultative) Ecrire la fonction supprime_poccur qui supprime, dans une liste
doublement chaînée Ld, la première occurrence d'un élément connaissant l'adresse pN de son noeud.

Exercice 5
Refaire l'exercice 3 ci-dessus, en considérant une liste chaînée circulaire Lc.

- 2/2 -
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°2 : Types Abstraits de Données : Piles & Files]

Exercice1

On s'intéresse au TAD Pile, défini dans le cours. Les primitives du TAD Pile sont supposées
déjà définies.
a)- Ecrire un algorithme (ou une fonction C), taille_pile, qui calcule le nombre d'éléments
dans une pile donnée.
b)- Ecrire un algorithme (ou une fonction C), copie_pile, qui retourne une copie d'une pile
donnée.
Exercice2

Utiliser une pile pour évaluer une expression arithmétique postfixée codée sur un tableau de
caractères, en supposant pour simplifier que: tous les opérateurs sont binaires et limités à +, -,
* et / . On utilise uniquement des nombres entiers naturels
Indication : On utilise la pile pour stocker les opérandes. Dès qu'on lit une opération, on
récupère les deux opérandes sur le dessus de la pile, on effectue l'opération et on met le
résultat sur la pile. A la fin de la lecture de l'expression, il ne doit rester dans la pile qu'une
seule valeur: le résultat du calcul.
Note : on se donne la primitive « est-opérande » pour tester si un caractère est opérande ou
pas de même la primitive « effectuer-opération » pour effectuer une opération arithmétique
entre deux opérandes.
Exercice3

Ecrire une primitive (ou algorithme) qui retourne une file inversée. Note : La représentation
du TAD file par tableau circulaire est conseillée.
Exercice 4
Nous avons également vu en cours une implémentation d'une file par un tableau circulaire.
Dans cet exercice, nous allons implémenter une file de taille N à l'aide de deux piles de taille
N. L'idée est la suivante : Le sommet de la première pile correspond à l'avant de la file, tandis
que le sommet de la seconde pile correspond à l'arrière de la file. Lorsque la première pile est
vide, la seconde peut être retournée sur la première. Ce retournement est utilisé pour retirer
l'élément en tête de file lorsque la pile correspondant à l'avant est vide.
1) Ecrire toutes les primitives standards concernant une file, à savoir Création d’une file ;
tester si une file vide ou pleine ; retourner la tête d’une file.
2) Ecrire la primitive enfiler (F) correspondante à cette nouvelle conception de la file
3) De même écrire la primitive défiler (F).

Note : on pourra utiliser toutes les primitives du cours aux pile et files
 Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°2 : Types Abstraits de Données : Piles & Files]

Solution
Exercice1

a) Taille d’une pile

int taille_pile (Pile p) {

return ([Link] +1)

}

b) Copie d’une pile

Pile Copie_Pile ( Pile p) {

Pile pa =pile_vide ( ), pc = pile-vide( ) ;
If est_vide (p) return (p) ;
for (i=0 ; i<= [Link] ; i++) {
Pa= empiler (pa, sommet(p)) ;
P=depiler (P) ;
}
for (i=0 ; i<=pa. sommet ; i++) {
pc=empiler (pc, sommet(pa)) ;
p=empiler (p, sommet(pa)) ;
pa=depiler (pa) ;
}
return(pc) ;
}

Exercice2

Indication : On utilise la pile pour stocker les opérandes. Dès qu'on lit une opération, on
récupère les deux opérandes sur le dessus de la pile, on effectue l'opération et on met le
résultat sur la pile. A la fin de la lecture de l'expression, il ne doit rester dans la pile qu'une
seule valeur: le résultat du calcul.
Note : on se donne la primitive « est-opérande » pour tester si un caractère est opérande ou
pas de même la primitive « effectuer-opération » pour effectuer une opération arithmétique
entre deux opérandes.
Dans cet exercice, une expression arithmétique est postfixée au lieu d’infixée et à
laquelle on est habitué. On peut définir une expression postfixée (EP) comme suit :
Une variable ou un nombre est une expression postfixée. Si Ο est un opérateur et x et y
deux EP alors xyΟ est une EP.

1/5
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°2 : Types Abstraits de Données : Piles & Files]

Solution
Exemple :

Une telle Expression sera délimitée par le caractère ‘%’ et mise dans un tableau de
caractères de taille maximale Max , nommé tableau.

Dans cet exercice comme mentionné dans la note de l’énnoncé on suppose que l’on
dispose déjà de deux primitives (ici fonctions), la première nommée « estopérande » qui
retourne vrai si le caractère de l’expression arithmétique est un opérande sinon elle
retourne 0. La deuxième primitive nommée « effectueroper » effectue une opération
arithmétique entre 2 opérandes.
Algorithme évaluer-EP ( E , EP : tableau[MAX] de caractères) : réel
Var : i entier ; opd, opg, résultat : réel ; p : Pile)
Début
P ! pile_vide ( ) ;
i !0;
tant que EP[i]<> ‘%’ faire
si estopérande(EP[i]) alors empiler(p, ValeurSommet(EP[i])
sinon
opd ! Sommet(p) ;
p ! dépiler(p) ;
opg! Sommet(p) ;
p! dépiler(p) ;
p! empiler(p, effectueroper(opg, EP[i], opd)) ;
i++ ;
fin tant que
résultat! Sommet(p) ;
p! dépiler(p) ;
retourner(résultat) ;
fin.

Note importante : ValeurSommet est une fonction qui permet de donner la valeur
numérique de l’opérande parce qu’il est inséré dans le tableau comme caractère et ce afin
de pouvoir effectuer les opérations arithmétiques .

Exercice 3

Algorithme File-Inversée (F : File) : File ;

Var p : Pile
Début

2/5
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°2 : Types Abstraits de Données : Piles & Files]

Solution
p!pile_vide (p) ;
Tant que ( ! est_vide (F)) faire
début
p!empiler (p, tête(F)) ;
F!défiler (F) ;
Fin (tantque) ;
Tant que ( ! est_vide(p))
F!enfiler (F, sommet(p)) ;
p!depiler (p) ;
Fin (tantque) ;
retourner(F) ;
Fin.

Exercice 4

Dans cet exercice une nouvelle représentation d’une file aura lieu. En effet, une file de taille
N va être représentée par deux piles de taille N.

Note importante : - Etant donné que la taille de la file est N , alors les 2 piles ne peuvent
jamais contenir en même temps N éléments, mais par contre le nombre total des éléments
contenus en même temps dans les 2 piles peut atteindre N .

La file peut être considérée ICI comme une structure à 2 champs,

typdef struct {
Tête : pile ;
Queue : pile ;
} file-2-piles.

Primitive de création d’une File : Créer-file

Algorithme Créer –file ( ) : file-2-piles
Var F : file-2-piles ;
Début
F.Tête <− pile_vide ( );
[Link] <− pile_vide ( );
retourner F;
Fin.
Note : - le sommet de F.Tête est la tête de la file F.

- le sommet de [Link] est la queue de la file F

3/5
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°2 : Types Abstraits de Données : Piles & Files]

Solution
Primitive pour tester si une file est vide

Remarque : La file est vide si les deux piles sont vides

Algorithme File-Vide (F) :" Booleén

Début
retourner (est_vide(F.tête) && est_vide([Link])) ;
Fin.

Primitive pour tester si une file est pleine/

On décide qu’une file est pleine si le nombre d’éléments contenus dans les 2 piles vaut N .

Algorithme File-Pleine (F : file-2-piles) : Booléen

Début
Si ( taille_pile(F.tête)+taille_pile([Link]) )== N) alors
retourner (1)
Sinon
retourner (0)
Fin.

Primitive pour retourner la tête d’une file

Algorithme Tête-File (F : file-2-piles) : Element

Début
Si ! File-Vide (F) alors
Si ! est_vide( F.tête) alors
Retourner (sommet ( F.tête))
Sinon retourner ((F. Queue).elements[0] ) ;

Sinon retourner (« impossible : la file est vide ») ;

Fin.
Primitive pour enfiler un élément e dans une file

Algorithme Enfiler ( F :file-2-piles , e :Element ) : file-2-piles ;

Début
Si ! File-Pleine (F) alors
F! emplier ([Link], e) ;
Sinon
Ecrire (« impossible : la file est pleine ») ;
Fin.

4/5
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°2 : Types Abstraits de Données : Piles & Files]

Solution
Primitive pour défiler(F)
Algorithme Défiler (F : file-2-pile) : file-2-piles ;
Début
Si ! File-Vide (F) alors
Si ! est_vide(F.Tête) alors
F.Tête ! depiler (F.Tête) ;
Sinon / *retourner la pile ([Link]) sur la pile F.Tête */
Début
Tant que ! est_vide( [Link]) faire
Début
F.Tête! emipler( F.Tête, sommet ([Link])) ;

[Link]! depiler([Link]) ;
Fin de tantque .
F.Tête! depiler (F.Tête) ;

Rappel : les primitives empiler et depiler sont définies dans le cours.

5/5
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]

Objectifs : - Initier à la manipulation des arbres (représentés par pointeurs ou par tableaux) ;
- Distinguer différents arbres binaires : de recherche et tas.

Exercice 1
On considère la représentation par pointeurs pour le TAD Arbre_Binaire défini en cours pour un arbre binaire
contenant des nombres entiers. Ecrire en langage C les fonctions suivantes :
a)- La fonction taille qui calcule le nombre de nœuds dans un arbre binaire Ab.
b)- La fonction hauteur qui calcule la hauteur d'un arbre binaire Ab.
c)- La fonction est_feuille qui retourne 1 si un arbre binaire Ab correspond à une feuille, 0 sinon.
d)- La fonction appartient_AB qui retourne 1 si un élément e appartient à un arbre binaire Ab, 0 sinon.

Exercice 2
Un arbre binaire de recherche est un arbre binaire tel que pour tout nœud, les clés de tous les nœuds du sous-arbre
gauche (resp. du sous-arbre droit) sont inférieures ou égales (resp. supérieures) à la clé du nœud.
a)- Dessiner l'arbre binaire de recherche obtenu par ajouts successifs aux feuilles des éléments suivants :
10, 12, 7, 14, 16, 15, 4, 9, 8, 5, 3, 2.
b)- Supprimer les éléments 15, 9, 7, en utilisant l'algorithme vu en cours.
c)- Ecrire la série de nombres entiers qui résulte de l'arbre précédent en utilisant chacun des parcours suivants :
préfixe, infixe, postfixe et en largeur (par niveau).
Exercice 3
On considère la représentation par pointeurs pour le TAD Arbre_Rech défini en cours pour un arbre binaire de
recherche contenant des nombres entiers.
a)- Ecrire en C la fonction récursive affiche_infixe qui affiche, à l'aide d'un parcours infixe, les éléments d'un
arbre binaire de recherche Abr.
b)- Proposer en pseudo-code l'algorithme affiche_en_largeur qui affiche, à l'aide d'un parcours en largeur,
les éléments d'un arbre binaire de recherche Abr. (Indication : Utiliser la structure de données File)
c)- (Question facultative) Ecrire en C la fonction itérative appartient_ABR qui retourne 1 si un élément e
appartient à un arbre binaire de recherche Abr, 0 sinon.
d)- (Question facultative) Ecrire la fonction fusion_ABR qui fusionne deux arbres binaires de recherche Abr1 et
Abr2 (sans duplication des éléments).
Exercice 4
Un tas est un arbre binaire parfait tel que la clé de chaque nœud est supérieure ou égale aux clés de ses fils. On
considère la représentation par tableaux pour le TAD Tas défini en cours pour un tas contenant des entiers.
a)- Donner l'arbre binaire parfait correspondant au tableau T d'entiers suivants : {7, 1, 6, 4, 5, 2, 3, 10, 9, 11, 8}
b)- Transformer cet arbre pour qu'il vérifie la propriété du tas.
c)- (Question facultative) Exécuter l'algorithme du tri par tas sur le tableau T.
d)- (Question facultative) Ecrire en C la fonction appartient_Tas qui retourne 1 si un élément e appartient à
un tas T, 0 sinon.

- 1/1 -
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

Objectifs : - Initier à la manipulation des arbres (représentés par pointeurs ou par tableaux) ;
- Distinguer différents arbres binaires : de recherche et tas.

On rappelle la représentation chaînée d'un arbre binaire :

. typedef int Element;//le type d'information contenue dans
un noeud

. typedef struct noeud *Pnoeud;//un pointeur de noeud

. typedef struct noeud {

Element val; // valeur contenue dans le noeud

Pnoeud fg; // fils gauche
Pnoeud fd; // fils droit
} Noeud;
. typedef Noeud *Arbre_Binaire;

Exercice 1

a)
int taille(Arbre_Binaire Ab) {
// nombre de noeuds dans un arbre binaire
if (est_vide(Ab)) return 0;
return (1+taille(gauche(Ab))+taille(droite(Ab))); }

b)
int hauteur(Arbre_Binaire Ab) {
if (est_vide(Ab)) return -1;
else {
int hg=1+hauteur(gauche(Ab));
int hd=1+hauteur(droite(Ab));
return (hg<hd?hd:hg);}
}

1 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

c)

int est_feuille(Arbre_Binaire Ab) {

// precondition : arbre non vide !

if (est_vide(Ab)) {

printf("Erreur : Arbre vide !\n");

exit(-1); }
return (est_vide(gauche(Ab)) && est_vide(droite(Ab));
}

d) int appartient_AB(Arbre_Binaire Ab, Element e) {//

retourne 1 si un element est dans un arbre binaire, //
sinon 0
if (est_vide(Ab)) return 0;
if (contenu(racine(Ab)) == e) return 1;
return (appartient_AB(gauche(Ab),e)||
appartient_AB(droite(Ab),e));

Exercice 2

a)10 est la racine ; 7 le fils gauche et 12 le fils de droite. 4 et 9 sont les

fils gauche et droit de 7. 3 et 5 sont les fils gauche et droit de 4. 2 est le
fils gauche de 3. 8 est le fils gauche de 9. 14 est le fils droit de 12. 16 est
le fils droit de 14. 15 est le fils gauche de 16.

2 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

b) Après la suppression, il faudra toujours avoir un arbre binaire de

recherche.

3 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

Il y a en général trois cas à considérer qui sont décrits par les 3 suppressions suivantes :
15 n'a pas de fils ; il est simplement éliminé.

9 a un seul fils (8 qui est son fils gauche) ; 9 est remplacé par 8.

7 a deux fils ; on choisit de le remplacer par le plus grand élément de son

sous arbre gauche (c-à-d 5) .

4 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

c) parcours préfixe : 10 5 4 3 2 8 12 14 16
parcours infixe : 2 3 4 5 8 10 12 14 16
parcours postfixe : 2 3 4 8 5 16 14 12 10
parcours en largeur (par niveau) : 10 5 12 4 8 14 3 16 2

Exercice 3
a)
void affiche_infixe(Arbre_Binaire Abr) {
if (Abr) {
affiche_infixe(Abr->fg);
printf("%d ", Abr->val);
affiche_infixe(Abr->fd);
} }

b) Algorithme affiche_en_largeur(Abr : Arbre_binaire)

Entrées : un arbre binaire

5 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

Sortie : affichage des éléments de Abr par niveau

Variables :

F : File ; (* Une file de pointeurs de nœud *)

pn: Pnoeud; (* un pointeur de nœud *)
Début
F!file_vide();

si non(est_vide(Abr)) alors

F! enfiler(F, Abr); (* enfiler le pointeur sur la racine *)

fsi

tantque non(est_vide(F)) faire

pn! tete(F);F!défiler(F);

afficher(contenu(racine(pn)));

si non(est_vide(gauche(pn))) alors

F!enfiler(F, gauche(pn));

fsi

si non(est_vide(droite(pn))) alors

F!enfiler(F, droite(pn));

fin si
fin tantque

Fin.

6 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

c) int appartient_ABR(Arbre_Rech Abr, int e){

// une solution itérative
int trouve=0;
while ((Abr) && !trouve) { //Cela signifie que la boucle s'arrêtera dès que l'élément 'e' est trouvé ou
que tous les nœuds de l'ABR ont été examinés sans trouver l'élément e.
if (Abr->valeur == e)
trouve=1;
//Si la valeur de l'élément courant de l'ABR est inférieure à 'e', on sait que e
else if (Abr-->valeur < e)
doit être dans le sous-arbre droit, On se déplace donc vers le sous-arbre droit
Abr=Abr->fd; en affectant la valeur de Abr->fd (fils droit) à Abr.
else
Abr=Abr->fg; //Si la valeur de l'élément courant de l'ABR est supérieure à 'e', On se déplace
donc vers le sous-arbre gauche en affectant la valeur de Abr->fg (fils gauche) à
}
return trouve; Abr.
}
d) Il s'agit de la fusion de deux arbres binaires de recherche, Abr1 et Abr2.
Une solution naïve (très simple), mais inefficace en terme de coût d'exécution,
consisterait à :
a- considérer un nouvel arbre initialement vide, appelé AbrF (arbre de la fusion)
b- insérer les éléments de Abr1 dans AbrF : utiliser la fonction d'insertion dans un
arbre binaire de recherche
c- faire de même avec les éléments de Abr2
d- retourner AbrF
Pour parcourir les éléments de Abr1 et Abr2, en vue de les insérer dans AbrF, on
pourrait utiliser l'une des trois opérations de parcours (préfixe, infixe ou postfixe).

La non duplication des éléments est gérée par l'opération d'insertion dans un arbre
binaire de recherche.

7 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution
Exercice 4
Question a)- T={7,1,6,4,5,2,3,10,9,11,8}

Il s'agit d'une question simple. Tout simplement, en faisant référence au cours et se

basant sur la numérotation hiérarchique (par un parcours par niveaux) des arbres
binaires parfaits, on fait la correspondance entre les indices du tableau T et les numéros
des nœuds de l'arbre binaire parfait correspondant.
Par exemple, l'information 7 (d'indice 0) est la racine de l'arbre associé
L'information 1 (d'indice 1) est le fils gauche de 7
L'information 6 (d'indice 2) est le fils droit de 7
Et de manière générale, un nœud d'indice i dans le tableau T aura ses fils (s'ils existent)
en position 2i+1 (fils gauche) et 2i+2 (fils droit).

En dessinant cet arbre binaire parfait, on remarque bien que ce n'est pas un tas (il ne
vérifie pas la propriété d'un tas).
Je rappelle qu'on travaille directement dans le tableau représentant l'arbre binaire
parfait.

8 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

Question b)- Comment transformer T en un tas ?

L'idée est simple (voir cours) : on parcourt le tableau de la droite vers la gauche. Les
feuilles (des arbres réduits à un élément) sont des tas. Ici dans T (de la droite à la
gauche), ce sont les nœuds contenant resp. 8, 11, 9, 10, 6 et 2
En suivant notre parcours dans le tableau de la droite à sa gauche, on tombera sur le
nœud 5 d'indice 4 dans le tableau : il s'agit de la racine d'un arbre binaire parfait (les
fils de 5 sont 11 et 8). Ce n'est pas un tas, on utilisera l'opération Entasser(T,4). Il sera
transformé en le tas de racine 11 (ses fils sont 5 et 8).
On continue de la même façon pour les autres sous-arbres : un arbre de racine en
position i ses fils sont des tas, on utilisera Entasser(T, i).

9 sur 17
 Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

Finalement, on obtient le tas suivant qui vérifie les propriétés d'un tas: T= {11,10,6,9,8,2,3,4,7,5,1}

Question c)- le déroulement du tri est le suivant :

On veut trier le tableau T. Par conséquent, dans une première phase on le transforme en
un tas (question précédente). Ensuite, on se base sur l'opération de suppression de
l'élément maximum au niveau d'un tas. C'est-à-dire, et comme on veut trier T dans
l'ordre croissant, on va répéter à chaque itération : échanger la racine du tas avec la
dernière information. Ignorer la dernière case du tableau (i.e., T privé de son dernier
élément qui est le maximum). Ce nouveau tableau n'est pas un tas, le problème se pose
au niveau de sa racine. Pour qu'il devienne un tas, on utilise Entasser(T,0). On s'arrête
lorsque le tableau est réduit à un seul élément. On remarquera finalement que l'on a
obtenu un tableau T trié dans l'ordre croissant.

10 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

Dans une première phase on le transforme en un tas:

Echanger la racine du tas avec la dernière information, et ignorer la dernière case du tableau

1)

11 sur 17
 Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

2)

Pour qu'il devienne un tas, on utilise Entasser(T,0):

3)
4)

5)

12 sur 17
 Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

1ère itération

La colonne en blue est ignorée.

6) 7)

Entasser

9)
8)

2ème itération

10) 11)

13 sur 17
 Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

12)

3ème itération

14)
13)

4ème itération

15) 16)

5ème itération

14 sur 17
 Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

17) 18)

6ème itération

19)
20)

7ème itération

21) 22)

8ème itération

15 sur 17
 Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

23) 24)

9ème itération

Notre tableau maintenant est réduit en un seul élément, donc on va s'arrêter ici: 10ème itération

Finalement, notre tas trié est sous la forme suivante:

Avec:

16 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°3 : Arbres]
Solution

Question d)- Ici, il s'agit de faire un simple parcours du tableau de son début à sa fin

Algorithme Appartient_Tas (T : Tas, e : Entier) : Entier

Entrées : un tas et un entier

Sortie : un entier
variables locales :

n, res : Entier

Début

n ! [Link]
res ! 0
i ! 1
tant que ((i<= n) et (res=0) faire

si ([Link][i]=e) alors
res ! 1
fsi

i ! i+1

ftq

retourner res;
Fin

On notera que le tas n'est pas bien adapté à la recherche d'informations !

17 sur 17
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°4 : Graphes :Première Partie]

Exercice n°1.
Un groupe d’amis organise une randonnée dans les grandes montagnes.

On a représenté par le graphe ci-dessus les sommets B, C, D, F, T, N par lesquels ils peuvent choisir
de passer.
Une arête entre deux sommets coïncide avec l’existence d’un chemin entre les deux sommets.
1) Donner la définition formelle de ce graphe
2) Déterminer le degré de chacun des sommets de ce graphe. Donner le résultat sous forme de
tableau
3) Ce graphe est –il connexe ? justifier

Exercice2
Une grande ville a créé un jardin pédagogique sur le thème de l’écologie, jardin qui doit être visité par
la suite par la majorité des classes de cette ville. Ce jardin comporte six zones distinctes correspondant
aux thèmes :
A. Eau B. Economie d’énergie C. Plantations et cultures locales
D. Développement durable E. Biotechnologies F. Contes d’ici (et d’ailleurs)
Ces zones sont reliées par des passages (portes) où sont proposées des questionnaires.
Le jardin et les portes sont représentés par le graphe ci-dessous (chaque porte et
donc chaque questionnaire est représenté par une arête)

Question préliminaire :
Si un visiteur répond à tous les questionnaires, à combien de questionnaires aura-t-il répondu ?
Autres questions :
1) Donner la matrice d’adjacence G associée à ce graphe
2) Le graphe est-il complet ? Est-il connexe ? Justifier
3) Donner la liste d’adjacence associée.
Exercice4 :
Considérons le graphe G décrit par le schéma ci-dessous :

a) Donner une représentation du graphe ci-dessus au moyen d'une liste d'adjacence,

puis au moyen d'une matrice d'adjacence.
b) Considérons un graphe G = (V;E) sans boucle triviale. On appelle matrice d'incidence du
graphe G, la matrice à IVI lignes et IEI colonnes, B = (bi;j ) définie par :

Donner une représentation du même graphe (ci-dessus) en matrice d'incidence.

Quels problèmes rencontre-t-on ?
c) Proposer un algorithme de construction de la matrice d'incidence à partir de la
liste d'adjacence d'un graphe, puis à partir de sa matrice d'adjacence.
d) Si BT désigne la transposée de B, que représente la matrice BBT ?

Exercice4 :
a) Dans chacune des trois représentations, quel temps faut-il pour déterminer si
deux sommets u et v donnés sont voisins ?.
b) Dans chacune des trois représentations, quel temps faut-il pour calculer le
degré sortant d'un sommet ? Même question pour le degré entrant ?

Exercice5 :
Réécrivez l'algorithme générique de parcours d'un graphe vu en cours de façon
adaptée à chaque représentation. Quel est le temps d'exécution, à chaque fois ?
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°4 : Graphes :Première Partie]

Solution
Exercice n°1.

1) Définition formelle du Graphe donné sur l schéma. On va le désigner par G.

G= (S, A) où S={B, C, D, F ,N, T } et

A={ (B ;C),(B ;F),(C ;D),(C ;F),(C ;T),(D ;F),(D ;T),(D ;N),(F ;N), (F ;T),(N ;T) }

2) Tableau représentatif des degrés des sommets

Sommets B C D F N T
Degrés 2 4 4 5 3 4

3) Ce graphe est connexe car tous les sommets peuvent être reliés entre
eux par (au moins) une chaî[Link] exemple, la chaîne BCDNTF contient
tous les sommets.
Exercice2
Question préliminaire :Il y a dix questionnaires car il y a dix arêtes.

1) la matrice d’adjacence associé à ce graphe est :

0 1 1 1 0 1
 
1 0 1 1 1 1
1 1 0 1 0 0
G= 
1 1 1 0 1 0
0 1 0 1 0 0
 
1 1 0 0 0 0 

2) Ce graphe est connexe car, pour chaque paire de sommets, il existe une
chaîne les reliant. Ce graphe n’est pas complet car, par exemple, les
sommets E et F ne sont pas adjacents.

1 sur 2
Université Mohammed V-Agdal Année Universitaire 2022/2023
Faculté des Sciences de Rabat MODULE SD
Département d'Informatique Semestre 4 (SMI4)

Travaux Dirigés de Structures de Données

[TD n°4 : Graphes :Première Partie]

Solution
3) La liste d’adjacence :

2 sur 2