Exercice 2 - Arbres · Bac Numérique et Sciences Informatiques Nouvelle-Calédonie 2022 (jour 2)
Thème : Arbres : vocabulaire, mesures et algorithmique · Tiré du sujet Jour 2 (2022)
Énoncé
EXERCICE 2
Cet exercice porte sur de l'algorithmique et de la programmation en langage Python utilisant les structures de données du type arbre binaire.
On crée un jeu dans lequel les personnages doivent se déplacer. Le personnage Mélusine se déplace et se retrouve devant différents chemins possibles. Le schéma 1 ci-dessous illustre la situation.
Mélusine part du point A et peut se rendre à n'importe quel autre point repéré par une lettre. Sous chaque lettre, se cache un objet à récupérer. Chaque objet est associé à une valeur.
1)
Indiquer pourquoi il s'agit d'un arbre binaire.
3)
Indiquer, en justifiant la réponse, le rôle de l'algorithme suivant.
CALCUL(T: arbre):
VARIABLE
x: noeud
DEBUT
si T n'est pas un arbre vide:
x ← racine de T
renvoyer 1 + CALCUL(sous arbre gauche de x) + CALCUL(sous arbre droit de x)
sinon:
renvoyer 0
fin si
FIN
4)
On applique l'algorithme ci-dessous à l'arbre du schéma 1.
VISITE(T: arbre):
VARIABLE
x: noeud
DEBUT
si T n'est pas un arbre vide:
x ← racine de T
affiche clé de x
VISITE(sous arbre gauche de x)
VISITE(sous arbre droit de x)
fin si
FIN
a)
b)
Corrigé
Corrigé proposé par AprenAI (non officiel)
1) Indiquer pourquoi il s'agit d'un arbre binaire.
Réponse : Chaque nœud possède au plus deux fils (un sous-arbre gauche et un sous-arbre droit).
3) Rôle de l'algorithme CALCUL
Réponse : Calcul de la taille de l'arbre (le nombre total de nœuds).
3) Justification du rôle de l'algorithme CALCUL
Réponse : Pour un arbre vide, l'algorithme renvoie 0 (cas de base). Pour un arbre non vide, il renvoie 1 (comptabilisant le nœud courant) plus la somme des nœuds du sous-arbre gauche et du sous-arbre droit. Par récurrence, cela donne le nombre total de nœuds de l'arbre (sa taille).
Les réponses des 2 questions restantes et l’explication pas à pas sont réservées aux membres Premium. Premium
Résous-le ici : correction automatique, indices et corrigé détaillé.
‹ Exercice 4 · Nouvelle-Calédonie 2022 (jour 1)