Terminale · NSI

Contrôle n°1 — Structures de données : Piles et Files

Ce contrôle évalue votre compréhension des structures de données linéaires, leur implémentation en Python et leurs propriétés algorithmiques.

1h · Moyen · 3 exercices · Barème sur 20 points

Entraînement généré par IA — vérification pédagogique complète non acquise.

Ce sujet n’est pas une annale officielle. La présence d’un corrigé ne garantit pas son exactitude. Vérifie les méthodes avec ton cours ; une note d’entraînement n’est pas une note officielle. Signaler une erreur.

La fenêtre d’impression de ton navigateur permet aussi d’enregistrer en PDF. Aucun téléchargement de PDF officiel n’est annoncé ici.

Sujet

Travaille d’abord sans consulter le corrigé. Note tes réponses et les étapes de ton raisonnement.

Exercice 1 — Questions de cours (6 points)

1. Définissez précisément les propriétés LIFO et FIFO. À quelle structure de données chacune est-elle associée ? 2. Donnez la séquence des éléments retirés si on empile, dans l'ordre, les nombres 5, 12, 8, puis 3, avant de les dépiler tous. 3. Citez deux avantages de l'utilisation d'une liste Python pour implémenter une pile par rapport à l'implémentation d'une file.

Exercice 2 — Implémentation d'une file (8 points)

On considère l'implémentation d'une file à l'aide d'une liste Python nommée `contenu` et de deux indices, `tete` et `queue`. L'indice `tete` pointe sur le prochain élément à défiler, l'indice `queue` pointe sur la première case libre pour un nouvel enfilage. La file est circulaire : lorsqu'un indice dépasse la fin de la liste, il revient au début. 1. Écrivez la fonction `est_vide(self)` qui renvoie `True` si la file ne contient aucun élément. 2. Écrivez la fonction `enfiler(self, element)` qui ajoute un élément à la file. Vous supposerez que la file n'est jamais pleine. 3. Quelle est la complexité en temps de ces deux opérations ? Justifiez.

Exercice 3 — Analyse d'algorithme (6 points)

On utilise une pile pour vérifier la bonne parenthésage d'une chaîne de caractères contenant '(', ')', '[', ']'. L'algorithme parcourt la chaîne. S'il rencontre une parenthèse ouvrante, il l'empile. S'il rencontre une fermante, il dépile et vérifie la correspondance ( '(' avec ')' , '[' avec ']' ). La chaîne '([)]' est-elle considérée comme correctement parenthésée par cet algorithme ? Pourquoi ? Que cela révèle-t-il sur la propriété vérifiée ?

Corrigé et barème

Le total du barème est de 20 points. Les réponses rédigées admettent plusieurs formulations pertinentes ; compare le raisonnement, pas seulement les mots.

Exercice 1 — Questions de cours : 6 points

1. LIFO (Last In, First Out) : le dernier élément ajouté est le premier retiré. Propriété de la pile. FIFO (First In, First Out) : le premier élément ajouté est le premier retiré. Propriété de la file. 2. Séquence de dépilement : 3, 8, 12, 5. 3. Avantages : facilité d'ajout/suppression en fin de liste avec append()/pop() (coût constant amorti), pas besoin de gérer un indice de tête ou de fin séparé pour une pile simple.

Exercice 2 — Implémentation d'une file : 8 points

1. `def est_vide(self): return self.tete == self.queue` 2. `def enfiler(self, element): self.contenu[self.queue] = element; self.queue = (self.queue + 1) % len(self.contenu)` 3. Complexité en O(1) (temps constant). Les opérations sont des affectations, des comparaisons ou des calculs modulo, indépendants du nombre d'éléments dans la file.

Exercice 3 — Analyse d'algorithme : 6 points

Non, la chaîne '([)]' est rejetée. L'algorithme dépile '[' lorsqu'il rencontre ')', ce qui n'est pas une correspondance valide. L'algorithme vérifie que les parenthèses sont correctement *imbriquées* (la dernière ouvrante doit correspondre à la première fermante), et non simplement qu'il y a le même nombre d'ouvrantes et de fermantes de chaque type. Il vérifie l'ordre d'ouverture/fermeture.

Comprendre, puis réessayer

Repère une erreur précise, explique ce qui t’a manqué et refais l’exercice sans le corrigé. Reprends la notion dans ton cours avant de passer à un autre sujet.

Planifier une révision · Chercher un autre entraînement

Contrôle n°2 — Récursivité et Diviser pour régner

Contrôle n°3 — Bases de données et Langage SQL

Contrôle n°4 — Architectures matérielles, Réseaux et Routage