Exercice 2 · Bac Numérique et Sciences Informatiques Polynésie 2026 (jour 1)

EXERCICE 2 (6 points)

Cet exercice porte sur la programmation Python, la Programmation Orientée Objet, les arbres binaires de recherche, les dictionnaires et les traitements sur le fichier CSV.

Dans le cadre d'un projet informatique, des étudiants sont chargés de développer une application console de gestion d'annuaire téléphonique. L'enseignant fournit un fichier contenant des contacts fictifs, chaque contact étant associé à un prénom (clé) et un numéro de téléphone (valeur). Le fichier des contacts est stocké dans la variable ci-dessous.

contacts_fictifs = [

{'Olivier': '01 23 45 67 89'},

{'Benjamin': '06 12 34 56 78'},

{'Sophie': '02 34 56 78 90'},

{'Antoine': '09 87 65 43 21'},

{'Eric': '03 45 67 89 01'},

{'Roxanne': '07 45 67 89 01'},

{'Victor': '03 56 78 90 12'},

{'Emilie': '04 23 45 67 89'},

{'Yann': '01 54 32 10 98'},

{'Zoé': '05 23 45 67 89'}

]

Cette application permet d'ajouter, de rechercher des contacts par nom et d'afficher tous les contacts dans l'ordre alphabétique.

Partie A

Un arbre binaire de recherche est utilisé pour stocker et gérer efficacement ces contacts.

Dans cet exercice, les arbres binaires de recherche ne peuvent pas comporter plusieurs fois la même clé.

Pour un arbre binaire de recherche limité à un nœud, on considère sa hauteur comme étant 1.

On considère l'arbre binaire de recherche suivant:

1.

Donner la structure de données de la variable contacts_fictifs.

2.

Justifier que l'arbre binaire ci-dessus est bien un arbre binaire de recherche pour l'ordre alphabétique.

3.

Indiquer la racine de cet arbre, puis donner l'ensemble des feuilles de cet arbre.

4.

Donner la hauteur et la taille de l'arbre.

5.

Citer l'avantage d'utiliser un arbre de recherche par rapport au type de données de la variable contacts_fictifs.

6.

Donner le sous-arbre droit du nœud Benjamin.

On considère les classes suivantes:

class Contact:

def __init__(self, v_prenom, v_num_tel):

self.prenom = v_prenom

self.num_tel = v_num_tel

class Noeud:

def __init__(self, v_contact, v_gauche=None, v_droite=None):

self.contact = v_contact

self.gauche = v_gauche

self.droite = v_droite

7.

Parmi les trois instructions (A), (B) et (C) suivantes, choisir celle qui construit et stocke dans la variable abr le sous-arbre qui a pour racine Benjamin.

A

>>> abr = Noeud(Contact('Benjamin', '06 12 34 56 78'), Noeud(Contact('Antoine', '09 87 65 43 21')), Noeud(Contact('Emilie', '04 23 45 67 89'), Noeud(Contact('Eric', '03 45 67 89 01'))))

B

>>> abr = Noeud(Contact('Benjamin', '06 12 34 56 78'), Noeud(Contact('Antoine', '09 87 65 43 21')), Noeud(Contact('Eric', '03 45 67 89 01'), Noeud(Contact('Emilie', '04 23 45 67 89'))))

C

>>> abr = Noeud(Noeud(Contact('Benjamin', '06 12 34 56 78'), ('Antoine', '09 87 65 43 21')), Noeud(Contact('Eric', '03 45 67 89 01'), ('Emilie', '04 23 45 67 89')))

On considère la classe suivante:

class ContactManager:

def __init__(self):

self.root = None

def inserer_contact(self, contact):

self.root = self.inserer_recursive(self.root, contact)

def inserer_recursive(self, noeud, contact):

if noeud is None:

return Noeud(contact)

if contact.prenom < noeud.contact.prenom:

noeud.gauche = self.inserer_recursive(noeud.gauche, contact)

else:

...

return noeud

def trouver_contact(self, prenom):

return self.trouver_recursive(self.root, prenom)

def trouver_recursive(self, noeud, prenom):

if noeud is None:

return None

...

return noeud.contact.num_tel

elif prenom < noeud.contact.prenom:

...

else:

return self.trouver_recursive(noeud.droite, prenom)

8.

Donner les instructions à placer dans les lignes 14, 23 et 26 pour compléter les méthodes inserer_recursive et trouver_recursive.

Dans le programme principal, on considère les instructions suivantes:

# Création du gestionnaire de contacts

contact_manager = ContactManager()

# Insertion des contacts

contact_manager.inserer_contact(Contact('Olivier', '01 23 45 67 89'))

contact_manager.inserer_contact(Contact('Benjamin', '06 12 34 56 78'))

contact_manager.inserer_contact(Contact('Sophie', '02 34 56 78 90'))

contact_manager.inserer_contact(Contact('Antoine', '09 87 65 43 21'))

contact_manager.inserer_contact(Contact('Eric', '03 45 67 89 01'))

contact_manager.inserer_contact(Contact('Roxanne', '07 45 67 89 01'))

contact_manager.inserer_contact(Contact('Victor', '03 56 78 90 12'))

contact_manager.inserer_contact(Contact('Emilie', '04 23 45 67 89'))

contact_manager.inserer_contact(Contact('Yann', '01 54 32 10 98'))

contact_manager.inserer_contact(Contact('Zoé', '05 23 45 67 89'))

9.

En utilisant la variable contact_manager définie à la ligne 2, et en particulier sa méthode trouver_contact (de la classe ContactManager), écrire en langage Python une fonction recherche_contact qui prend en paramètre prenom_recherche une chaîne de caractère à rechercher et qui affichera dans la console les résultats selon les cas prévus dans le sujet.

Dans le programme principal, on considère les instructions suivantes:

print("Liste des contacts triés:")

affichage_contacts_trie(contact_manager.root)

On souhaite afficher dans la console la liste des contacts dans l'ordre alphabétique.

10.

Indiquer, en le justifiant, le type de parcours à utiliser pour afficher la liste des prénoms dans l'ordre alphabétique (Parcours en largeur - parcours en profondeur dans l'ordre préfixe - parcours en profondeur dans l'ordre infixe - parcours en profondeur dans l'ordre postfixe).

Parcours en largeur

Parcours en profondeur dans l'ordre préfixe

Parcours en profondeur dans l'ordre infixe

Parcours en profondeur dans l'ordre postfixe

On donne la fonction récursive suivante:

def affichage_contacts_trie(noeud):

"""Afficher les contacts triés par nom"""

if noeud is not None:

...

...

affichage_contacts_trie(noeud.droite)

11.

Écrire les instructions des lignes 4 et 5 de la fonction récursive affichage_contacts_trie afin d'obtenir ce résultat.