Examen ALGOII 2010

|EXAMEN |
|Matière : Algorithmique & Structures des Données|Classes : TI1.1 ( 10 |
|II | |
|Enseignant(s) : I.MALLOUG, M. ELEUCH, H. HMANI, |Date : 11/06/2010 |
|R. BEN | |
|SLAMA, H. HADJ MOHAMED, M. K. KHOUJA, | |
|M. SALEM, A. BEN SALEM | |
|Documents : Non Autorisés |Durée : 1.5 heure |
Exercice 2 :
On se propose d'étudier un TAD (Type Abstrait de Données) nommé LDCC qui
se présente comme une Liste d'entiers Doublement Chainée et Circulaire
comme le montre la représentation schématique ci-dessous.
Chaque élément possède un précédent et un suivant. Ainsi, le précédent du
premier élément sera le dernier élément de la liste et le suivant du
dernier élément sera le premier élément de la liste.
|SDPF avec | |
|plusieurs | |
|éléments | |
| | |
|SDPF avec un | |
|seul élément | |
| | |
| | |
|SDPF vide | |
Comme toutes les structures de données dynamiques, on accède à cette
structure par l'intermédiaire d'un pointeur que l'on nommera ptLDCC. Ce
dernier pointe sur le premier élément de la liste.
Les opérations de manipulation du TAD sont les suivantes :
- Init : initialise une LDCC à vide.
- est_vide : vérifie si une LDCC est vide ou non
- consulter_tete : donne le premier élément de la LDCC
- consulter_queue : donne le dernier élément de la LDCC
- ajout_tete : ajoute un élément en tête de la LDCC
- ajout_queue : ajoute un élément en queue de la LDCC
- supprim_tête : supprime le premier élément de la LDCC
- supprim_queue : supprime le dernier élément de la LDCC
- longueur : donne le nombre d'éléments de la LDCC
- affiche : affiche sur écran les éléments de la LDCC
Questions :
1. Donner les structures de données nécessaire pour définir une LDCC.
2. Implémenter les opérations ci-dessous sous forme de fonction ou
procédure
3. Proposer un algorithme principal qui manipule une LDCC en faisant appel
aux fonctions et procédures ainsi implémentées. Exercice 2 :
Soit une pile P1 contenant une suite d'entiers.
1. Ecrire une procédure qui met dans une deuxième pile P2 les entiers pairs
de P1 et laisse dans P1 les entiers impairs. Attention, les entiers
doivent être dans le même ordre qu'au début.
Exemple :
| |
|16 |
|15 |
|14 |
|13 |
|12 |
|11 |
|10 |
| |
|16 |
|14 |
|12 |
|10 |
[ Avant ]
[ Après ]
| |
|15 |
|13 |
|11 | ( P1
P1 P2
2. Modifier la procédure précédente pour que l'ensemble des éléments de la
pile P2 soient dans l'ordre inverse de leur entrée dans la pile.
Exemple :
| |
|16 |
|15 |
|14 |
|13 |
|12 |
|11 |
|10 |
| |
|10 |
|12 |
|14 |
|16 |
[ Avant ]
[ Après ]
| |
|15 |
|13 |
|11 | (
P1 P1
P2 Bon Travail Barème prévisionnel :
Exercice 1 : 12 pts
Exercice 2 : 08 pts
----------------------- République Tunisienne
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Institut Supérieur des Etudes Technologiques de Mahdia
Département Technologies de l'Informatique ptSDPF
ptSDPF 2 ptSDPF 4 7 2