Exercice 4 · Bac Numérique et Sciences Informatiques Métropole 2022 (sujet 1)

EXERCICE 4 (4 points)

Cet exercice, composé de deux parties A et B, porte sur le parcours des arbres binaires, le principe « diviser pour régner » et la récursivité.

Cet exercice traite du calcul de la somme d’un arbre binaire. Cette somme consiste à additionner toutes les valeurs numériques contenues dans les nœuds de l’arbre.

L’arbre utilisé dans les parties A et B est le suivant:

Partie A: Parcours d'un arbre

1.

Donner la somme de l’arbre précédent. Justifier la réponse en explicitant le calcul qui a permis de l’obtenir.

2.

Indiquer la lettre correspondante aux noms ‘racine’, ‘feuille’, ‘nœud’, ‘SAG’ (Sous Arbre Gauche) et ‘SAD’ (Sous Arbre Droit). Chaque lettre A, B, C, D et E devra être utilisée une seule fois.

Terme

Lettre associée

Racine

Feuille

Nœud

SAG (Sous Arbre Gauche)

SAD (Sous Arbre Droit)

3.

Parmi les quatre propositions A, B, C et D ci-dessous, donnant un parcours en largeur d’abord de l’arbre, une seule est correcte. Indiquer laquelle.

4.

Écrire en langage Python la fonction somme qui prend en paramètre une liste de nombres et qui renvoie la somme de ses éléments.

Exemple: somme([1, 2, 3, 4]) est égale à 10.

5.

La fonction parcourir(arbre) pourrait se traduire en langage naturel par:

parcourir(A):

L = liste_vide

F = file_vide

enfiler A dans F

Tant que F n'est pas vide

défiler S de F

ajouter la valeur de la racine de S dans L

Pour chaque sous arbre SA non vide de S

enfiler SA dans F

renvoyer L

Partie B: Méthode ‘diviser pour régner’

6.

Parmi les quatre propositions A, B, C et D ci-dessous, indiquer la seule proposition correcte.

En informatique, le principe diviser pour régner signifie:

7.

L’arbre présenté dans le problème peut être décomposé en racine et sous arbres:

8.

Écrire en langage Python une fonction récursive calcul_somme(arbre).

Cette fonction calcule la somme de l'arbre passé en paramètre.

Les fonctions suivantes sont disponibles:

- est_vide(arbre): renvoie True si arbre est vide et renvoie False sinon;

- valeur_racine(arbre): renvoie la valeur numérique de la racine de arbre;

- arbre_gauche(arbre): renvoie le sous arbre gauche de arbre;

- arbre_droit(arbre): renvoie le sous arbre droit de arbre.