Sujet du bac 2022 de NSI — Métropole, Mayotte, La Réunion, Antilles Guyane, jour 1 (session de remplacement) (général)

22-NSIJ1ME3 BACCALAURÉAT GÉNÉRAL ÉPREUVE D’ENSEIGNEMENT DE SPÉCIALITÉ SESSION 2022 NUMÉRIQUE ET SCIENCES INFORMATIQUES Jour 1 Durée de l’épreuve : 3 heures 30 L’usage de la calculatrice n’est pas autorisé. Dès que ce sujet vous est remis, assurez-vous qu’il est complet. Ce sujet comporte 13 pages numérotées de à . Le candidat traite au choix 3 exercices parmi les 5 exercices proposés Chaque exercice est noté sur 4 points. 22-NSIJ1ME3 EXERCICE 1 (4 points) Cet exercice porte sur le thème ‘‘Algorithmique’’, les arbres binaires de recherche et leurs parcours. Rappel : Un arbre binaire de recherche (ABR) est un arbre binaire étiqueté avec des clés tel que : - Les clés du sous arbre gauche sont inférieures ou égales à celle de la racine ; - Les clés du sous arbre droit sont strictement supérieures à celle de la racine ; - Les deux sous arbres sont eux-mêmes des arbres binaires de recherche. Partie A : Préambule 1) Recopier sur votre copie le ou les numéro(s) correspondant aux arbres binaires de recherche parmi les arbres suivants : Arbre 1 Arbre 2 Arbre 3 22-NSIJ1ME3 Partie B : Analyse On considère la structure de données abstraites ABR (Arbre Binaire de Recherche) que l’on munit des opérations suivantes : Structure de données : ABR Utilise : Booleen, Element Opérations : • creer_arbre : ∅ →ABR creer_arbre() renvoie un arbre vide. • est_vide : ABR→Booleen est_vide(a) renvoie True si l’arbre a est vide et False sinon. • racine : ABR→ Element racine(a) renvoie la clé de la racine de l’arbre non vide a. • sous_arbre_gauche : ABR→ABR sous_arbre_gauche(a) renvoie le sous-arbre gauche de l’arbre non vide a. • sous_arbre_droit : ABR→ABR sous_arbre_droit(a) renvoie le sous-arbre droit de l’arbre non vide a. • inserer : ABR, Element→Rien inserer(a, e) insère la clé e dans l’arbre a. 2.a) Dans un ABR, où se trouve le plus petit élément ? Justifier. Pour rechercher une clé dans un …