NSI Terminale • Programme français, lycées de Montréal
Les structures de données sont le chapitre où l'on connaît les définitions et où l'on perd pourtant des points sur des questions de déroulé : quel élément sort en premier, quelle hauteur pour cet arbre, dans quel ordre le parcours visite. Rien ne se démontre ici, tout se déroule, et un déroulé faux ne se rattrape jamais.
Cette fiche liste les neuf erreurs qui reviennent dans les copies, avec la phrase exacte à écrire à la place et ce que chacune coûte au barème.
Le fil du chapitre
Une structure de données est un CONTRAT sur l'ordre de sortie : remplacer une pile par une file ne casse aucun programme, cela en change silencieusement le résultat.
Dans une question de déroulé, dessiner l'état de la structure après chaque opération vaut toujours mieux que de suivre de tête : c'est aussi ce que le barème demande.
Écrire la convention retenue en tête de copie, « hauteur comptée en arêtes », évite de perdre un point quand le sujet compte en niveaux.
Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.
Ce qu'il ne faut pas écrire
« Je dépile 3 puis 5, donc j'écris . »
Ce qu'il faut écrire
« Le PREMIER dépilé est le SECOND opérande : je dépile 3 puis 5, et je calcule . »
Pourquoi : Une pile rend les éléments dans l'ordre inverse de leur arrivée, donc le sommet est l'opérande de droite. L'erreur reste invisible sur et , puis fausse tout dès la première soustraction ou division.
Ce qu'il ne faut pas écrire
« Cet arbre a 5 noeuds, donc sa hauteur est 5. »
Ce qu'il faut écrire
« La taille est 5 et la hauteur est le nombre d'ARÊTES du plus long chemin : elle vaut 2 pour cet arbre équilibré, 4 s'il est en peigne. »
Pourquoi : Taille et hauteur ne sont liées que par un ENCADREMENT : entre et . Deux arbres de même taille peuvent avoir des hauteurs très différentes, et c'est justement ce que mesure l'équilibre.
Ce qu'il ne faut pas écrire
« Un arbre vide a une hauteur de 0, comme un arbre réduit à sa racine. »
Ce qu'il faut écrire
« L'arbre vide a une hauteur de et une taille de ; l'arbre réduit à sa racine a une hauteur de et une taille de . »
Pourquoi : C'est la convention qui rend juste la formule : sans le , une feuille se verrait attribuer une hauteur de 1.
Ce qu'il ne faut pas écrire
« Une recherche dans un arbre binaire de recherche coûte . »
Ce qu'il faut écrire
« Elle coûte la HAUTEUR, qui vaut seulement si l'arbre est équilibré. Insérées dans l'ordre croissant, valeurs donnent un peigne de hauteur . »
Pourquoi : La structure ne s'équilibre pas toute seule : l'ordre d'insertion décide de la forme. C'est pour cela qu'existent les arbres équilibrés, hors programme mais souvent évoqués en fin de sujet.
Ce qu'il ne faut pas écrire
« Le parcours infixe donne toujours les valeurs dans l'ordre croissant. »
Ce qu'il faut écrire
« Seulement dans un arbre binaire de RECHERCHE, où tout le sous-arbre gauche est inférieur à la racine. Sur un arbre quelconque, l'infixe ne trie rien. »
Pourquoi : C'est la propriété de l'arbre qui fait le tri, pas le parcours. L'infixe se contente de visiter gauche, racine, droite : c'est l'invariant de l'arbre de recherche qui rend cette suite croissante.
Ce qu'il ne faut pas écrire
« Je mets les voisins dans une pile et je les traite un par un : c'est le parcours en largeur. »
Ce qu'il faut écrire
« Le parcours en largeur exige une FILE. Avec une pile, on obtient un parcours en profondeur, et le chemin trouvé n'est plus le plus court. »
Pourquoi : La file garantit qu'on traite tous les sommets à distance avant ceux à distance : c'est exactement ce qui rend le premier chemin trouvé minimal. Une pile détruit cette garantie.
Ce qu'il ne faut pas écrire
« Je défile un sommet, je le marque, puis j'ajoute ses voisins non marqués. »
Ce qu'il faut écrire
« Je marque un sommet au moment où je l'AJOUTE : sinon un même sommet est ajouté plusieurs fois avant d'être traité, et le parcours enfle. »
Pourquoi : Entre l'ajout et le traitement, un sommet reste non marqué et peut être atteint par un autre voisin. Marquer à l'ajout est ce qui borne le nombre d'entrées dans la file par le nombre de sommets.
Ce qu'il ne faut pas écrire
« Une liste chaînée est plus efficace qu'un tableau, donc lire le millième élément y est rapide. »
Ce qu'il faut écrire
« Il faut suivre mille maillons : l'accès au -ième coûte . La liste chaînée est plus efficace pour INSÉRER en tête, pas pour accéder. »
Pourquoi : Aucune structure n'est meilleure en tout : chaque choix échange un coût contre un autre. Le tableau paie l'insertion, la liste chaînée paie l'accès.
Ce qu'il ne faut pas écrire
« La matrice est plus simple, et de toute façon un graphe de mille sommets tient en mémoire. »
Ce qu'il faut écrire
« Avec et , la matrice occupe de cases contre entrées pour les listes, et le parcours passe de à . »
Pourquoi : La matrice ne dépend que du nombre de sommets : elle réserve la place de toutes les arêtes possibles. Sur un graphe creux, la quasi-totalité de cette place est occupée par des zéros.
Ce qu'il ne faut pas écrire
« Défiler oblige parfois à transvaser toute la pile, donc cette file coûte par opération. »
Ce qu'il faut écrire
« Chaque élément est empilé et dépilé au plus deux fois dans sa vie, soit quatre opérations : le coût AMORTI par opération est constant. »
Pourquoi : Le coût amorti se raisonne sur la vie d'un élément, pas sur le pire cas d'une opération. Un transvasement coûteux ne se produit qu'après autant d'opérations bon marché.
Si « le dernier arrivé doit repartir en premier » → pile
Exemple : vérifier un parenthésage, annuler une action
Si « dans l'ordre d'arrivée », « le plus court chemin » → file
Exemple : parcours en largeur, file d'attente
Si « insérer souvent en tête », « la taille varie beaucoup » → liste chaînée
Exemple : un journal d'événements
Si « accéder au -ième », « parcourir par indice » → tableau
Exemple : un relevé indexé par le numéro de capteur
Si « retrouver vite par une clé » → dictionnaire, ou arbre binaire de recherche si l'ordre compte
Exemple : l'annuaire d'un réseau
l'arbre garde l'ordre, le dictionnaire est plus rapide
Si l'énoncé impose le plus court chemin, la réponse est la file, sans discussion : c'est la seule structure qui donne cette garantie.
Si « les valeurs dans l'ordre croissant » → parcours infixe, et seulement dans un arbre de recherche
Exemple : lister un annuaire trié
Si « recopier ou sérialiser l'arbre » → parcours préfixe
Exemple : écrire l'arbre dans un fichier
la racine d'abord permet de reconstruire en lisant
Si « évaluer une expression », « libérer la mémoire » → parcours suffixe
Exemple : calculer la valeur d'un arbre d'expression
Si « le plus court chemin », « le nombre minimal d'étapes » → parcours en largeur, avec une FILE
Exemple : sortir d'un labyrinthe
Si « existe-t-il un chemin », « toutes les configurations » → parcours en profondeur, avec une pile ou par récursivité
Exemple : tester la connexité
Si aucune branche ne s'applique, dérouler le parcours en largeur : c'est celui qui répond au plus grand nombre de questions de sujet.
Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.
Quand l'utiliser : L'énoncé demande l'ordre de visite, ou le plus court chemin dans un graphe donné.
Phrase de conclusion
« Le parcours en largeur depuis A visite A, B, C, D, E, F. Le sommet F est atteint à la distance 3, et ce chemin est minimal car le parcours en largeur traite tous les sommets à distance avant ceux à distance . »
Le piège : Ne pas préciser l'ordre dans lequel les voisins sont pris : le déroulé devient alors indéfendable dès qu'il diffère du corrigé.
Barème : 1 point pour la structure annoncée, 2 points pour le tableau, 1 point pour la justification de minimalité.
Quand l'utiliser : L'énoncé demande le coût d'une suite d'opérations, ou parle explicitement de coût amorti.
Phrase de conclusion
« Chaque élément est empilé puis dépilé au plus deux fois, soit quatre opérations élémentaires. Une suite de ajouts et retraits coûte donc au plus opérations, soit un coût amorti constant par opération, bien qu'un retrait isolé puisse en coûter . »
Le piège : Raisonner sur le pire cas d'une opération isolée : c'est vrai et hors sujet, la question porte sur la suite.
Barème : 2 points pour le suivi d'un élément, 1 point pour le total, 1 point pour la conclusion.
Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.
Compter les entrées dans la structure
Dans un parcours correct, chaque sommet entre au plus une fois dans la file ou la pile. Compter les entrées et les comparer au nombre de sommets.
Sept entrées pour six sommets signalent un marquage fait au traitement au lieu de l'ajout.
Vérifier la hauteur par l'encadrement
Une hauteur annoncée doit tenir entre et . Hors de cet intervalle, elle est fausse sans qu'il faille redessiner l'arbre.
Une hauteur de 6 pour un arbre de 5 noeuds est impossible, puisque le maximum est 4.
Relire l'infixe d'un arbre de recherche
Sur un arbre binaire de recherche, le parcours infixe doit donner une suite strictement croissante : le premier couple qui décroît localise l'insertion fautive.
Une suite signale que le 5 a été placé dans le mauvais sous-arbre.
Tester la structure sur trois éléments
Ajouter 1, 2, 3 puis tout retirer : une pile rend 3, 2, 1 et une file rend 1, 2, 3. Deux lignes suffisent à savoir laquelle on a écrite.
Un code censé faire un parcours en largeur qui rend 3, 2, 1 utilise en réalité une pile.
Contrôler l'ordre de grandeur d'une représentation
Comparer et avant de choisir : si le second est cent fois plus petit, la matrice ne se justifie pas.
et donnent contre .
Un labyrinthe est donné par un graphe de 12 cases et 16 passages. On cherche le nombre minimal de déplacements pour aller de la case de départ à la sortie.
Écrire l'algorithme, justifier qu'il donne bien le minimum, et donner son coût.
Étape 1
Structure : une FILE, initialisée avec la case de départ, qui est marquée immédiatement.
Pourquoi
Le choix de la file est la réponse à la question de minimalité : c'est lui qu'il faut annoncer en premier, avant même d'écrire une ligne d'algorithme.
Étape 2
Un dictionnaire distance associe 0 à la case de départ, et rien aux autres.
Pourquoi
Le dictionnaire sert à la fois de marquage et de résultat : un sommet marqué est un sommet dont la distance est déjà connue, ce qui évite d'entretenir deux structures.
Étape 3
Tant que la file n'est pas vide : défiler une case, puis pour chaque voisin NON marqué, lui donner la distance de la case plus un, le marquer, et l'enfiler.
Pourquoi
Marquer AVANT d'enfiler est ce qui garantit qu'aucune case n'entre deux fois. C'est la ligne que les copies inversent le plus souvent.
Étape 4
Arrêt dès que la sortie est défilée, ou à file vide si elle est inatteignable.
Pourquoi
Le cas inatteignable est une demi-question à lui seul : une réponse qui ne le traite pas perd le point de complétude.
Étape 5
Justification : le parcours traite tous les sommets à distance avant tout sommet à distance , donc la première atteinte d'une case est la plus courte.
Pourquoi
C'est la phrase qui vaut les points de raisonnement. Sans elle, l'algorithme peut être juste et la question reste sans réponse.
Étape 6
Coût : chaque case entre au plus une fois dans la file et chaque passage est examiné deux fois, soit , ici opérations.
Pourquoi
Le chiffrage sur les données de l'énoncé transforme une formule apprise en réponse défendable, et se compare aux cases d'une matrice d'adjacence.
Conclusion rédigée
« Le parcours en largeur depuis la case de départ donne la distance minimale à la sortie, car il traite les cases par distance croissante. Son coût est , soit de l'ordre de 44 opérations pour 12 cases et 16 passages, contre 144 avec une matrice d'adjacence. »
L'erreur classique sur cet exercice : Écrire le même algorithme avec une pile : il trouve un chemin, mais rien ne garantit qu'il soit le plus court, et la question de minimalité devient sans réponse.
Seul l'ordre de sortie change. Une pile rend d'abord le dernier élément entré, une file rend d'abord le premier. Les deux offrent les mêmes opérations, ajouter, retirer et tester si c'est vide, si bien qu'un algorithme reste syntaxiquement correct quand on remplace l'une par l'autre : c'est son résultat qui change, sans aucun message d'erreur.
On compte les arêtes du plus long chemin partant de la racine, pas les noeuds. L'arbre vide a pour hauteur moins un, un arbre réduit à sa racine a pour hauteur zéro, et la formule récursive est un plus le maximum des hauteurs des deux sous-arbres. Cette convention est celle qui rend la formule juste pour une feuille.
Parce que la file impose de traiter tous les sommets situés à distance d avant le moindre sommet à distance d plus un. La première fois qu'un sommet est atteint, c'est donc par un chemin de longueur minimale. Avec une pile, cette garantie disparaît : on trouve un chemin, mais rien ne dit qu'il soit le plus court.
Non. La recherche coûte la hauteur de l'arbre, et cette hauteur dépend de l'ordre d'insertion. Des valeurs insérées dans l'ordre croissant produisent un peigne de hauteur n moins un, où la recherche est aussi lente que dans une liste. Le coût logarithmique n'est atteint que si l'arbre reste équilibré.
On compare le nombre de sommets au nombre d'arêtes. La matrice occupe le carré du nombre de sommets, quelle que soit la densité, et permet un test d'arête immédiat. Les listes occupent le nombre de sommets plus deux fois le nombre d'arêtes, et rendent le parcours proportionnel à cette somme. Sur un graphe creux, les listes l'emportent largement.
