Exercices - Structures de données¶
Exercice 1 - Pile : vérification de parenthèses¶
Écrire une fonction parentheses_valides(expression) qui vérifie si les parenthèses d'une expression mathématique sont correctement équilibrées, en utilisant une pile.
Exemples :
"(3 + 5) * (2 - 1)"→True"((3 + 5) * 2"→False(parenthèse ouvrante non fermée)"3 + 5) * 2"→False(parenthèse fermante sans ouvrante)
Solution
def parentheses_valides(expression):
pile = []
for c in expression:
if c == '(':
pile.append(c)
elif c == ')':
if len(pile) == 0:
return False
pile.pop()
return len(pile) == 0
# Tests
print(parentheses_valides("(3 + 5) * (2 - 1)")) # True
print(parentheses_valides("((3 + 5) * 2")) # False
print(parentheses_valides("3 + 5) * 2")) # False
print(parentheses_valides("()()()")) # True
print(parentheses_valides("((()))")) # True
Exercice 2 - Pile : notation polonaise inversée¶
En notation polonaise inversée (NPI), les opérateurs sont placés après leurs opérandes. Par exemple :
3 4 +signifie3 + 4 = 73 4 + 2 *signifie(3 + 4) * 2 = 14
Écrire une fonction evaluer_npi(expression) qui prend une chaîne en NPI (éléments séparés par des espaces) et renvoie le résultat, en utilisant une pile.
Solution
def evaluer_npi(expression):
pile = []
for token in expression.split():
if token in "+-*/":
b = pile.pop()
a = pile.pop()
if token == '+':
pile.append(a + b)
elif token == '-':
pile.append(a - b)
elif token == '*':
pile.append(a * b)
elif token == '/':
pile.append(a / b)
else:
pile.append(float(token))
return pile[0]
# Tests
print(evaluer_npi("3 4 +")) # 7.0
print(evaluer_npi("3 4 + 2 *")) # 14.0
print(evaluer_npi("5 1 2 + 4 * + 3 -")) # 14.0
Exercice 3 - File : simulation d'une file d'attente¶
On simule une file d'attente à un guichet. Écrire une classe FileAttente qui propose :
arrivee(nom): une personne arrive et se place en fin de file ;service(): la première personne de la file est servie (retirée) et son nom est renvoyé ;attente(): renvoie le nombre de personnes en attente ;afficher(): affiche l'état de la file.
Simuler le scénario suivant : Alice arrive, Bob arrive, Alice est servie, Clara arrive, Bob est servi.
Solution
class FileAttente:
def __init__(self):
self.personnes = []
def arrivee(self, nom):
self.personnes.append(nom)
def service(self):
if len(self.personnes) == 0:
return None
return self.personnes.pop(0)
def attente(self):
return len(self.personnes)
def afficher(self):
if len(self.personnes) == 0:
print("File vide")
else:
print(" <- ".join(self.personnes))
# Simulation
f = FileAttente()
f.arrivee("Alice")
f.arrivee("Bob")
f.afficher() # Alice <- Bob
print(f.service()) # Alice
f.arrivee("Clara")
f.afficher() # Bob <- Clara
print(f.service()) # Bob
f.afficher() # Clara
print(f.attente()) # 1
Exercice 4 - Liste chaînée : opérations¶
Compléter la classe ListeChainee vue en cours avec les méthodes suivantes :
a. longueur() : renvoie le nombre d'éléments.
b. contient(valeur) : renvoie True si la valeur est dans la liste.
c. élément(i) : renvoie la valeur à l'indice i (en partant de 0).
Solution
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.tete = None
def est_vide(self):
return self.tete is None
def ajouter_en_tete(self, valeur):
self.tete = Maillon(valeur, self.tete)
def longueur(self):
compteur = 0
courant = self.tete
while courant is not None:
compteur += 1
courant = courant.suivant
return compteur
def contient(self, valeur):
courant = self.tete
while courant is not None:
if courant.valeur == valeur:
return True
courant = courant.suivant
return False
def élément(self, i):
courant = self.tete
for _ in range(i):
courant = courant.suivant
return courant.valeur
# Tests
lst = ListeChainee()
lst.ajouter_en_tete(30)
lst.ajouter_en_tete(20)
lst.ajouter_en_tete(10)
print(lst.longueur()) # 3
print(lst.contient(20)) # True
print(lst.contient(50)) # False
print(lst.élément(0)) # 10
print(lst.élément(2)) # 30
Exercice 5 - Arbres binaires¶
On considère l'arbre binaire suivant :
a. Donner la racine, les feuilles et les nœuds internes de cet arbre.
b. Quelle est la taille de cet arbre ? Sa hauteur ?
c. Quelle est la profondeur du nœud 7 ? Du nœud 18 ?
d. Construire cet arbre en Python avec la classe Nœud vue en cours, puis vérifier vos réponses avec les fonctions taille() et hauteur().
Solution
a.
- Racine : 12
- Feuilles : 3, 7, 25 (pas d'enfant)
- Nœuds internes : 12, 6, 18, 8 (au moins un enfant)
b. Taille = 7 nœuds. Hauteur = 3 (chemin le plus long : 12 → 6 → 8 → 7).
c. Profondeur de 7 : 3 (12 → 6 → 8 → 7, soit 3 arêtes). Profondeur de 18 : 1.
d.
class Nœud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def taille(arbre):
if arbre is None:
return 0
return 1 + taille(arbre.gauche) + taille(arbre.droit)
def hauteur(arbre):
if arbre is None:
return -1
return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))
arbre = Nœud(12,
Nœud(6, Nœud(3), Nœud(8, Nœud(7), None)),
Nœud(18, None, Nœud(25))
)
print(taille(arbre)) # 7
print(hauteur(arbre)) # 3
Exercice 6 - Graphes : modélisation¶
Modéliser les situations suivantes sous forme de graphes (préciser si orienté ou non, donner les sommets et arêtes/arcs, puis écrire la liste d'adjacence en Python).
a. Un groupe de 5 amis : Alice, Bob, Clara, David, Emma. Alice est amie avec Bob et Clara. Bob est ami avec David. Clara est amie avec Emma et David.
b. Un réseau de pages web : la page A contient un lien vers B et C. La page B contient un lien vers A. La page C contient un lien vers B.
Solution
a. Graphe non orienté (l'amitié est réciproque) :
amis = {
"Alice": ["Bob", "Clara"],
"Bob": ["Alice", "David"],
"Clara": ["Alice", "Emma", "David"],
"David": ["Bob", "Clara"],
"Emma": ["Clara"]
}
b. Graphe orienté (un lien va d'une page vers une autre, pas forcément l'inverse) :
Exercice 7 - Graphes : matrice d'adjacence¶
On considère le graphe non orienté suivant :
a. Écrire la matrice d'adjacence de ce graphe.
b. Écrire une fonction Python nb_aretes(matrice) qui calcule le nombre d'arêtes d'un graphe non orienté à partir de sa matrice d'adjacence.
c. Écrire une fonction degré(matrice, sommet) qui renvoie le degré d'un sommet (nombre de voisins).
Solution
a. Matrice d'adjacence (sommets dans l'ordre A, B, C, D) :
b. et c.
matrice = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]
]
def nb_aretes(matrice):
total = 0
for i in range(len(matrice)):
for j in range(len(matrice)):
total += matrice[i][j]
return total // 2 # chaque arête est comptée 2 fois
def degré(matrice, sommet):
return sum(matrice[sommet])
print(nb_aretes(matrice)) # 5
print(degré(matrice, 0)) # 2 (A est relié à B et C)
print(degré(matrice, 1)) # 3 (B est relié à A, C et D)
Exercice 8 - Choix de structure¶
Pour chaque situation, indiquer quelle structure de données est la plus adaptée et justifier.
a. Gérer l'historique des pages visitées dans un navigateur (bouton « retour »).
b. Gérer une file d'impression (les documents s'impriment dans l'ordre d'envoi).
c. Stocker un arbre généalogique.
d. Représenter un plan de métro (stations et correspondances).
e. Associer un numéro de téléphone à chaque contact.
Solution
a. Une pile (LIFO) : le bouton « retour » revient à la dernière page visitée, qui est celle au sommet de la pile.
b. Une file (FIFO) : les documents doivent être traités dans l'ordre d'arrivée.
c. Un arbre : la structure est hiérarchique (parents → enfants). Pas forcément binaire (une personne peut avoir plus de 2 enfants).
d. Un graphe non orienté : les stations sont les sommets, les liaisons entre stations sont les arêtes. Ce n'est pas un arbre car il peut y avoir des cycles (boucles de métro).
e. Un dictionnaire : on associe la clé (nom du contact) à la valeur (numéro de téléphone), avec un accès rapide.
Exercice 9 - Implémentation d'une file avec deux piles¶
a. Implémenter une file en utilisant deux piles (comme vu en cours). Tester avec le scénario : enfiler 1, 2, 3 ; défiler ; enfiler 4 ; défiler deux fois.
b. Expliquer pourquoi cette implémentation fonctionne correctement (ordre FIFO respecté).
Solution
a.
class Pile:
def __init__(self):
self.éléments = []
def empiler(self, x):
self.éléments.append(x)
def depiler(self):
return self.éléments.pop()
def est_vide(self):
return len(self.éléments) == 0
class File:
def __init__(self):
self.entree = Pile()
self.sortie = Pile()
def enfiler(self, x):
self.entree.empiler(x)
def defiler(self):
if self.sortie.est_vide():
while not self.entree.est_vide():
self.sortie.empiler(self.entree.depiler())
return self.sortie.depiler()
def est_vide(self):
return self.entree.est_vide() and self.sortie.est_vide()
# Test
f = File()
f.enfiler(1)
f.enfiler(2)
f.enfiler(3)
print(f.defiler()) # 1
f.enfiler(4)
print(f.defiler()) # 2
print(f.defiler()) # 3
print(f.defiler()) # 4
b. Quand on défile, si la pile de sortie est vide, on transfère tous les éléments de la pile d'entrée vers la pile de sortie. Ce transfert inverse l'ordre : le premier élément entré (au fond de la pile d'entrée) se retrouve au sommet de la pile de sortie, et sera donc le premier à sortir. L'ordre FIFO est ainsi respecté.