USTTB-FST INF1201- Licence MPCI - S2

DER de Mathématique et Informatique Année universitaire 2019-2020

Examen d’Algorithmique et programmation (INF1201)
Première session Durée : 2h

Les documents et supports électroniques ne sont pas autorisés. Les algorithmes et programmes C à écrire doivent être
bien détaillés et bien structurés. Les exercices sont indépendants et l’épreuve est notée sur 20.

Exercice 1 (8 points)
a) Ecrire l’algorithme d’une procédure, nommée inverseTableau, qui prend en paramètre un tableau d’entiers
tab et sa taille n et inverse l’ordre de ses éléments, c’est-à-dire, le premier élément du tableau deviendra le
dernier et vice-versa, le deuxième élément deviendra l’avant-dernier et vice-versa, et ainsi de suite. On
n’utilisera pas de tableau d’aide ou intermédiaire.
b) Ecrire un programme C qui implémente la procédure inverseTableau proposée dans a).
c) Ecrire l’algorithme d’une fonction, nommée rechercheElement, qui prend en paramètre un tableau
d’entiers tab, sa taille n et un entier x. La fonction déterminera, à travers une recherche séquentielle, si x
est un élément de tab. Elle retournera la position (indice) de x s’il appartient à tab et -1 sinon.
d) Ecrire un programme C qui implémente la fonction rechercheElement proposée dans c).

Exercice 2 (6 points)
On considère l’algorithme suivant de tri à bulles :
Algorithme 1 : Tri à bulles
Procedure void triBulles (entier tab[ ], entier n)
entier i, j, temp ;
pour (i de n-1 à 1) faire
pour (j de 0 à i-1) faire
si (tab[j+1] < tab[j]) alors
temp tab[j] ;
tab[j] tab[j+1] ;
tab[j+1] temp ;

a) Faire tourner l’algorithme 1 de tri à bulles ci-dessus sur le tableau {7,3,-4,2,-5,1,0}.

b) Ecrire un programme C qui implémente la procédure triBulles.

Exercice 3 (6 points)
On considère l’algorithme suivant de tri par insertion :
Algorithme 2 : Tri par insertion
Procedure void triInsertion (entier tab[ ], entier n)
entier i, c, k ;
pour (i de 1 à n-1) faire
c tab[i] ;
k i-1 ;
tant que (k >= 0 et tab[k] > c) faire
tab[k+1] tab[k] ;
k k-1 ;
tab[k+1] c;

a) Faire tourner l’algorithme 2 de tri par insertion ci-dessus sur le tableau {2,0,3,1,-1,5,-1}.
b) Ecrire un programme c qui implémente la procédure triInsertion.

Fin
 Correction :
Exercice 1 (8 points)
a) Ecrivons l’algorithme d’une procédure, nommée inverseTableau, qui prend en paramètre un tableau
d’entiers tab et sa taille n et inverse l’ordre de ses éléments, c’est-à-dire, le premier élément du tableau
deviendra le dernier et vice-versa, le deuxième élément deviendra l’avant-dernier et vice-versa, et ainsi de
suite. On n’utilisera pas de tableau d’aide ou intermédiaire.
Algorithme : inverse tableau
Procedure void inverseTableau (entier tab[ ], entier n)
entier i, temp ;
pour (i de i=0 à n/2) faire
temp tab[i] ;
tab[i] tab[n-i-1] ;
tab[n-i-1] temp ;

b) Ecrivons un programme C qui implémente la procédure inverseTableau proposée dans a).

c) Ecrivons l’algorithme d’une fonction, nommée rechercheElement, qui prend en paramètre un tableau
d’entiers tab, sa taille n et un entier x. La fonction déterminera, à travers une recherche séquentielle, si x
est un élément de tab. Elle retournera la position (indice) de x s’il appartient à tab et -1 sinon.

d) Ecrivons un programme C qui implémente la fonction rechercheElement proposée dans c).

Kandé TRAORE, étudiant à la faculté des sciences et techniques, est l’auteur de ce

document.

2
Exercice 2 (6 points)
a) Faisons tourner l’algorithme 1 de tri à bulles sur le tableau {7,3,-4,2,-5,1,0}.
i j Tab[j+1] Tab[j] Tab[j+1]<tab[j] Tableau
6 0 3 7 OUI {3,7,-4,2,-5,1,0}
1 -4 7 OUI {3,-4 ,7,2,-5,1,0}
2 2 7 OUI {3,-4,2,7,-5,1,0}
3 -5 7 OUI {3,-4,2,-5,7,1,0}
4 1 7 OUI {3,-4,2,-5,1,7,0}
5 0 7 OUI {3,-4,2,-5,1,0,7}
5 0 -4 3 OUI {-4,3,2,-5,1,0,7}
1 2 3 OUI {-4,2,3,-5,1,0,7}
2 -5 3 OUI {-4,2,-5,3,1,0,7}
3 1 3 OUI {-4,2,-5,1,3,0,7}
4 0 3 OUI {-4,2,-5,1,0,3,7}
4 0 2 -4 NON
1 -5 2 OUI {-4,-5,2,1,0,3,7}
2 1 2 OUI {-4,-5,1,2,0,3,7}
3 0 2 OUI {-4,-5,1,0,2,3,7}
3 0 -5 -4 OUI {-5,-4,1,0,2,3,7}
1 1 -4 NON
2 0 1 OUI {-5,-4,0,1,2,3,7}
2 0 -4 -5 NON
1 0 -4 NON
1 0 -4 -5 NON

Le tableau après exécution de l’algorithme tri à bulles est {-5,-4,0,1,2,3,7}.

b) Ecrivons un programme C qui implémente la procédure triBulles.

Exercice 3 (6 points)
a) Faisons tourner l’algorithme 2 de tri par insertion ci-dessus sur le tableau {2,0,3,1,-1,5,-1}.

I c k tab[k] k>=0 et tab[k]>c Tableau

1 0 0 2 OUI {2,2,3,1,-1,5,-1}
-1 ! NON {0,2,3,1,-1,5,-1}
2 3 1 2 NON {0,2,3,1,-1,5,-1}
3 1 2 3 OUI {0,2,3,3,-1,5,-1}
1 2 OUI {0,2,2 ,3,-1,5,-1}
0 0 NON {0,1,2 ,3,-1,5,-1}
4 -1 3 3 OUI {0,1,2 ,3,3,5,-1}
2 2 OUI {0,1,2 ,2,3,5,-1}
1 1 OUI {0,1,1 ,2,3,5,-1}
0 0 OUI {0,0,1 ,2,3,5,-1}

Kandé TRAORE, étudiant à la faculté des sciences et techniques, est l’auteur de ce

document.

3
 -1 ! NON {-1,0,1 ,2,3,5,-1}
5 5 4 3 NON {-1,0,1 ,2,3,5,-1}
6 -1 5 5 OUI {-1,0,1 ,2,3,5,5}
4 3 OUI {-1,0,1 ,2,3,3,5}
3 2 OUI {-1,0,1 ,2,2,3,5}
2 1 OUI {-1,0,1 ,1,2,3,5}
1 0 OUI {-1,0,0 ,1,2,3,5}
0 -1 NON {-1,-1,0 ,1,2,3,5}

b) Ecrivons un programme c qui implémente la procédure triInsertion.

Kandé TRAORE, étudiant à la faculté des sciences et techniques, est l’auteur de ce

document.