Rattrapage + Solution
Rattrapage + Solution
Rattrapage + Solution
3. Procedure CreerABR( Var R : ptrN, n : entier) (0.5 3. Procedure CreerABR( Var R : ptrN, n : entier) (0.5
point) point)
R Nil Si (n>0) alors
Pour i 1 à n faire Lire (x)
Lire (x) R InsererABR(R, x)
R InsererABR(R, x) CreerABR(R, n-1)
FP FSi
7. Fonction SupprimerMin (R :ptrN) : ptrN (1 point) 7. Fonction SupprimerMin (R :ptrN) : ptrN (1 point)
Si (R = Nil) alors retourner (Nil) Si (R = Nil) alors retourner (Nil)
Sinon Sinon
Si (FG(R)=Nil) alors //min se trouve à la racine Si (FG(R)≠Nil) alors
Q R Aff_FG(R, SupprimerMin(FG(R))
R FD(R) Retourner (R)
Sinon Sinon
//rechercher le minimum D FD(R)
P Nil ; Q R libererNoeud(R)
TQ (FG(Q) ≠ Nil) faire retourner (D)
P Q ; Q FG(Q) FSi
Aff_FG(P, FD(Q)) //le chaînage
FSi
libererNoeud(Q)
retourner (R)
FSi
2/8
Exercice 2 (1 + 1.5
1.5 + 1.5 = 4 points) :
Soit « IND » un index des mots qui est défini par un tableau « Tab »de taille n où chaque case du tableau
« Tab » contient un entier qui représente la longueur du mot et un pointeur vers une liste linéaire chaînée
unidirectionnelle. Cette liste contient des mots de même longueurs à raison d’un mot par maillon. Le
tableau est trié selon l’ordre décroissant de la longueur du mot. Les listes sont triées par ordre alphabétique
(ordre croissant de A à Z).
type maillon = structure Const Max = 100 ;
val : chaîne de caractères type index = structure
suiv : * maillon Tab: Tableau [Max] de case
Fin Queue :entier
type ptrM = * maillon Fin
type case = structure
long : entier
tête :ptrM
Fin
Dans le but de supprimer un mot dans cet index, il est demandé d’écrire les modules suivants:
1. La fonction récursive « RechDichoTab » qui permet de faire la recherche dichotomique et de retourner
l’indice de la case du Tab contenant une longueur donnée (soit x) si elle existe, sinon elle retourne -1.
2. La fonction récursive « SuppLLC » qui permet de supprimer dans une liste linéaire chaînée ordonnée un
mot s’il existe.
3. En utilisant les fonctions précédentes, écrire la procédure « Supprimer (var ID : index, y : chaîne de
caractère) » qui permet de supprimer un mot « y » de l’index « ID ». Si la liste contenant le mot « y » devient
vide alors la case correspondante à sa longueur est supprimée du tableau Tab.
INDICATION. Vous pouvez utiliser les fonctions suivantes :
a. Longch(ch : chaine de caractère) : entier qui retourne le nombre de caractère dans ch.
b. Cmpch (ch1, ch2 : chaine de caractère) : entier qui compare les chaînes ch1 et ch2 et retourne une valeur négative
si (lexicalement) ch1 < ch2, nulle si ch1 = ch2 et positive si ch1 > ch2.
Solution Exercice 2 :
Fonction RechDichoTab (Tab : tableau[] de case, D, F,x : entier) : entier
Si (D>F) alors retourner (-1) (0.25)
Sinon
M (D+F) div 2
Si Tab[M].long = x alors retourner (M) (0.25)
Sinon
Si Tab[M]>x alors retourner (RechDichoTab (Tab, M+1, F,x)) (0.25)
Sinon (RechDichoTab (Tab, D, M-1,x)) (0.25)
Fin
Fonction SuppLLC (L:ptrM, y : chaine de caractère) : ptrM
Si (L = Nil) ou cmpch(valeur(L), y)>0) alors retourner (Nil) (0.5)
Sinon
Si (cmpch(valeur(L), y)<0)) alors Aff_suiv (L, SupprimerLLC(suivant(L), x) ) ; Retourner (L) (0.5)
Sinon P L ; L suivant (L) ; libérer (P) ; Retourner (L) (0.5)
Fin
3/8
Procédure Supprimer (var ID : index, y :chaine de caractère)
//1. Rechercher la case du tab qui contient des mots de même longueur que y
i RechDichoTab (ID.Tab, 0, ID.Queue, Longch(y)) ; (0.25)
//2. s’il existe déjà des mots de même longueur que y
Si (i ≠ -1) alors (0.125)
//3. supprimer le mot de la liste
ID.Tab[i].Tete SuppLLC(ID.Tab(i].Tete, y) (0.25)
//4. Si la liste devient vide
Si (ID.Tab[i].Tete = Nil) (0.125)
// 5. Faire un décalage à gauche (0.25)
Pour j i à ID.Queue-1 faire
ID.Tab[j] ID.Tab[j+1]
//6. Réinitialiser la dernière case (0.25)
ID.Tab[j].long 0
ID.Tab[j].Tete Nil
//7. Décrémenter la taille du tableau (0.25)
ID.Queue-- ;
4/8
L2 Informatique Algorithmique et Structures de données 2017-2018
6/8
Exercice 4 (2.5 + 2.5
2.5 = 5 points) :
Soit P une pile d’entiers implémentée de manière statique en utilisant un tableau de taille « max ».
Bon courage
8/8