NSI - Bac 2023

Exercice 1 — Structures de données (6 points)

[Contexte] On considère une structure de données représentant un arbre binaire de recherche (ABR) stockant des entiers. Chaque nœud est représenté par un dictionnaire avec les clés 'valeur', 'gauche' et 'droite'. L'arbre vide est représenté par None.

# Code Python à analyser/compléter
class ABR:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None
    
    def inserer(self, valeur):
        """Insère la valeur dans l'ABR"""
        if valeur < self.valeur:
            if self.gauche is None:
                self.gauche = ABR(valeur)
            else:
                self.gauche.inserer(valeur)
        elif valeur > self.valeur:
            if self.droite is None:
                self.droite = ABR(valeur)
            else:
                self.droite.inserer(valeur)
    
    def recherche(self, valeur):
        """Recherche la valeur dans l'ABR"""
        if self is None:
            return False
        if valeur == self.valeur:
            return True
        elif valeur < self.valeur:
            if self.gauche is None:
                return False
            else:
                return self.gauche.recherche(valeur)
        else:
            if self.droite is None:
                return False
            else:
                return self.droite.recherche(valeur)
    
    def parcours_infixe(self):
        """Retourne la liste des valeurs dans l'ordre croissant"""
        resultat = []
        if self.gauche is not None:
            resultat.extend(self.gauche.parcours_infixe())
        resultat.append(self.valeur)
        if self.droite is not None:
            resultat.extend(self.droite.parcours_infixe())
        return resultat

# Exemple d'utilisation
arbre = ABR(10)
arbre.inserer(5)
arbre.inserer(15)
arbre.inserer(3)
arbre.inserer(7)
print(arbre.parcours_infixe())  # Affiche [3, 5, 7, 10, 15]

1. La méthode recherche contient une erreur. Expliquez pourquoi la condition if self is None: à la ligne 25 ne fonctionnera jamais comme prévu, et proposez une correction.

2. Quelle est la complexité temporelle (dans le pire des cas) des méthodes inserer et recherche dans cet ABR ? Justifiez votre réponse.

3. Complétez la classe ABR en ajoutant une méthode hauteur(self) qui retourne la hauteur de l'arbre (la hauteur d'un arbre vide est 0, la hauteur d'un arbre avec un seul nœud est 1).

Exercice 2 — Algorithmique (6 points)

On considère l'algorithme suivant qui permet de déterminer si un tableau d'entiers contient des doublons (valeurs apparaissant au moins deux fois).

def contient_doublons(tab):
    """
    tab : liste d'entiers
    Renvoie True si tab contient au moins un doublon, False sinon
    """
    n = len(tab)
    for i in range(n):
        for j in range(i + 1, n):
            if tab[i] == tab[j]:
                return True
    return False

1. Donner la complexité temporelle de cet algorithme dans le pire des cas, en fonction de n (la taille du tableau). Justifier votre réponse.

2. Proposer une version améliorée de cet algorithme qui aurait une complexité temporelle meilleure dans le pire des cas. Expliquer brièvement pourquoi votre solution est plus efficace.

3. Compléter le code Python ci-dessous qui implémente votre solution améliorée :

def contient_doublons_ameliore(tab):
    """
    tab : liste d'entiers
    Renvoie True si tab contient au moins un doublon, False sinon
    Version améliorée
    """
    # À compléter

Exercice 3 — Bases de données (6 points)

On considère une base de données relationnelle contenant une table 'Etudiants' avec les attributs suivants:

• id_etudiant (INT, clé primaire)
• nom (TEXT)
• prenom (TEXT)
• annee_naissance (INT)
• specialite (TEXT)

On souhaite créer une fonction Python qui permet de récupérer les étudiants nés après une certaine année et triés par nom.

import sqlite3

def get_etudiants_apres_annee(annee, specialite=None):
    """
    Récupère les étudiants nés après 'annee'.
    Si 'specialite' est spécifié, filtre également par spécialité.
    Retourne une liste de tuples (nom, prenom, annee_naissance).
    """
    conn = sqlite3.connect('universite.db')
    cursor = conn.cursor()
    
    if specialite:
        requete = "SELECT nom, prenom, annee_naissance FROM Etudiants WHERE annee_naissance > ? AND specialite = ? ORDER BY nom"
        cursor.execute(requete, (annee, specialite))
    else:
        requete = "SELECT nom, prenom, annee_naissance FROM Etudiants WHERE annee_naissance > ? ORDER BY nom"
        cursor.execute(requete, (annee,))
    
    resultats = cursor.fetchall()
    conn.close()
    return resultats

# Exemple d'utilisation
print(get_etudiants_apres_annee(2000))
print(get_etudiants_apres_annee(2000, "NSI"))

1. Expliquez pourquoi l'utilisation des paramètres '?' dans les requêtes SQL est préférable à la concaténation de chaînes. Quels risques cela évite-t-il ?

2. Proposez une modification de la fonction pour qu'elle retourne également l'âge actuel de chaque étudiant (en supposant l'année actuelle 2023). Quelle serait la complexité temporelle de votre solution ?

3. Complétez la fonction suivante qui doit permettre d'ajouter un nouvel étudiant dans la base de données, en vérifiant d'abord que l'id_etudiant n'existe pas déjà :

def ajouter_etudiant(id_etudiant, nom, prenom, annee_naissance, specialite):
    """
    Ajoute un étudiant s'il n'existe pas déjà.
    Retourne True si l'ajout a réussi, False sinon.
    """
    conn = sqlite3.connect('universite.db')
    cursor = conn.cursor()
    
    # Vérifier si l'id existe déjà
    # À COMPLÉTER
    
    # Ajouter l'étudiant
    # À COMPLÉTER
    
    conn.close()
    return False  # À MODIFIER