Sujet NSI — Terminale — Liban — Bac 2022

EXERCICE 1 (4 points) Cet exercice porte sur les structures de données (listes, piles et files). On cherche ici à mettre en place des algorithmes qui permettent de modifier l’ordre des informations contenues dans une file. On considère pour cela les structures de données abstraites de Pile et File définies par leurs fonctions primitives suivantes : Pile :  creer_pile_vide() renvoie une pile vide ;  est_pile_vide(p) renvoie True si la pile p est vide, False sinon ;  empiler(p, element) ajoute element au sommet de la pile p ;  depiler(p) renvoie l’élément se situant au sommet de la pile p en le retirant de la pile p ;  sommet(p) renvoie l’élément se situant au sommet de la pile p sans le retirer de la pile p. File :  creer_file_vide() renvoie une file vide ;  est_file_vide(f) renvoie True si la file f est vide, False sinon ;  enfiler(f, element) ajoute element dans la file f ;  defiler(f) renvoie l’élément à la tête de la file f en le retirant de la file f. On considère de plus que l'on dispose d'une fonction permettant de connaître le nombre d'éléments d'une file :  taille_file(f) renvoie le nombre d'éléments de la file f. On représentera les files par des éléments en ligne, l'élément de droite étant la tête de la file et l'élément de gauche étant la queue de la file. On représentera les piles en colonnes, le sommet de la pile étant le haut de la colonne. La file suivante est appelée f : 4 3 8 2 1 5 8 La pile suivante est appelée p : 6 2 1. Les quatre questions suivantes sont indépendantes. Pour chaque question, on repartira de la pile p et de la file f initiales (présentées ci-dessus) a. Représenter la file f après l’exécution du code suivant. enfiler(f, defiler(f)) b. Représenter la pile p après l’exécution du code suivant. empiler(p, depiler(p)) c. Représenter la pile p et la file f après l’exécution du code suivant. for i in range(2): enfiler(f, depiler(p)) 22-NSIJ1LR1 Page 2 sur 16 d. Représenter la pile p et la file f après l’exécution du code suivant. for i in range(2): empiler(p, defiler(f)) 2. On donne ici une fonction mystere qui prend une file en argument, qui modifie cette file, mais qui ne renvoie rien. def mystere(f): p = creer_pile_vide() while not est_file_vide(f): empiler(p, defiler(f))