Terminale NSI - Exercices : listes - piles - files

Quelle structure de données choisir pour chacune des tâches suivantes :

  1. Représenter un répertoire téléphonique.
  2. Envoyer des fichiers à un serveur d'impression. (un spooler en anglais).
  3. Gérer dans un logiciel les commandes Undo et Redo (Annuler et refaire).
  1. Un dictionnaire avec comme clés le nom et le numéro de téléphone.
  2. Une file : premier fichier envoyé => premier fichier à imprimer.
  3. Une pile : on empile avec la commande "Redo" et on dépile avec la commande "Undo".

On donne la séquence d'instructions suivante : 


L1 = CREER_LISTE_VIDE()
L2 = CREER_LISTE_VIDE()
INSERER(L1,10,1)
INSERER(L1,20,2)
INSERER(L1,30,3)
INSERER(L1,40,4)
INSERER(L2,LIRE(L1,1),1)
INSERER(L2,LIRE(L1,2),1)
INSERER(L2,LIRE(L1,3),1)
INSERER(L2,LIRE(L1,4),1)
  1. Illustrer le résultat de chaque étape de la séquence.
  2. Quelle est l'opération effectuée ?
  1. 
L1 = CREER_LISTE_VIDE()       L1 = ()
L2 = CREER_LISTE_VIDE()       L2 = ()
INSERER(L1,10,1)              L1 = (10)
INSERER(L1,20,2)              L1 = (10,20)
INSERER(L1,30,3)              L1 = (10,20,30)
INSERER(L1,40,4)              L1 = (10,20,30,40)
INSERER(L2,LIRE(L1,1),1)      L2 = (10)
INSERER(L2,LIRE(L1,2),1)      L2 = (20,10)
INSERER(L2,LIRE(L1,3),1)      L2 = (30,20,10)
INSERER(L2,LIRE(L1,4),1)      L2 = (40,30,20,10)

  2. La liste L2 contient les éléments de la liste L1 dans l'ordre inverse.

On donne la séquence d'instructions suivante : 


F = CREER_FILE_VIDE()
ENFILER(F,5)
ENFILER(F,8)
ENFILER(F,9)
R = DEFILER(F)
ENFILER(F,7)
R = DEFILER(F)

Illustrer le résultat de chaque étape de la séquence. 


F = CREER_LISTE_VIDE()      F = ()
ENFILER(F,5)                F = (5)
ENFILER(F,8)                F = (8,5)
ENFILER(F,9)                F = (9,8,5)
R = DEFILER(F)              R = 5 et F = (9,8)
ENFILER(F,7)                F = (7,9,8)
R = DEFILER(F)              R = 8 et F = (7,9)

On dispose d'une file F1 qui contient les éléments suivants classés par ordre alphabétique :

F1=('A','B','C','D','E')

  1. Quel est l'élément issu du défilage de F1 ?
  2. Proposer un algorithme écrit en pseudo-code qui utilise deux piles P1 et P2 et qui permet la saisie d'affilée des 5 éléments (sans sortie intermédiaire) et la sortie des éléments comme s'ils sortaient d'une file.
  1. Le premier élément issu du défilage de F1 est A.

  2. 
P1 = CREER_PILE_VIDE()
P2 = CREER_PILE_VIDE()
EMPILER(P1,'A')
EMPILER(P1,'B')
EMPILER(P1,'C')
EMPILER(P1,'D')
EMPILER(P1,'E')
Tant que non(EST_VIDE(P1)) Faire
	N = Depiler(P1)
	EMPILER(P2,N)
Fin TanQue