Exercice 1 · Bac Numérique et Sciences Informatiques Polynésie 2023 (jour 2)
Thème : Arbres : vocabulaire, mesures et algorithmique · Tiré du sujet Jour 2 (2023)
Énoncé
EXERCICE 1 (4 points)
Cet exercice porte sur les arbres binaires, les arbres binaires de recherche, la programmation orientée objet et la récursivité.
1.
On considère l'arbre ci-dessous:
a.
Justifier que cet arbre est un arbre binaire.
b.
Indiquer si l'arbre ci-dessus est un arbre binaire de recherche (ABR). Justifier votre réponse.
2.
On considère la classe Noeud, nous permettant de définir les arbres binaires, définie de la manière suivante en Python:
class Noeud:
def __init__(self, g, v, d):
"""crée un noeud d'un arbre binaire"""
self.gauche = g
self.valeur = v
self.droit = d
On considère également la fonction construire ci-dessous qui prend en paramètre deux entiers mini et maxi et qui renvoie un arbre.
def construire(mini, maxi):
"""mini, maxi: entiers respectant mini <= maxi"""
assert isinstance(mini, int) and isinstance(...,...) and...
if maxi - mini == 1 or maxi - mini == 0:
return Noeud(None, mini, None)
elif maxi - mini == 2:
return Noeud(None, (mini+maxi)//2, None)
else:
sag = construire(mini, (mini+maxi)//2)
sad = construire((mini+maxi)//2, maxi)
return Noeud(sag, (mini+maxi)//2, sad)
La fonction isinstance(obj, t) renvoie True si l'objet obj est du type t, sinon False.
a.
Recopier et compléter sur votre copie la ligne 3 de l'assertion de la fonction construire de manière à vérifier les conditions sur les paramètres mini et maxi.
b.
On exécute l'instruction construire(0, 8). Déterminer quels sont les différents appels récursifs de la fonction construire exécutés. On représentera ces appels sous forme d'une arborescence, par exemple:
c.
Dessiner l'arbre renvoyé par l'instruction construire(0, 8).
d.
Dessiner l'arbre renvoyé par l'instruction construire(0, 3).
e.
Donner le résultat d'un parcours infixe sur l'arbre obtenu à la question 2.c. Expliquer pourquoi ce parcours permet d'affirmer que l'arbre est un arbre binaire de recherche.
f.
La fonction récursive maximum ci-dessous prend en paramètre un arbre binaire de recherche abr et renvoie la valeur maximale de ses nœuds. Recopier et compléter les lignes 5 et 7 de cette fonction.
def maximum(abr):
if abr is None:
return None
elif abr.droit is None:
return.........
else:
return.........
3.
On donne l'arbre binaire de recherche abr_7_noeuds suivant:
On donne également ci-dessous la fonction mystere qui prend en paramètres un arbre binaire de recherche abr, un entier x et une liste liste.
def mystere(abr, x, liste):
"""
abr -- arbre binaire de recherche
x -- int
liste -- list
Renvoie -- list"""
if abr is None:
return []
else:
liste.append(abr.valeur)
if x == abr.valeur:
return liste
elif x < abr.valeur:
return mystere(abr.gauche, x, liste)
else:
return mystere(abr.droit, x, liste)
a.
Donner les résultats obtenus lorsque l'on exécute les instructions suivantes:
b.
Décrire quel peut être le rôle de la fonction mystere.
Corrigé
Corrigé proposé par AprenAI (non officiel)
1.a. Justifier que cet arbre est un arbre binaire.
Réponse : Chaque nœud de cet arbre possède au plus deux fils (un sous-arbre gauche et un sous-arbre droit).
1.b. Indiquer si l'arbre ci-dessus est un arbre binaire de recherche (ABR). Justifier votre réponse.
Réponse : Non, cet arbre n'est pas un arbre binaire de recherche (ABR).
2.a. Recopier et compléter sur votre copie la ligne 3 de l'assertion de la fonction construire de manière à vérifier les conditions sur les paramètres mini et maxi.
Réponse : assert isinstance(mini, int) and isinstance(maxi, int) and mini <= maxi
2.b, 2.c, 2.d. Arborescence des appels récursifs et dessins des arbres obtenus.
Réponse : 2.b. Arborescence des appels pour construire(0, 8) : - `construire(0, 8)` - gauche : `construire(0, 4)` - gauche : `construire(0, 2)` (cas de base, , renvoie `Noeud(None, 1, None)`) - droite : `construire(2, 4)` (cas de base, , renvoie `Noeud(None, 3, None)`) - droite : `construire(4, 8)` - gauche : `construire(4, 6)` (cas de base, , renvoie `Noeud(None, 5, None)`) - droite : `construire(6, 8)` (cas de base, , renvoie `Noeud(None, 7, None)`) 2.c. Arbre renvoyé par construire(0, 8) : - Racine : 4 - Sous-arbre gauche de racine 2 : - Fils gauche : 1 - Fils droit : 3 - Sous-arbre droit de racine 6 : - Fils gauche : 5 - Fils droit : 7 2.d. Arbre renvoyé par construire(0, 3) : - Racine : 1 (calculé par ) - Fils gauche : 0 (appel `construire(0, 1)`, cas de base , renvoie `Noeud(None, 0, None)`) - Fils droit : 2 (appel `construire(1, 3)`, cas de base , renvoie `Noeud(None, (1+3)//2, None)` soit 2)
2.e. Donner le résultat d'un parcours infixe sur l'arbre obtenu à la question 2.c.
Réponse : 1, 2, 3, 4, 5, 6, 7
2.e. Expliquer pourquoi ce parcours permet d'affirmer que l'arbre est un arbre binaire de recherche.
Réponse : Les valeurs issues du parcours infixe sont triées dans l'ordre strictement croissant (1, 2, 3, 4, 5, 6, 7). Or, un arbre binaire est un arbre binaire de recherche si et seulement si son parcours infixe énumère les clés dans l'ordre croissant.
Les réponses des 6 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 2 · Polynésie 2024 (jour 2) · Exercice 5 · Polynésie 2022 (jour 1) ›