CORRIGES
CONTROLE DE CONNAISSANCES
1- Une structure de données est une manière d’organiser les données pour faciliter les traitements.
-Un tableau est un regroupement de valeurs portant le même nom de variable qui sont repérées par un numéro. Il permet de ranger un nombre fini d’éléments de même type et selon une disposition bien définie.
2 -Limites des tableaux :
-les données sont du même type, on ne peut pas utiliser les entiers et les caractères dans un même tableau.
-Les données présentes dans un tableau sont contigües c.-à-d. côte-à-côte dans la mémoire, ce qui entraine que la taille du tableau est fixe.
-On ne peut ni ajouter une case à la fin d’un tableau, ni insérer une case au milieu.
3 : Tableau, enregistrement, listes chainées, piles, files.
4 : Graphes, arbres
EXERCICE I.
1-Une variable est un objet qui peut être modifié par une action au cours de l’exécution d’un algorithme.
2-i et s sont des variables de type entier.
3-la ligne n°2 déclare un tableau.
-la ligne n°5 initialise la variable S à 0.
4-Entête : ligne1
Déclaration des variables : ligne 2 et 3
Délimiteur de début : ligne 4
Corps de l’algorithme : lignes 5….14
Délimiteur de fin : ligne 15
5-instruction de lecture : Lire Notes(i) ;
-instruction d’écriture : Ecrire (« Moyenne : », S/9) ;
-instruction affectation: S ← S +Notes[i];
5- L’accès à un élément du tableau se fait par l’intermédiaire de son indice qui représente l’emplacement de l’élément dans le tableau : c’est l’accès direct.
NB : On parle d’accès séquentiel lorsque pour accéder à un élément donné, il faut parcourir tous les éléments précédents comme une bande magnétique.
EXERCICES II :
1-Structure itérative complète : lignes 6 à 8 Ou lignes 9 à 11.
2- Une structure itérative est dite complète si le nombre de répétition est connu d’avance alors qu’une structure itérative à condition d’arrêt a besoin d’une condition pour connaître la fin des itérations
3- k=1
Tant que (k<7) faire
N[k] ← N (k-1) + 2 ;
k←k+1 ;
Fin Tant que
4-Pour la structure Tant que la condition est au début donc on peut ne pas exécuter une seule action alors que pour la structure Répéter …jusqu’à on exécute la boucle au moins une fois.
5-
|
Ligne |
i |
k |
Instructions |
écran |
|
4 |
|
|
N[0]=1 |
|
|
7 |
|
1 |
N[1]=1+2=3 |
|
|
7 |
|
2 |
N[2]=3+2=5 |
|
|
7 |
|
3 |
N[3]=5+2=7 |
|
|
7 |
|
4 |
N[4]=7+2=9 |
|
|
7 |
|
5 |
N[5]=9+2=11 |
|
|
7 |
|
6 |
N[6]=11+3=13 |
|
|
10 |
|
|
|
3 5 7 9 11 13 |
6-Cet algorithme calcule et affiche les nombres impairs de 1 jusqu’à
13
EXERCICE III :
1-04 instructions.
2-
|
Ligne |
i |
Instructions |
écran |
|
5 6 |
|
tab [0] =1 ; |
|
|
8 |
2 |
tab [2] =1+1=2 |
|
|
8 |
3 |
tab [3] =2+1=3 |
|
|
8 |
4 |
tab [4] =3+2=5 |
|
|
8 |
5 |
tab [5] =5+3=8 |
|
|
8 |
6 |
tab [6] =8+5=13 |
|
|
8 |
7 |
tab [7] =13+8=21 |
|
|
10 |
0 à 7 |
|
1 1 2 5 8 13 21 |
3-cet algorithme calcule et affiche la liste : 1 1 2 5 8 13 21
EXERCICE IV :
1. Trouve est une variable de type booléen jouant le rôle de drapeau.
2. Recherche séquentielle
3. Recherche dichotomique
NB : La dichotomie, c’est le fait de couper en deux le tableau trié et de regarder dans quelle partie du tableau se trouve l’élément cherché. On recoupe en deux cette partie du tableau et on regarde à nouveau dans quelle moitié l’élément peut se trouver.
4. C’est le remplissage du tableau
5. n=5 nombreCherch=08
|
Ligne |
i |
Instructions |
écran |
|
|
|
n=5 trouve=0 |
|
|
16 |
0 |
I<5 ?vrai on entre dans la boucle Tant que… |
|
|
23 |
1 |
Notes [1]=08 ?faux on saute la boucle Si… I prend la valeur 2 |
|
|
|
2 |
Notes [2]=08 ? faux on saute la boucle Si… I prend la valeur 3 |
|
|
|
3 |
Notes [3]=08 ? Vrai on entre dans la boucle Si… |
|
|
18 |
|
Trouve prend la valeur 1 |
|
|
23 |
|
On entre dans la deuxième boucle Si… |
|
|
24 |
|
|
La note cherchée se trouve à l’indice 3 |
|
|
|
|
|
EXERCICE V:
1. Tri par insertion
2. Le tri par insertion considère chaque élément du tableau et l’insère à la bonne place parmi les éléments déjà triés. Ainsi, au moment où on considère un élément, les éléments qui lui e précèdent sont déjà triés tandis que les éléments qui le suivent ne sont pas encore triés.
3.tri par sélection, tri a bulle
4.Trace d’exécution :
On suppose que le tableau est déjà créé :27 10 12 8 11
|
N° ligne |
var1 |
Var2 |
Instructions |
Ecran |
|
|
j=2 |
i=1 |
Aux=10 i>0 et tab[1]=27 >12 VRAI, on entre dans la boucle tab[2]=27 02 |
27 27 12 8 11 |
|
|
i=0 |
i>0 FAUX, on n’entre pas dans la boucle tab[1]=10 |
10 27 12 8 11 |
|
|
|
j=3 |
i=2 |
Aux=12,i>0 et tab[2]=27>12 VRAI , on entre dans la boucle tab[3]=27 |
10 27 27 8 11 |
|
|
|
i=1 |
i>0 et tab[1]=10 >10 FAUX, on n’entre pas dans la boucle tab[2]=12 |
10 12 27 8 11 |
|
|
j=4 |
i=3 |
Aux=8 ,i>0 et tab[3]=27>8 VRAI, on entre dans la boucle tab[4]=27 |
10 12 27 27 11 |
|
|
|
i=2 |
i>0 et tab[2]=12>8 VRAI, on entre dans la boucle tab[3]=12 |
10 12 12 27 11 |
|
|
|
i=1 |
i>0 et tab[1]=10>8 VRAI, on entre dans la boucle tab[2]=10 |
10 10 12 27 11 |
|
|
|
i=0 |
i>0 FAUX, on n’entre pas dans la boucle tab[1]=8 |
8 10 12 27 11 |
|
|
j=5 |
i=4 |
Aux=11,i>0 et tab[4]=27>11 VRAI, on entre dans la boucle tab[5]=27 |
8 10 12 27 27 |
|
|
|
i=3 |
i>0 et tab[3]=12>11 VRAI, on entre dans la boucle tab[4]=12 |
8 10 12 12 27 |
|
|
|
i=2 |
i>0 et tab[2]=10>11 FAUX, on n’entre pas dans la boucle tab[3]=11 |
8 10 11 12 27 |
EXERCICE VI:
1- Un enregistrement est un type de données défini par l’utilisateur qui permet de regrouper un nombre fini d’éléments de types éventuellement différents sous un nom commun.
2- Lignes 2 à 7
3- pers1 et pers2 sont des variables d’enregistrement.
4- L’accès à un champ d’enregistrement se fait à l’aide de l’opérateur’’ .’’ alors que l’accès à un élément d’un tableau est l’accès direct
5- pers1.nom ← ‘’Fati’’
pers1.age ← 20
EXERCICE VII :
1- La ligne 9 déclare un tableau d’enregistrement.
2- L’opérateur ‘’. ‘’ permet l’accès à un élément d’un enregistrement.
3-Saisit et affiche deux caractéristiques d’un élément chimique.
EXERCICE VIII :
1- Algorithme InitialiseTableau
tab : Tableau [0…7] de réels ;
var i entier ;
Début
Pour i de 0 à 7 Faire
tab[i] ← 0 ;
FinPour
Pour i de 0 à 7 Faire
Afficher tab[i] ;
FinPour
Fin
2- Algorithme AfficheTableau
T : Tableau [5] d’entiers ;
var i : entier ;
Début
Pour i de 0 à 5 Faire
T[i] ← i*i ;
FinPour
Pour i de 0 à 5 Faire
Ecrire T[i] ;
FinPour
Fin
EXERCICE IX :
.
1- Type
Annuaire=Enregistrement
Nom : chaine
Num_téléphone: entier
Adresse : chaine
FinAnnuaire
2-var pers1, pers2 : Annuaire
Pers1.nom
Pers1.adresse,
Pers1.num_téléphone
EXERCICE X:
1-
Type Complexe=Enregistrement
P_réelle :réel ;
P_imaginaire :réel ;
Fin Complexe
2-
Z’ : Complexe ;