8 - Exercices Files
Attention, le soin est noté et les codes markdown identiques seront sanctionnés à moins de noter clairement que vous avez travaillé avec un autre élève de la classe.
1 - Principe
01° Que veut dire FIFO ? Que veut dire LIFO ?
02° La file suit-elle le précepte FIFO ou LIFO ?
03° On insére chronologiquement d'abord 5, puis 25 puis 50 dans une file. On désire lire l'avant de cette file. Quel élément va-t-on obtenir ?
2 - Interface non mutable / immuable
On considère d'abord une interface permettant d'interagir avec une file non mutable (on dit immuable en français).
Voici les 5 fonctions d'interface qu'on vous propose d'utiliser :
nouvelleFile() -> File: on crée une nouvelle file vide.estVide(f:File) -> bool: renvoie un booléen qui vaut True si la file f transmise est une file vide.enfiler(elt:Elt, f:File) -> File: on renvoie une file en rajoutant l'élément elt en entrée dans f..defiler(f:File) -> File: on supprime l'élément en position de sortir et renvoie la nouvelle file f.lireAvant(p:File) -> Elt: on renvoie l'élément en sortie(sans le supprimer ici). La fonction n'est définie que si la file n'est pas vide normalement.
04° Quel élément constitue l'arrière de la file construite à l'aide du faux langage ci-dessous ? Quel élément forme l'avant ?
Attention : pensez bien à regarder les fonctions d'interface pour être certain de ce qu'elles font.
1
2
3
4
5 | |
05° Même question : que contiennent Avant et Arrière à la fin de cette séquence d'instruction ?
1
2
3
4
5 | |
3 - Interface mutable / muable
On donne cette fois l'interface permettant d'interagir avec une file mutable.
Voici les 5 fonctions d'interface qu'on vous propose d'utiliser :
nouvelleFile() -> File: on crée une nouvelle file vide.estVide(f:File) -> bool: renvoie un booléen qui vaut True si la file p transmise est une file vide.enfiler(x:Elt, f:File) -> None: on rajoute un élément à l'arrière de la file en modifiant la file en place. On ne renvoie donc rien.defiler(f:File) -> Elt: on supprime l'avant en modifiant la file en place et on renvoie l'élément qu'on vient de sortir de la file.lireAvant(p:File) -> Elt: on renvoie l'élément en sortie(sans le supprimer ici). La fonction n'est définie que si la file n'est pas vide normalement.
06° Quelle est la grosse différence de la version mutable de la fonction enfiler (par rapport à la fonction immuable) ?
Expliquer pourquoi il suffit de taper ceci dans la version mutable :
1
2 | |
07° Quelle est la grosse différence de la version mutable de la fonction defiler (par rapport à la fonction immuable) ?
Pensez bien à analyser ce que retourne cette fonction par rapport à la version immuable.
08° Fournir le code permettant de créer une file dans laquelle on insère dans l'ordre.
- D'abord 45 (ce sera donc l'avant)
- Puis 12
- Puis 450 (ce sera donc l'arrière)
09° Que doit-on inscrire si on veut lire ET supprimer l'avant de la liste précédente ?
10° On veut obtenir une implémentation tableau dynamique à coût constant pour l'insertion de l'arrière et la suppression de l'avant. Donner la seule affirmation correcte parmi
- Un tableau dynamique car
pop(0)permet de supprimer la première case à coût constant. - Une liste doublement chaînée (une Cellule connait son successeur et son prédécesseur) dont on garde les références de la première et de la dernière cellule : on pourra ainsi insérer ou supprimer une cellule à coût constant
- Un tuple (tete, queue), il n'y a que ça de vrai.
- Une liste simplement chaînée (une Cellule connait uniquement son successeur, pas son prédécesseur) dont on garde les références de la première et de la dernière cellule : on pourra ainsi insérer ou supprimer une cellule à coût constant
Activité publiée le 21 10 2020
Dernière modification : 21 10 2020
Auteur : ows. h.