Correction Serie Exercices7 Revision [PDF]

Zitiervorschau

esprit

Série 7

►

Ecole Supérieure Privée d’Ingénierie et de Technologies

Module : Algorithmique II

Unité pédagogique : Algorithmique & Programmation

Séance : cours intégré

Classe(s) : 1A Année universitaire: 2021 - 2022

Exercice 1 

numéro

noeud

numéro de FilsG

numéro de FilsD

1

50

2

3

2

30

4

5

3

60

6

7

4

20

0

0

5

40

8

9

6

55

0

0

7

70

10

11

8

35

0

0

9

48

0

0

10

65

0

0

11

90

0

0

1. Dessiner l’arbre binaire de recherche correspondante au tableau ci-dessus

2. Quelle est la hauteur de l’arbre ? 4 (remarque : la hauteur est égale à 3 ) 3. Quelle est la taille de l’arbre ? 11 4. Afficher cet arbre binaire en adoptant un parcours préfixé, puis infixé, et ensuite postfixé. parcours prefixé: 50, 30, 20, 40, 35, 48, 60, 55, 70, 65, 90 parcours infixé: 20, 30, 35, 40, 48, 50, 55, 60, 65, 70, 90 parcours postfixé: 20, 35, 48, 40, 30, 55, 65, 90, 70, 60, 50 Exercice 2: Un parti politique est caractérisé par un nom (unique), le nom du président du parti, un certain nombre d'affiliés et un certain nombre de responsables. L’ensemble des partis sont organisés dans une liste doublement chainée. 1. Définir les structures nécessaires pour représenter l’ensemble des partis politiques. Type parti= Enregistrement nom, nompr: chaine [10] nbaffi, nbresp :entier fin Enregistrement cellule= Enregistrement val: parti precedent : *cellule suivant : *cellule Fin Enregistrement LS = *cellule LD = Enregistrement Tete: LS Queue: LS Fin Enregistrement

2. Écrire une procédure saisir_parti (Prt: *Parti) qui permet de remplir les données d'un parti. Le nombre de responsables d'un parti est toujours compris entre 1 et 50 et le nombre d’affiliés doit être supérieur ou égale au nombre de responsables. procédure saisir_parti (p: *parti) Début lire(p🡪nom, p🡪nompr) répéter lire (p🡪nbresp) jusqu’à (p🡪nbresp >1) et (p🡪nbresp p🡪nbresp) Fin

3. Écrire d’une manière récursive la fonction recherche_part (Lp: LD, NomPrt: chaîne): *cellule qui permet de retourner un pointeur sur l’élément de la liste contenant le parti dont le nom est passé en paramètre et NULL si le parti n’existe pas. Fonction Recherche_part (lp :LD, nomPrt :chaine) :*cellule Début Si (Vide_LD (Lp)) alors // si(lp=NULL) Recherche_part 🡨 NULL Sinon si (lp.tete🡪 val.nom = nomPrt) alors Recherche_part 🡨 lp.tete sinon lp.tete 🡨

(lp.tete 🡪suivant)

Recherche_part🡨 Recherche_part ( lp , nomPrt) fin si fin si Fin 4. Écrire une fonction ajouter_parti (Lp: LD, Prt: Parti): LD qui permet d’ajouter à la fin de la liste Lp le parti Prt s’il n’existe pas dans la liste.

Fonction ajouter_parti (lp :LD, Prt: parti): LD Variable Nouv :*cellule Parc :* cellule Debut Si ( Recherche_part (lp, Prt.nom) = NULL) alors Nouv🡨allouer (taille(cellule)) Si (Nouv=NULL) alors Ecrire (‘’ espace insufisant ‘’) Sinon Nouv🡪val 🡨prt Nouv🡪suivant 🡨NULL Nouv🡪precedent🡨NULL Si (Vide_LD (Lp)) Alors // Liste vide Lp.queue🡨Nouv Lp.tete🡨 Nouv Sinon // ajout à la fin *(Lp.queue).suivant🡨Nouv *Nouv.precedent🡨Lp.queue Lp.queue🡨 Nouv Finsi Finsi Finsi Finsi ajouter_parti←lp fin Fonction Vide_LD(L :LD) :Booléen Début Vide_LD🡨 (L.tete = Null) et (L.queue = Null) Fin

5. En utilisant la fonction recherche_part, écrire la fonction ajouter_affiliés ( Lp: LD, NomPtr: chaîne, nbAff: entier):LD qui permet d’augmenter le nombre d'affiliés d'un parti, dont le nom NomPtr est passé en paramètre, par la valeur du paramètre nbAff. Fonction ajouter_affiliés ( lp :LD , nomPtr : chaine, nbAff : entier) : LD Variable Element:*cellule Début Element 🡨

Recherche_part (lp, nomPtr)

Si ( Element= Null) alors Ecrire (‘‘ parti politique non existant’’) Sinon Element🡪 val.nbaffi= Element🡪 val.nbaffi+nbAff Finsi ajouter_affiliés 🡨

Lp

Fin 6. Écrire la fonction Supp_parti (Lp: LD, NomPtr: chaine): LD qui permet de supprimer un parti dont le nom est NomPrt de la liste Lp. Avant de supprimer le parti mentionné, on doit tout d’abord vérifier s’il existe dans la liste ou non. Fonction SUPP_Parti (Lp: LD, NomPtr: chaine): LD Var P: *cellule Début Si (Recherche_part (Lp, nomPtr) NULL) alors P🡨Lp.tete Tant que (pNULL) et (*P.val.nom NomPtr) P🡨*P.suivant Fin tantque si (P=Lp.tete) alors Lp🡨 SUPP_TETE(Lp) sinon si (P=Lp.queue) alors Lp🡨SUPP_QUEUE(Lp) sinon *(*P.précédent).suivant 🡨*P.suivant *(*P.suivant).précédent🡨*P.précédent Libérer(P) Fin si

Fin si Fin si SUPP_Parti🡨Lp Fin Fonction SUPP_TETE(L : LD) : LD Var P: *cellule Début Si (Vide_LD (Lp) = faux) alors P🡨L.tete Si (L.tete = L.queue) alors // liste contenant un seul element L.tete 🡨NULL L.queue 🡨 NULL sinon L.tete 🡨*(L.tete). suivant *(L.tete). precedent 🡨 NULL Finsi Liberer (P) Finsi SUPP_TETE ← L Fin Fonction SUPP_QUEUE(L : LD) : LD Var P: *cellule Début Si (Vide_LD (Lp)= faux) alors P🡨L.queue Si (L.queue = L.tete) alors // liste contenant un seul element L.tete 🡨NULL L.queue 🡨NULL Sinon L.queue 🡨*(L.queue).precedent *(L.queue). suivant 🡨NULL Finsi Liberer (P) Finsi SUPP_QUEUE← L Fin

7. Écrire d’une manière récursive la fonction Nbre_part (Lp: LD): entier qui permet de retourner le nombre total des partis existants dans la liste Lp. Fonction Nbre_part (Lp: LD): entier Début Si (Vide_LD (Lp)) alors Nbre_part 🡨 0 Sinon lp.tete 🡨

(lp.tete 🡪suivant)

Nbre_part 🡨

1+

Nbre_part ( lp)

fin si Fin

Considérons maintenant une file de partis. On se propose de remplir cette file par les n partis ayant le nombre d'affiliés le plus grand. 8. Définir la structure File de partis Element = Enregistrement      P: Parti    suivant : *Element FinEnregistrement File = Enregistrement Sommet : *Element Queue : *Element FinEnregistrement 9. Écrire la fonction Max_parti (Lp: LD): *cellule qui permet de retourner un pointeur sur l’élément de la liste contenant le parti ayant le nombre d’affiliés le plus grand. Fonction Max_parti (Lp: LD): *cellule Var maxP, P: *cellule Début P ← Lp.tete max ← *P.val.nbAffi Pour i de 1 à Nbre_parti (Lp) faire P ← *P.suivant Si (*P.val.nbAffi > max) alors max ← *P.val.nbAffi maxP n) F🡨

Enfiler_parti (Lp, n, F)

3 : écrire (‘‘Quitter ’’) Jusqu'à (choix=1) Jusqu'à (choix=3) Fin