Exo File

Identification

Infoforall

6 - 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 :

  1. nouvelleFile() -> File : on crée une nouvelle file vide.
  2. estVide(f:File) -> bool : renvoie un booléen qui vaut True si la file f transmise est une file vide.
  3. enfiler(elt:Elt, f:File) -> File : on renvoie une file en rajoutant l'élément elt en entrée dans f..
  4. defiler(f:File) -> File  : on supprime l'élément en position de sortir et renvoie la nouvelle file f.
  5. 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
a = nouvelleFile() a = enfiler("Bonjour", a) a = enfiler("à", a) a = enfiler("tous", a) avant = lireAvant(a)

05° Même question : que contiennent Avant et Arrière à la fin de cette séquence d'instruction ?

1 2 3 4 5
a = nouvelleFile() a = enfiler(12, a) a = enfiler(27, a) a = defiler(a) a = enfiler(42, a)

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 :

  1. nouvelleFile() -> File : on crée une nouvelle file vide.
  2. estVide(f:File) -> bool : renvoie un booléen qui vaut True si la file p transmise est une file vide.
  3. 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.
  4. 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.
  5. 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
a = nouvelleFile() enfiler(12, a)

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

  1. Un tableau dynamique car pop(0) permet de supprimer la première case à coût constant.
  2. 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
  3. Un tuple (tete, queue), il n'y a que ça de vrai.
  4. 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.