Sujet NSI — Terminale — Métropole — Bac 2021

Exercice 1 Cet exercice porte sur la notion de pile et sur la programmation de base en Python. sorti » : On empile On dépile Sommet de la pile Une pile On munit la structure de données Pile de quatre fonctions primitives définies dans le tableau ci-dessous. : Structure de données abstraite : Pile Utilise : Éléments, Booléen Opérations : — creer_pile_vide : ∅ −→ Pile creer_pile_vide() renvoie une pile vide — est_vide : Pile −→ Booléen est_vide(pile) renvoie True si pile est vide, False sinon — empiler : Pile, Élément −→ Rien empiler(pile, element) ajoute element au sommet de la pile — depiler : Pile −→ Élément depiler(pile) renvoie l’élément au sommet de la pile en le retirant de la pile Question 1 On suppose dans cette question que le contenu de la pile P est le suivant (les éléments étant empilés par le haut) : 4 2 5 8 Quel sera le contenu de la pile Q après exécution de la suite d’instructions suivante? Q = creer_pile_vide() 1 while not est_vide(P): 2 empiler(Q, depiler(P)) 3 page 2 de 12 Question 2 1. On appelle hauteur d’une pile le nombre d’éléments qu’elle contient. La fonction hauteur_pile prend en paramètre une pile P et renvoie sa hauteur. Après appel de cette fonction, la pile P doit avoir retrouvé son état d’origine. Exemple : si P est la pile de la question 1 : hauteur_pile(P) = 4. Recopier et compléter sur votre copie le programme Python suivant implémentant la fonction hauteur_pile en remplaçant les ??? par les bonnes instructions. def hauteur_pile(P): 1 Q = creer_pile_vide() 2 n = 0 3 while not(est_vide(P)): 4 ??? 5 x = depiler(P) 6 empiler(Q,x) 7 while not(est_vide(Q)): 8 ??? 9 empiler(P, x) 10 return ??? 11 2. Créer une fonction max_pile ayant pour paramètres une pile P et un entier i. Cette fonction renvoie la position j de l’élément maximum parmi les i derniers éléments empilés de la pile P. Après appel de cette fonction, la pile P devra avoir retrouvé son état d’origine. La position du sommet de la pile est 1. Exemple : si P est la pile de la question 1 : max_pile(P, 2) = 1 Question 3 Créer une fonction retourner ayant pour paramètres une pile P et un entier j. Cette fonc- tion inverse l’ordre des j derniers éléments empilés et ne renvoie rien. On pourra utiliser deux piles auxiliaires.