Synthèse¶

Exercices¶

Exercice 1 : structures et interfaces¶

A. Quelle opération ne fait pas partie de l’interface d’une pile ?
1. ajouter un élément à la pile
2. supprimer l’élément le plus récent de la pile
3. retirer l’élément le plus ancien de la pile

B. Quelle opération ne fait pas partie de l’interface d’une file ?
1. ajouter un élément à la file
2. supprimer l’élément le plus récent de la file
3. retirer l’élément le plus ancien de la file

C. Pour que deux implémentations du même type abstrait soient interchangeables, il faut que :
1. la complexité en temps soit la même dans les deux cas
2. l’interface de la structure de données soit la même dans les deux cas
3. les deux implémentations soient parfaitement identiques

Exercice 2 : choisir une structure de données¶

Associer une structure de données adaptée à chaque situation.

Dans une administration, on souhaite insérer dans une structure de données les doléances reçues afin de les traiter selon leur ordre d’arrivée. On aura plutôt intérêt à les enregistrer dans :
a) une liste b) une pile c) une file
Pour un logiciel, on doit enregistrer la liste des actions dans une structure de données de sorte à voir la dernière action en priorité. On enregistrera donc les actions dans :
a) une liste b) une pile c) une file
On souhaite insérer dans une structure de données les différentes hauteurs d’un arbre au fil des années sans y insérer les années. La structure de données la plus adaptée est :
a) une liste b) une pile c) une file

Exercice 3 : algorithmes sur les files et les piles¶

Implémentation File
Implémentation Pile

Dans ces deux questions, on utilise une implémentation des structures en POO. Pour tester les fonctions, il faut importer les classes correspondantes dans le fichier de travail.

Les structures ont les primitives (ici des méthodes) usuelles :

Pour les files : enfiler(elt), defiler(), est_vide() testant si la file est vide. f = File() crée une nouvelle file.
Pour les piles : empiler(elt), depiler(), est_vide() testant si la file est vide. p = Pile() crée une nouvelle file.

On dispose d’une file contenant des entiers, écrire une fonction qui renvoie une file dont on aura enlevé les nombres impairs, mais dont les nombres pairs sont dans le même ordre qu’initialement.

###
On dispose d’une pile contenant des entiers, écrire une fonction qui renvoie une pile dont on aura enlevé les nombres pairs, mais dont les nombres impairs sont dans le même ordre qu’initialement.

###

Exercice 4 : synthèse¶

Structure	Définition	Cas d'utilisation	Accès élément (coût)	Ajout élément (coût)
Liste chaînée
Tableau statique
Tableau dynamique
File
Pile
Tableau associatif