Listes, Piles et Files (Exercices)

Les exercices précédés du symbole sont à faire sur machine, en sauvegardant le fichier si nécessaire.

Les exercices précédés du symbole doivent être résolus par écrit.

Exercice 1 (listes)

On reprend l’implémentation des listes avec des tuples présentée dans le cours.

  1. Prévoir l’effet et l’affichage en console des instructions suivantes, puis vérifier en exécutant ces instructions dans la console interactive après avoir créé et importé un fichier contenant le code du cours :
>>> L = creer()
>>> est_vide(L)
>>> L = ajouter(5, ajouter(4, ajouter(3, ajouter(2, ajouter(1, ajouter(0,()))))))
>>> est_vide(L)
>>> longueur(L)
>>> L = ajouter(6,L)
>>> longueur(L)
>>> tete(L)
>>> queue(L)
>>> longueur(queue(L))
  1. Créer un fichier nommé listes_tuples.py contenant le code du cours implémentant les listes avec des tuples. Dans un autre fichier, situé dans le même dossier, importer le module listes_tuples et tester les instructions de la question précédente.
  2. Ajouter dans le module listes_tuples une fonction afficher(L) qui affiche le contenu de la liste L sous la forme d’une chaîne de caractères. Par exemple, l’instruction afficher(L) doit afficher 5 -> 4 -> 3 -> 2 -> 1 -> 0.

Exercice 2 (listes)

Soit la suite d’instructions suivantes utilisant l’implémentation des listes avec des tuples:

from listes_tuples import *

L = creer()
L = ajouter(2, ajouter(15, ajouter (23, L)))
L1 = queue(L)
a = tete(L1)
L1 = ajouter(4, ajouter(3, L1))

Donnez le contenu des listes L et L1 et la valeur de a.

Exercice 3 (piles)

On suppose que l’on dispose d’un module piles_listes.py contenant l’implémentation des piles avec des listes Python vue dans le cours. On suppose également que l’on a importé ce module dans la console interactive.

Soit une pile P initialement vide. Soit les instructions suivantes :

>>> empiler(P,4)
>>> empiler(P,7)
>>> a = depiler(P)
>>> b = taille(P)
>>> c = depiler(P)
>>> empiler(P,3)
>>> empiler(P,2)
>>> d = taille(P)

Donnez le contenu de la pile P, la valeur de a, la valeur de b, la valeur de c et la valeur de d.

Expérimenter ensuite ces commandes dans la console Python.

Exercice 4 (piles)

On suppose que l’on dispose d’un module piles_POO.py contenant l’implémentation des piles en POO vue dans le cours (classe Pile). On suppose également que l’on a importé ce module dans la console interactive.

Soit le programme Python suivant :

pile = Pile()
tab = [5,8,6,1,3,7]
for k in tab:
    pile.empiler(k)
pile.empiler(5)
pile.empiler(10)
pile.empiler(8)
pile.empiler(15)
for k in tab:
    if k > 5:
        pile.depiler()

Donnez l’état de la pile pile après l’exécution de ce programme.

Expérimenter ensuite ces commandes dans la console Python.

Exercice 5 (piles)

Ce problème propose une application concrète des piles. Il s’agit d’écrire une fonction qui contrôle si une expression mathématique, donnée sous forme d’une chaîne de caractères, est bien parenthésée, c’est- à-dire s’il y a autant de parenthèses ouvrantes que de fermantes, et qu’elles sont bien placées

Par exemple :

  • (..(..)..) est bien parenthésée
  • (…(..(..)…) ne l’est pas

L’algorithme :

  • On crée une pile
  • On parcourt l’expression de gauche à droite.
  • À chaque fois que l’on rencontre une parenthèse ouvrante “(” on l’empile
  • Si on rencontre une parenthèse fermante ” ) ” et que la pile n’est pas vide on dépile ( sinon on retourne faux )
  • À la fin la pile doit être vide…
  1. En utilisant l’une des structures pile du cours, écrire une fonction verification(expr) qui vérifie si une expression mathématique passée en paramètre est correctement parenthésée.
  2. Proposer un jeu de tests unitaires vérifiant le bon fonctionnement de la fonction.
  3. Faire en sorte que le programme tienne compte également des [.

Exercice 6 (files)

On suppose que l’on dispose d’un module files_deux_piles.py contenant l’implémentation des files avec deux piles vue dans le cours. On suppose également que l’on a importé ce module dans la console interactive.

Soit une file F initialement vide. Soit les instructions suivantes :

enfiler(F,6)
enfiler(F,3)
a = defiler(F)
enfiler(F,9)
b = taille_file(F)
enfiler(F,17)
c = defiler(F)
enfiler(F,2)
d = taille_file(F)

Donnez le contenu de la file F, la valeur de a, la valeur de b, la valeur de c et la valeur de d.

Expérimenter ensuite ces commandes dans la console Python.

Exercice 7 (files)

On suppose que l’on dispose d’un module files_POO.py contenant l’implémentation des files en POO vue dans le cours (classe File). On suppose également que l’on a importé ce module dans la console interactive.

Soit le programme Python suivant :

file = File()
tab = [2,78,6,89,3,17]
file.enfiler(5)
file.enfiler(10)
file.enfiler(8)
file.enfiler(15)
for i in tab:
    if i > 50:
        file.defiler()

Donnez l’état de la file file après l’exécution de ce programme

Expérimenter ensuite ces commandes dans la console Python.

Exercices tombés au bac