NSI - Bac 2024

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

[Contexte] On considère une structure de données permettant de représenter un arbre binaire. Un arbre binaire est soit vide, soit un nœud contenant une valeur et deux sous-arbres (gauche et droit).

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droit = droit

def parcours_prefixe(arbre):
    """Retourne la liste des valeurs de l'arbre dans l'ordre préfixe."""
    if arbre is None:
        return []
    else:
        return [arbre.valeur] + parcours_prefixe(arbre.gauche) + parcours_prefixe(arbre.droit)

# Exemple d'arbre :
#       1
#      / \
#     2   3
#    / \
#   4   5
arbre_exemple = Noeud(1,
                     Noeud(2,
                           Noeud(4),
                           Noeud(5)),
                     Noeud(3))
print(parcours_prefixe(arbre_exemple))  # Affiche [1, 2, 4, 5, 3]

1. Quelle est la complexité temporelle de la fonction parcours_prefixe en fonction du nombre n de nœuds de l'arbre ? Justifiez votre réponse.

2. On souhaite maintenant implémenter une fonction hauteur(arbre) qui retourne la hauteur de l'arbre (la hauteur d'un arbre vide est -1, la hauteur d'un arbre réduit à un nœud est 0). Proposez une implémentation récursive de cette fonction.

3. Complétez la fonction est_equilibre(arbre) ci-dessous qui retourne True si l'arbre est équilibré, c'est-à-dire si pour chaque nœud, les hauteurs de ses sous-arbres gauche et droit diffèrent d'au plus 1, et False sinon.

def est_equilibre(arbre):
    """Retourne True si l'arbre est équilibré, False sinon."""
    if arbre is None:
        return True
    else:
        # À compléter

Exercice 2 — Algorithmique (6 points)

On considère l'algorithme suivant qui permet de déterminer si une chaîne de caractères est un palindrome (elle se lit de la même façon de gauche à droite et de droite à gauche).

def est_palindrome(chaine):
    """
    Détermine si une chaîne de caractères est un palindrome.
    """
    n = len(chaine)
    for i in range(n // 2):
        if chaine[i] != chaine[n - 1 - i]:
            return False
    return True

1. Expliquez ce que fait la fonction est_palindrome et donnez sa complexité temporelle en fonction de la longueur n de la chaîne.

2. On souhaite maintenant écrire une fonction récursive est_palindrome_rec qui réalise la même tâche. Complétez le code ci-dessous :

def est_palindrome_rec(chaine):
    """
    Version récursive pour déterminer si une chaîne est un palindrome.
    """
    n = len(chaine)
    if n <= 1:
        return True
    if chaine[0] != chaine[n - 1]:
        return False
    # À compléter

1. Modifiez la fonction est_palindrome_rec pour qu'elle ignore les espaces et la casse (majuscules/minuscules). Par exemple, "Ésope reste ici et se repose" doit être considéré comme un palindrome.

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

Un développeur travaille sur une application de gestion de bibliothèque. Il utilise une base de données relationnelle contenant les tables suivantes :

• LIVRES (id_livre, titre, auteur, annee_publication, id_genre)
• GENRES (id_genre, nom_genre)
• EMPRUNTS (id_emprunt, id_livre, date_emprunt, date_retour)

Il souhaite créer une fonction Python qui permet de récupérer les livres empruntés pendant une période donnée, avec leur genre.

import sqlite3

def livres_empruntes_periode(date_debut, date_fin):
    """
    Retourne la liste des livres empruntés entre date_debut et date_fin
    avec leur titre, auteur et nom du genre.
    """
    conn = sqlite3.connect('bibliotheque.db')
    curseur = conn.cursor()
    
    requete = """
    SELECT L.titre, L.auteur, G.nom_genre
    FROM LIVRES L
    JOIN GENRES G ON L.id_genre = G.id_genre
    JOIN EMPRUNTS E ON L.id_livre = E.id_livre
    WHERE E.date_emprunt BETWEEN ? AND ?
    """
    
    curseur.execute(requete, (date_debut, date_fin))
    resultats = curseur.fetchall()
    
    conn.close()
    return resultats

# Test de la fonction
print(livres_empruntes_periode('2024-01-01', '2024-03-31'))

1. Expliquez ce que fait la requête SQL dans la fonction, en détaillant chaque clause (SELECT, FROM, JOIN, WHERE).

2. Le développeur souhaite maintenant modifier la fonction pour qu'elle retourne également le nombre total d'emprunts par livre pendant la période. Proposez une solution algorithmique en expliquant votre démarche.

3. Complétez le code Python ci-dessous pour implémenter cette nouvelle fonctionnalité :

def livres_empruntes_avec_compteur(date_debut, date_fin):
    """
    Retourne la liste des livres empruntés entre date_debut et date_fin
    avec leur titre, auteur, nom du genre et nombre d'emprunts.
    """
    conn = sqlite3.connect('bibliotheque.db')
    curseur = conn.cursor()
    
    # À compléter : écrire la requête SQL adaptée
    requete = """
    """
    
    curseur.execute(requete, (date_debut, date_fin))
    resultats = curseur.fetchall()
    
    conn.close()
    return resultats