R6publlque dù Sénégal
Mlnlstètê de l &ntèlgnêment supérlèur et dê l'lnnovotton
1
Annêê scolalr• 2023 .. 2024
Examen de structure da données
~~OER. ~~
.~~~
,.:: . Durée 04h
;;;
0:
0 '
•' "1~ . ~
\~"i~j ••••••
Chargé de cours : Dr BARRO
<.i.,.o~
Unité de formation et de recherche en sciences et technologies
Département Mathématique et Informatique
Exercice l (4 points)
1. Ecrire un programme qui lit la dimension N d'un tableau Tdu type entier (dimension maximale:
50 composantes), remplit le tableau par des valeurs entrées au clavier et affiche le tableau.
2. Ecrire un algorithme Tri_à_bulles qui permet de parcourir le tableau, et comparer les couples
d'éléments successifs. Lorsque deux éléments successifs ne sont'pas dans l'ordre çroissant les
permuter. Après chaque parcours complet du tableau, recommencer l'opération ju_ s qu'aucuoe
pP.rm11tntion n'n lie11 r,endant un parcours. ·
3. Rechercher dans le tableau, par la méthode dichotomique, une valeur VAL entrée au clavier.
4. Calculer et afficher ensuite la somme des éléments du tableau.
5. Ranger les éléments du tableau T dans l'ordre inverse sans utiliser de tableau d'aide. Afficher le
tableau résultant.
Exercice 2 ( 10 points)
1. Ecrire un programme qui définit une structure etudiant où un étudiant est représenté par son
norn, son prénom et une note.
2. Ecrire une procédure «Creatliste » permettant de créer une liste chainée simple de n étudiants
entrées par l'utilisateur. f'~
3. Ecrire une procédure« Affichliste » permettant de pa[courir et d'afficher fes éléments de la
liste~- -- ---- _
4. Ecrire une procédure« AffichNoms » permettant de parcourir et d'afficher tous les étudiants
ayant une note supérieure ou égale à l Osur 20.
5. Ecrire une procédure« lnsertTete » permettant d'insérer un étudiant en tête de la liste.
6. Ecrire une fonction « [Link] » qui vérifie si un étudiant e figure dans la liste.
7. En supposant qu'un étudiante existe une seule fois dans la liste. Ecrire une procédure«
supprimer» permettant de supprimer cet étudiant de la liste.
8. Ecrire une procédure qui permet d'inverser la liste.
9. Ecrire une procédure qui permet de trier les éléments de la liste dans l'ordre croissant et suivant
leurs-notes.
10. Tester vos sous programmes dans la fonction principale.
Exercice 3 (6 points)
Ecrire un programme qui gère une pile à l'aide d'une liste chainée. Pour cela, vous créerez un type de
structure de pile à l'aide d'une liste chainée dont les éléments sont des entiers. Le pointeur d'un
élément de la pile pointe vers l'élément précédent.
Le programme se composera de plusieurs fonctions :
e Une fonction de .cr.éat!oÀ-creer_pile qui retourne un pointeur d~ type pile, nu:.
• Une fonction vide qui retourne Osi la pile, passée en paramètre, est non vide, et un nombre
différent de Odans le cas contraire.
• Une fonction sommet qui retourne le sommet de la pile passée en paramètre.
• _ U!1~ fonction empiler qui empile l'entier val, passé en paramètre. à la pile p. également passée
en paramètre.
• Une fonction desempiler qui supprime le sommet de la pile p. passée en paramètre. La
mémoire occupée par le précédent sommet de la pile est libérer.
• Une fonction afficher_récursive qui affiche le contenu de la pile de manière récursive.
Tester votre pro~ramme sur la fonction principale.
Bonne chance !
