Bac NSI — La Réunion 2022 (Jour 1) : sujet et corrigé

Présentation de l'épreuve

Épreuve écrite de spécialité NSI, session 2022, centre de La Réunion, jour 1. Durée : 3h30, calculatrice interdite. Le sujet comporte 5 exercices indépendants notés sur 4 points chacun ; le candidat en choisit 3.

Exercice 1 — Piles et files

On munit les structures abstraites Pile et File de leurs primitives usuelles : creer_pile_vide(), est_pile_vide(p), empiler(p, element), depiler(p), sommet(p) (renvoie le sommet sans le retirer) ; creer_file_vide(), est_file_vide(f), enfiler(f, element), defiler(f), ainsi que taille_file(f).

Convention graphique : une file est représentée en ligne, l'élément de droite étant la tête (premier servi, retiré par defiler) et l'élément de gauche la queue (où enfiler ajoute les nouveaux arrivants). Une pile est représentée en colonne, le sommet en haut.

File f initiale (queue → tête) : 4, 3, 8, 2, 1. Pile p initiale (sommet → fond) : 5, 8, 6, 2.

1. Les quatre questions suivantes repartent chacune de p et f initiales. a. Représenter f après enfiler(f, defiler(f)). b. Représenter p après empiler(p, depiler(p)). c. Représenter p et f après :

for i in range(2):
    enfiler(f, depiler(p))

d. Représenter p et f après :

for i in range(2):
    empiler(p, defiler(f))

2. Fonction mystere, qui modifie la file passée en paramètre sans rien renvoyer explicitement à travers son opération, mais renvoie la pile utilisée :

def mystere(f):
    p = creer_pile_vide()
    while not est_file_vide(f):
        empiler(p, defiler(f))
    while not est_pile_vide(p):
        enfiler(f, depiler(p))
    return p

Préciser l'état de f après chaque boucle de mystere appliquée à la file 1, 2, 3, 4 (queue → tête), et le contenu de la pile renvoyée.

3. Algorithme knuth(f) :

def knuth(f):
    p = creer_pile_vide()
    N = taille_file(f)
    for i in range(N):
        if est_pile_vide(p):
            empiler(p, defiler(f))
        else:
            e = defiler(f)
            if e >= sommet(p):
                empiler(p, e)
            else:
                while not est_pile_vide(p) and e < sommet(p):
                    enfiler(f, depiler(p))
                empiler(p, e)
    while not est_pile_vide(p):
        enfiler(f, depiler(p))

a. Détailler pas à pas l'exécution pour la file 2, 1, 3 (le tableau donné dans le sujet indique déjà : après le premier passage, f vaut 2, 1 et p vaut 3). b. Que fait cet algorithme ?

Exercice 2 — Programmation objet : bulles d'un jeu vidéo

Dans un jeu de plateforme, des bulles rondes se déplacent aléatoirement ; quand une petite bulle touche une plus grosse, elle disparaît et cède toute sa surface à la grosse bulle (dont la vitesse est ensuite réduite de moitié). Chaque bulle est un objet de la classe suivante :

from random import randint
from math import *
 
class Cbulle:
    def __init__(self):
        self.xc = randint(0, 100)
        self.yc = randint(0, 100)
        self.rayon = randint(0, 10)
        self.dirx = float(randint(-1, 1))
        self.diry = float(randint(-1, 1))
        self.couleur = randint(1, 65535)
 
    def bouge(self):
        self.xc = self.xc + self.dirx
        self.yc = self.yc + self.diry

On limite le jeu à 6 bulles, stockées dans Mousse = [None, None, None, None, None, None] puis remplies par des instances de Cbulle. Quand une bulle disparaît, son emplacement redevient None ; une nouvelle bulle prend le premier emplacement None disponible.

1.a. Compléter :

def donnePremierIndiceLibre(Mousse):
    """Renvoie l'indice du premier None dans Mousse, ou 6 s'il n'y en a pas."""
    i = 0
    while ......... and Mousse[i] != None:
        .........
    return i

1.b. Écrire placeBulle(B) qui place l'objet B (instance de Cbulle) dans le premier emplacement libre de Mousse (ne fait rien si aucun emplacement n'est libre).

2. On dispose de distanceEntreBulles(B1, B2), qui renvoie la distance entre les centres de deux bulles. Écrire bullesEnContact(B1, B2), qui renvoie True si B2 touche B1 (distance entre centres ≤ somme des rayons).

3. Compléter la fonction collision, appelée quand une petite bulle d'indice indPetite touche une grosse bulle d'indice indGrosse :

def collision(indPetite, indGrosse, mousse):
    surfPetite = pi * Mousse[indPetite].rayon**2
    surfGrosse = pi * Mousse[indGrosse].rayon**2
    surfGrosseApresCollision = ..........................
    rayonGrosseApresCollision = sqrt(surfGrosseApresCollision / pi)
    # réduction de 50% de la vitesse de la grosse bulle
    Mousse[indGrosse].dirx = ..........................
    Mousse[indGrosse].diry = ..........................
    # suppression de la petite bulle dans Mousse
    ..........................

Exercice 3 — Bases de données : QCM en ligne

Un enseignant gère une base QCM_NSI avec 4 tables : eleves(ideleve, nom, prenom), qcm(idqcm, titre, date), questions(idquestion, #idqcm, question, bonnereponse) et lien_eleve_qcm(#ideleve, #idqcm, note) dont la clé primaire est le couple (ideleve, idqcm).

Extrait des données :

Table eleves : (2, Dubois, Thomas), (3, Dupont, Cassandra), (4, Marty, Mael), (5, Bikila, Abebe).

Table qcm : (1, "Base de données", 2021-09-20), (2, "POO", 2022-04-08), (3, "Arbre Binaire", 2022-01-09), (4, "Arbre Parcours", 2022-02-15), (5, "Piles-Files", 2021-12-05).

Table lien_eleve_qcm (ideleve, idqcm, note) : (2,1,12), (2,3,18), (2,4,13), (2,5,15), (3,1,20), (3,2,9), (3,3,18), (3,5,13), (4,4,15), (4,5,20), (5,4,15).

1.a. Que renvoie SELECT titre FROM qcm WHERE date > '2022-01-10'; ? 1.b. Écrire une requête donnant les notes de l'élève d'identifiant 4.

2.a. La clé primaire de lien_eleve_qcm est le couple (ideleve, idqcm). Expliquer pourquoi un élève ne peut donc pas faire deux fois le même QCM. 2.b. Marty Mael vient de faire le QCM sur la POO et a obtenu 18. Comment est modifiée la base (sans écrire de SQL) ? 2.c. Un nouvel élève (Lefèvre, Kevin) est inscrit : écrire la requête d'enregistrement. 2.d. Dubois Thomas (ideleve = 2) quitte l'établissement : écrire la requête supprimant toutes ses références dans lien_eleve_qcm.

3.a. Compléter :

SELECT .............................. FROM eleves
JOIN lien_eleve_qcm ON eleves.ideleve = ..............................
WHERE .............................. ;

pour qu'elle affiche noms et prénoms des élèves ayant fait le QCM d'idqcm = 4. 3.b. Donner le résultat de cette requête.

4. Écrire une requête (utilisant les 3 tables) affichant nom, prénom et note des élèves ayant fait le QCM "Arbre Binaire".

Exercice 4 — Arbres : généalogie et parcours en profondeur

On modélise un arbre généalogique fictif : le nœud N (classe Noeud, attributs identite = (prénom, nom), gauche, droite) a pour sous-arbre gauche son père, pour sous-arbre droit sa mère. Racine : Albert Normand. Ses parents : Jules Normand (père) et Marie Comtois (mère). Grands-parents paternels : Michel Normand et Hélène Breton ; grands-parents maternels : Thibaut Comtois et Gabrielle Savoyard. Arrière-grands-parents (génération 3, tous sans parents connus dans l'arbre) : côté Michel Normand → Jules Normand et Odile Picard ; côté Hélène Breton → Evariste Breton et Camélia Charentais ; côté Thibaut Comtois → Léo Comtois et Eulalie Lorrain ; côté Gabrielle Savoyard → Guillaume Savoyard et Janet Chesterfield.

1.a. En quoi cet arbre généalogique est-il un arbre binaire ? 1.b. Pourquoi n'est-ce pas un arbre binaire de recherche (ABR) ?

2.a. Donner les 7 premières personnes rencontrées en parcours préfixe. 2.b. Donner les 7 premières personnes rencontrées en parcours infixe.

Code incomplet (l'instruction d'affichage manque) :

def parcours(racine_de_l_arbre):
    if racine_de_l_arbre != None:
        noeud_actuel = racine_de_l_arbre
        parcours(noeud_actuel.gauche)
        parcours(noeud_actuel.droite)

2.c. Insérer l'instruction d'affichage pour obtenir un parcours préfixe. 2.d. Insérer l'instruction d'affichage pour obtenir un parcours infixe.

3.a. Ajouter à la classe Noeud un attribut generation, valant 0 par défaut :

class Noeud:
    def __init__(self, prenom, nom):
        self.identite = (prenom, nom)
        self.gauche = None
        self.droite = None
        ..........................

3.b. Écrire numerotation(racine_de_l_arbre, num_gen=0), fonction récursive qui affecte generation à chaque ancêtre (parents = génération 1, etc.).

4. Avec :

def mystere(N, affiche):
    if N != None:
        if affiche:
            print(N.identite[0])
        mystere(N.gauche, False)
        mystere(N.droite, True)

donner, dans l'ordre, le résultat de mystere(racine_de_l_arbre, False) où racine_de_l_arbre référence Albert Normand.

Exercice 5 — Réseaux : adressage IP et notation CIDR

Pour une "LAN party", deux réseaux non reliés physiquement sont utilisés : réseau 1 (switch1), avec des serveurs 172.150.4.10, 172.150.4.3 et le PC3 en 172.150.4.30/24 ; réseau 2 (switch2), avec des PC en 192.168.5.10, .25, .27, .28.

1.a. Combien d'octets compose une adresse IPv4 ? 1.b. Quelle est la notation décimale du masque de sous-réseau associé à /24 ?

2. Compléter le tableau (adresse du PC3, 172.150.4.30/24) : conversion binaire de l'IP, masque en binaire, ET logique bit à bit, puis adresse réseau décimale.

3.a. Parmi ces propositions, laquelle/lesquelles conviendrait(ent) pour un 4ᵉ PC du réseau 1 ? 1) 172.154.4.30 2) 172.150.4.10 3) 172.150.10.257 4) 172.150.4.11 5) 172.150.4.0 6) 172.150.4.200 3.b. Quelle commande système permet de connaître sa propre adresse IP ?

4. On envisage de relier directement switch1 à switch2 pour que toutes les machines communiquent. Expliquer pourquoi cette solution est insuffisante, et proposer une alternative.

5. On représente les adresses IP connues par une liste de listes, par exemple liste_IP = [[192,168,10,1],[192,168,10,25],[192,168,10,13]]. Écrire adresse(ip, liste_IP) qui ajoute ip à la liste et affiche "pas trouvée, ajoutée" si elle n'y figure pas encore, ou affiche seulement "trouvée" sinon.

Bac NSI — La Réunion 2022 (Jour 1)

Sujet