Algorithmique et Structures de Données II
Examen Session Principal 2022
(Correction)
Exercice 1 : Arbre (7 pts)
Soit A un Arbre binaire ordonné (de recherche) contenant des valeurs entières.
A
99
74 140
35 80 200
76 87 160
Travail demander (En langage C) :
1. Définir et Déterminer le résultat de trois types de parcours en profondeur vue dans le
cours.
Parcours infixé : sous-arbre-gauche / racine/ sous-arbre-droit
35-74-76-80-87-99-140-160-200
Parcours préfixé : racine/ sous-arbre-gauche / sous-arbre-droit
99-74-35-80-76-87-140-200-160
Parcours postfixé : sous-arbre-gauche / sous-arbre-droit/ racine
35-76-87-80-74-160-200-140-99
2. Dessiner le nouvel arbre A après l’insertion d’une valeur x=65.
99
74 140
35 80 200
65 76 87 160
3. Définir la structure Arbre d’entier.
Typedef struct nœud
{
int val ;
Struct nœud *FG ;
Struct nœud *FD ;
}Nœud ;
Typedef Nœud* Arbre ;
4. Ecrire un sous-programme récursif « Insèrer_valeur» qui permet d’insérer une valeur
donnée « x » dans A.
Void inserer_valeur(Arbre *racine, int x) else
{ {
Nœud *nouveau ; If(x<*racine.val)
If(racine==NULL) inserer_valeur(*racine.FG, x) ;
{ else
Nouveau=(Nœud *)malloc sizeof(Nœud) ; inserer_valeur(*racine.FD, x) ;
If(nouveau) }
{ *nouveau.val=x ; }
*nouveau.FG=NULL ;
*nouveau.FD=NULL ;
racine=nouveau ;
}
else printf("pas d’espace") ;
}
5. En utilisant les actions précédentes, écrire le programme principal qui construit l’arbre A
de taille N=20 et affiche ses éléments dans l’ordre croissant.
Void main() Void affiche_infixé(Nœud *racine)
{ {
Arbre racine ; If(racine !=NULL)
int x, i, N=20 ; Affiche_infixé(*racine.FG) ;
For(i=0; i<N; i++) printf("%d", *racine.val) ;
printf(“donner la valeur %d"\n, i) ; Affiche_infixé(*racine.FD) ;
scanf("%d”,&x); }
inserer_valeur(&racine,x) ;
affiche_infixé(racine) ;
}
2
Exercice 2 : (13points)
Dans le cadre de la protection contre la pandémie de COVID-19, l’état Tunisien désire de gérer
la vaccination de ces citoyens à travers la plateforme « Evax.tn ». Pour l’inscription sur cette
plateforme chaque citoyen fournit les informations suivantes :
- NumCIN : numéro carte d’identité national
- Nom : nom du citoyen
- Prenom : prenom du citoyen
- Age : age du citoyen
- Ville : lieu de vaccination
- At_cov : avez-vous été atteint de la COVID-19 ? (oui ou bien non)
- Mal_chro : Etes-vous atteint d’une maladie chronique comme diabète,
hypertension, etc ? (oui ou bien non)
- Per : faites-vous partie du personnel de santé ? (oui ou bien non )
Partant de l’hypothèse qu’une vaccination généralisée à la population n’est pas possible
immédiatement, le groupement par ordre de priorité s’avère primordiale, il est déterminé
automatiquement selon des critères fixés à l’avance. Le tableau suivant récapitule le
groupement selon l’ordre des priorités et les critères.
Tableau 1: priorités & critères
Priorités Critères
P1 Citoyens âgés plus que 60 ans
P2 Professionnels de la santé et citoyens âgés entre 50 et 59 ans ayant une maladie chronique
P3 Citoyens âgés entre 50 et 59 ans n’ayant pas une maladie chronique
P4 Les autres citoyens
P5 Citoyens atteint de la COVID-19
Travail demander (En algorithmique) :
1. Définir la structure de données nécessaire pour un Citoyen.
Structure Citoyen Mal_chro : booleen
NumCIN: entire Per : booleen
Nom: chaine[50] Priorite: entire
prenom: chaine[50] Fin structure
age : entier
ville: chaine[50]
At_cov : booleen
2. Ecrire un sous-programme Saisir_Citoyen qui saisit les informations nécessaires d’un seul
patient et détermine sa priorité.
Void saisir_citoyen(var C : citoyen)
Debut
Ecrire ("donner le nom, le prenom, l’age, le numero de la carte d’identité et la ville de vaccination ")
Lire(C.Nom, C.Prenom, C.age, C.NumCIN, C.ville)
Ecrire("avez-vous atteint de la COVID-19 ?")
Lire(C.At_cov)
Ecrire("êtes-vous atteint d’une maladie chronique ?")
Lire(C.Mal_chro)
Ecrire("faites-vous partie du personnel de santé")
Lire(C.Per)
Si(C.age>=60)alors
C.Priorite 1
sinon
Si(C.age>=50) alors
Si((C.Mal_chro= "oui") ou C.Per="oui" ) alors
C.Priorite 2
Sinon
C.Priorite 3
finsi
sinon
si(C.At_cov="oui") alors
C.Priorite 5
Sinon
C.Priorite4
Finsi
Finsi
Finsi
Fin
3. Ecrire un sous-programme Afficher_Citoyen qui affiche les informations d’un seul
citoyen.
procedure affiche_citoyen( C : citoyen)
Debut
Ecrire("Numero Carte d’identité :", C.NumCIN)
Ecrire ("le nom et le prenom : ", C.Nom, C.Prenom)
Ecrire(" l’age du patient :", C.age)
Ecrire ("la ville de vaccination ", C.ville )
Ecrire("le patient atteint de la COVID-19(oui ou non) ?", C.At_cov )
Ecrire("le patient atteint d’une maladie chronique (oui ou non)?", C.Mal_chro)
Ecrire("le patient est un personnel de santé(oui ou non) ?", C.Per)
Ecrire("le patient est de priorité :", C.Priorite)
4
Pour gérer le processus de vaccination en le modélisant par une liste chainée de citoyens
« liste_Cit ». Cette dernière est organisée selon les priorités ( P1, P2, …P5) et l’ordre
d’inscription.
Exemple : une nouvelle inscription de priorité P2 sera placée à la fin du groupe P2 et avant
le premier du groupe P3
4. Définir la structure « liste_Cit » pour gérer le processus de vaccination.
Structure noeud
Val :Citoyen
Suiv : ↑ nœud
finStructure
type liste_Cit : ↑ nœud
5. Ecrire un sous-programme Ajouter_Citoyen qui ajoute une nouvelle inscription à la liste.
Procedure ajouter_citoyen(var tete :List_Cit)
Var C :Citoyen
Nouveau : List_Cit
Courant, precedent : List_Cit
Debut
Saisir_citoyen(C)
Allouer(nouveau)
*nouveau.valC
*nouveau.suiv Nil
Si (tete=Nil) alors
tetenouveau
else
courant*tete.suiv
precedenttete
Tantque(*courant.val.priorite<= *nouveau.val.priorite et*courant.suiv <> Nil) faire
Precedentcourant
Courant*courant.suiv
finTantque
si (*courant.val.priorite > *nouveau.val.priorite) alors
*precedent.suivnouveau
*nouveau.suivcourant
Sinon
*courant.suivnouveau
Finsi
Finsi
6. Ecrire un sous-programme Nb_Citoyen qui affiche le nombre total de citoyen inscrit ainsi
que le nombre de chaque priorité.
procedure Nb_citoyen( tete : List_Cit)
var courant : List_Cit
Np, N, i : entier
Debut
N0
couranttete
Pour i de 1 à 5 faire
Np0
Tantque(*courant.val.priorite=i et courant <>Nil) faire
NpNp+1
courant*courant.suiv
finTanque
si (*courant.val.priorite<>i) alors
ercire("le nombre des citoyens de priorité", i, "est", Np)
NN+Np
Finsi
Finpour
Ecrire("le nombre total des citoyen est :", N)
Fin
7. Ecrire un sous-programme Vacc_citoyen qui élimine un citoyen ayant pris une dose et le
place en tête d’une nouvelle liste des citoyen vaccinées.
procedure Vcc_citoyen( Var tete, tete_Vcc : List_Cit)
var courant : List_Cit
Debut
Si(tete<>Nil) alors
couranttete
tete*tete.suiv
si(tete_Vcc<>Nil) alors
*courant.suivtete_Vcc
tete_Vcc courant
sinon
tete_Vcccourant
*courant.suivNil
Finsi
Sinon
Ecrire("la liste est vide")
finsi
Fin
6
8. Ecrire un sous-programme Affiche_Vacc qui affiche les informations des citoyens
vaccinées.
procedure Affiche_Vacc( tete_Vcc : List_Cit)
var courant : List_Cit
Debut
Si(tete_Vcc<>Nil) alors
couranttete_Vcc
Tantque(*courant<>Nil)faire
Affiche_Citoyen(*courant.val)
courant*courant.suiv
FinTantque
Sinon
Ecrire("la liste est vide")
finsi
Fin
