2.3 KiB
2.3 KiB
Évaluation Terminale NSI : Arbres et Arbres Binaires
Exercice 1 : L'arbre généalogique loufoque
Le grand sorcier Archimagicus a perdu son arbre généalogique ! Il ne se souvient que de quelques relations de parenté et a noté les informations suivantes :
- Il a deux enfants : Merlin et Morgane.
- Merlin a lui-même deux enfants : Gandalf et Saroumane.
- Morgane a une fille, Circé.
- Gandalf et Circé ont un fils : Harry.
Représente cet arbre sous forme d'un schéma d'arbre binaire (même si certains n’ont qu'un seul enfant). Puis, détermine :
- Le niveau de chaque personnage.
- La hauteur de l'arbre.
- Si l’arbre est un arbre binaire de recherche.
Exercice 2 : Un arbre de décisions absurde
On considère l’arbre de décision suivant :
Est-ce urgent ?
/ \
Travail ou Loisir ? Ignorer la demande
/ \
Envoyer Form. Reporter
- Implémente cet arbre sous forme de structure en Python.
- Écris une fonction permettant de parcourir cet arbre et d’afficher les décisions possibles.
Exercice 3 : Un arbre de quêtes pour un RPG
Un jeu de rôle utilise un arbre pour gérer ses quêtes :
Trouver l'épée sacrée
/ \
Explorer la grotte Chercher le vieux sage
/ \ / \
Combattre Fuir Récupérer un sort Demander un conseil
un troll
- Représente cet arbre sous forme de structure Python.
- Écris une fonction permettant d’afficher toutes les quêtes accessibles à partir d’un point donné.
Exercice 4 : Un défi algorithmique avancé
Un arbre binaire est complet si tous ses niveaux, sauf éventuellement le dernier, sont complètement remplis, et si tous les nœuds sont alignés le plus à gauche possible.
Question :
- Écris une fonction récursive permettant de vérifier si un arbre est complet.
- Écris une autre fonction qui calcule le nombre minimum d’opérations nécessaires pour transformer un arbre quelconque en arbre binaire complet.
Exercice 5 : Un jeu ancien et les arbres
Quel est le jeu stratégique ancien qui pourrait voir tous ses coups représentés sous forme d'un arbre ? Explique pourquoi et propose une manière de représenter cet arbre en Python.