NSI - Bac 2022

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'. La valeur None représente un sous-arbre vide.

# Code Python à analyser/compléter
class ABR:
    def __init__(self, racine=None):
        self.racine = racine
    
    def inserer(self, valeur):
        """Insère la valeur dans l'ABR"""
        if self.racine is None:
            self.racine = {'valeur': valeur, 'gauche': None, 'droite': None}
        else:
            self._inserer_rec(self.racine, valeur)
    
    def _inserer_rec(self, noeud, valeur):
        if valeur < noeud['valeur']:
            if noeud['gauche'] is None:
                noeud['gauche'] = {'valeur': valeur, 'gauche': None, 'droite': None}
            else:
                self._inserer_rec(noeud['gauche'], valeur)
        else:
            if noeud['droite'] is None:
                noeud['droite'] = {'valeur': valeur, 'gauche': None, 'droite': None}
            else:
                self._inserer_rec(noeud['droite'], valeur)
    
    def recherche(self, valeur):
        """Recherche la valeur dans l'ABR"""
        return self._recherche_rec(self.racine, valeur)
    
    def _recherche_rec(self, noeud, valeur):
        if noeud is None:
            return False
        if valeur == noeud['valeur']:
            return True
        elif valeur < noeud['valeur']:
            return self._recherche_rec(noeud['gauche'], valeur)
        else:
            return self._recherche_rec(noeud['droite'], valeur)
    
    def hauteur(self):
        """Retourne la hauteur de l'arbre"""
        return self._hauteur_rec(self.racine)
    
    def _hauteur_rec(self, noeud):
        # À compléter
        pass

1. Expliquez ce que fait la méthode recherche et donnez sa complexité dans le pire des cas.
2. Proposez une méthode itérative (non récursive) pour la recherche dans un ABR.
3. Complétez la méthode _hauteur_rec qui doit retourner la hauteur de l'arbre (0 pour un arbre vide, 1 pour un arbre avec uniquement la racine).

Exercice 2 — Algorithmique (6 points)

On considère la fonction suivante qui manipule des tableaux d'entiers :

def mystere(tab, x):
    '''
    tab : tableau d'entiers triés par ordre croissant
    x : entier
    '''
    g = 0
    d = len(tab) - 1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == x:
            return m
        elif tab[m] < x:
            g = m + 1
        else:
            d = m - 1
    return -1

1. Quel est le nom de l'algorithme implémenté par cette fonction ? Quel est son principe ?
2. Quelle est la complexité temporelle de cet algorithme dans le pire des cas ? Justifier.
3. On souhaite modifier la fonction pour qu'elle renvoie l'indice de la première occurrence de x dans le tableau (le tableau peut contenir plusieurs fois la même valeur). Compléter la fonction suivante :

def premiere_occurrence(tab, x):
    '''
    tab : tableau d'entiers triés par ordre croissant
    x : entier
    Renvoie l'indice de la première occurrence de x dans tab, ou -1 si x n'est pas présent
    '''
    g = 0
    d = len(tab) - 1
    resultat = -1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == x:
            # À compléter
            pass
        elif tab[m] < x:
            g = m + 1
        else:
            d = m - 1
    return resultat

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

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

• id_etudiant (entier, clé primaire)
• nom (texte)
• prenom (texte)
• annee_naissance (entier)
• specialite (texte)

On souhaite implémenter en Python des fonctions pour manipuler cette base de données SQLite.

import sqlite3

def creer_connexion(nom_bd):
    """Crée une connexion à la base de données SQLite spécifiée"""
    conn = None
    try:
        conn = sqlite3.connect(nom_bd)
        return conn
    except sqlite3.Error as e:
        print(e)
    return conn

def creer_table(conn):
    """Crée la table Etudiants"""
    sql_create_table = """
    CREATE TABLE IF NOT EXISTS Etudiants (
        id_etudiant INTEGER PRIMARY KEY,
        nom TEXT NOT NULL,
        prenom TEXT NOT NULL,
        annee_naissance INTEGER,
        specialite TEXT
    );
    """
    try:
        c = conn.cursor()
        c.execute(sql_create_table)
    except sqlite3.Error as e:
        print(e)

def ajouter_etudiant(conn, etudiant):
    """Ajoute un nouvel étudiant à la table"""
    sql = ''' INSERT INTO Etudiants(id_etudiant, nom, prenom, annee_naissance, specialite)
              VALUES(?,?,?,?,?) '''
    cur = conn.cursor()
    cur.execute(sql, etudiant)
    conn.commit()
    return cur.lastrowid

def rechercher_etudiants_par_specialite(conn, specialite):
    """Recherche tous les étudiants d'une spécialité donnée"""
    cur = conn.cursor()
    cur.execute("SELECT * FROM Etudiants WHERE specialite=?", (specialite,))
    return cur.fetchall()

# Code principal
conn = creer_connexion("universite.db")
if conn is not None:
    creer_table(conn)
    
    # Ajout de quelques étudiants
    etudiants = [
        (1, 'Dupont', 'Jean', 2003, 'NSI'),
        (2, 'Martin', 'Marie', 2004, 'Maths'),
        (3, 'Durand', 'Pierre', 2003, 'NSI'),
        (4, 'Leroy', 'Sophie', 2004, 'Physique')
    ]
    
    for etudiant in etudiants:
        ajouter_etudiant(conn, etudiant)
    
    # Recherche des étudiants en NSI
    resultats = rechercher_etudiants_par_specialite(conn, 'NSI')
    print("Étudiants en NSI:")
    for etudiant in resultats:
        print(etudiant)
    
    conn.close()
else:
    print("Erreur! impossible de créer la connexion à la base de données.")

1. Expliquez pourquoi l'utilisation des paramètres '?' dans la fonction ajouter_etudiant est importante pour la sécurité des données. Quel risque évite-t-on ?

2. Proposez une fonction Python qui calcule l'âge moyen des étudiants d'une spécialité donnée. Quelle est la complexité algorithmique de votre solution ?

3. Complétez le code pour ajouter une fonction qui permet de mettre à jour la spécialité d'un étudiant donné par son identifiant.