Bac NSI — Métropole 2022 (Jour 1, 11 mai)

Présentation de l'épreuve

Épreuve écrite de spécialité NSI, session 2022, Métropole, mercredi 11 mai 2022. Durée : 3h30, calculatrice interdite. 5 exercices notés sur 4 points, le candidat en choisit 3.

Exercice 1 — Structures de données : parenthésage et balisage

Partie A — Expression correctement parenthésée. On enregistre, dans l'ordre d'apparition, uniquement les parenthèses d'une expression arithmétique (« expression simplifiée »). Exemple : "(2+3)×(18/(4+2))" donne l'expression simplifiée ( ) ( ( ) ).

1. La phrase « les éléments sont retirés dans le même ordre qu'ils ont été ajoutés » décrit-elle une file ou une pile ? Justifier.

On utilise une variable controleur (0 au départ, +1 sur (, -1 sur )). Exemple : pour ( ) ( ( ) ), controleur prend 1,0,1,2,1,0 (parenthésage correct).

2. Donner les valeurs successives de controleur pour B = ((( )( ) et C = (( )))(.

3. B est mal parenthésée (fermantes manquantes, controleur ≠ 0 en fin d'analyse) ; C est mal parenthésée (fermante sans ouvrante, controleur négatif en cours d'analyse). Compléter les lignes 13 et 16 :

 1 def parenthesage_correct(expression):
 7     controleur = 0
 8     for parenthese in expression:
 9         if parenthese == '(':
10             controleur = controleur + 1
11         else:
12             controleur = controleur - 1
13             if controleur ... :   # test 1
14                 return False
16     if controleur ... :   # test 2
17         return True
18     else:
19         return False

Partie B — Texte correctement balisé. Analogie HTML/parenthèses : "<p><strong><em></em></strong></p>" est correctement balisé (on ignore les balises sans fermeture comme <br>). Algorithme par pile : balise ouvrante → empiler ; balise fermante → si pile vide, incorrect ; sinon dépiler et vérifier la correspondance des noms.

4.a. Représenter la pile à chaque étape pour "<p><em></em></p>" (balisage correct). 4.b. Quelle condition simple sur la pile signale un balisage correct une fois toute l'expression parcourue ?

5. Une expression correctement balisée contient 12 balises. Quel est le nombre maximal d'éléments que peut contenir la pile durant l'analyse ?

Exercice 2 — Bases de données : cinéma

Schéma relationnel : individu(id_ind, nom, prenom, naissance), realisation(id_rea, titre, annee, type), emploi(id_emp, description, #id_ind, #id_rea).

Extrait individu : (105,Hulka,Daniel,01-06-1968), (403,Travis,Daniel,10-03-1968), (688,Crog,Daniel,07-07-1968), (695,Pollock,Daniel,24-08-1968). Extrait realisation : (105,"Casino Imperial",2006,action), (325,"Ciel tombant",2012,action), (655,"Fantôme",2015,action), (950,"Mourir pour attendre",2021,action).

1.a. Que renvoie SELECT nom, prenom, naissance FROM individu WHERE nom = 'Crog'; ? 1.b. Requête donnant titre et clé primaire de chaque film sorti strictement après 2020.

2.a. Pour corriger la date de naissance de Daniel Crog, faut-il utiliser :

UPDATE individu SET naissance = '02-03-1968'
WHERE id_ind = 688 AND nom = 'Crog' AND prenom = 'Daniel';

ou

INSERT INTO individu VALUES (688, 'Crog', 'Daniel', '02-03-1968');

Justifier en expliquant pourquoi l'autre requête échouerait. 2.b. La table individu peut-elle accepter deux individus de même nom, prénom et date de naissance ?

3.a. Compléter pour ajouter les rôles de Daniel Crog (James Bond) dans "Casino Impérial" (id_rea 105) puis "Ciel tombant" (id_rea 325) :

INSERT INTO emploi VALUES (5400, 'Acteur(James Bond)', ...);
INSERT INTO emploi VALUES (5401, 'Acteur(James Bond)', ...);

3.b. Pour un nouveau rôle de Daniel Crog dans "Docteur Yes" (film pas encore enregistré) : faut-il créer d'abord le film ou d'abord le rôle ? Pourquoi ?

4.a. Compléter pour obtenir nom de l'acteur, titre et année de sortie de tous les rôles 'Acteur(James Bond)' :

SELECT ...
FROM emploi
JOIN individu ON ...
JOIN realisation ON ...
WHERE emploi.description = 'Acteur(James Bond)';

4.b. Requête donnant uniquement les descriptions des emplois de Denis Johnson.

Exercice 3 — Représentations binaires et protocoles de routage

1.a. Donner en décimal l'adresse IPv4 : 11000000.10101000.10000000.10000011. 1.b. Le réseau A a toutes ses adresses de la forme 192.168.128._ _ _ (seul le dernier octet varie). Combien d'adresses différentes possibles ?

2. Tables de routage RIP (métrique = nombre de sauts) de 5 routeurs A à E : Routeur A : A0,B1,C1,D1,E2. Routeur B : A1,B0,C2,D1,E2. Routeur C : A1,B2,C0,D1,E2. Routeur D : A1,B1,C1,D0,E1. Routeur E : A2,B2,C2,D1,E0.

2.a. Lister les routeurs directement reliés à A. 2.b. Représenter sommairement le graphe des 5 routeurs et de leurs liaisons.

3. OSPF : $\text{métrique} = \dfrac{10^8}{\text{débit (bps)}}$. Compléter :

4. Réseau OSPF de 7 routeurs F à L (coûts des liaisons ci-dessous), table de routage partielle de F (F=0, G=8, H=5) :

Liaisons : F–G (8), F–H (5), F–I (20), G–I (6), G–L (3), H–J (4), H–I (20), I–J (5), L–J (2), J–K (3), I–K (15).

4.a. Indiquer, en justifiant, le chemin emprunté par un message de F vers I. 4.b. Compléter entièrement la table de routage de F. 4.c. Citer une unique panne qui forcerait tout le trafic à destination de F à transiter par G.

Exercice 4 — Arbres, parcours et diviser pour régner

Arbre binaire (valeurs) :

        3
      /   \\
     6     2
    / \\   / \\
   7   4 9   1

Partie A — Parcours d'un arbre.

1. Donner la somme de l'arbre (justifier le calcul).

2. Associer à chaque terme sa lettre sur le schéma (A = flèche vers le nœud 3 ; B = flèche vers le nœud 6 ; C = flèche vers le nœud 7 ; D = encadre {6,7,4} ; E = encadre {2,9,1}) : « racine », « nœud », « feuille », « SAG », « SAD ».

3. Un seul des parcours suivants est un parcours en largeur d'abord de l'arbre : lequel ? A. 7-6-4-3-9-2-1 B. 3-6-7-4-2-9-1 C. 3-6-2-7-4-9-1 D. 7-4-6-9-1-2-3

4. Écrire somme(liste), qui renvoie la somme des éléments d'une liste de nombres.

5. La fonction parcourir, décrite en langage naturel, enfile la racine dans une file, puis répète : défiler un sous-arbre S, ajouter sa valeur à une liste L, enfiler chaque sous-arbre non vide de S. Quel type de parcours obtient-on ?

Partie B — Diviser pour régner.

6. Le principe « diviser pour régner » signifie : A. diviser une fonction en deux fonctions plus petites. B. utiliser plusieurs modules. C. séparer les informations selon leur type. D. diviser un problème en deux problèmes plus petits et indépendants. Laquelle est correcte ?

7. En décomposant l'arbre en racine + SAG + SAD, donner l'égalité liant la somme de l'arbre à celle de ses sous-arbres et à la valeur de la racine.

8. Écrire calcul_somme(arbre), fonction récursive, à l'aide de est_vide(arbre), valeur_racine(arbre), arbre_gauche(arbre), arbre_droit(arbre).

Exercice 5 — Programmation orientée objet : LaserGame

class Joueur:
    def __init__(self, pseudo, identifiant, equipe):
        self.pseudo = pseudo
        self.equipe = equipe
        self.id = identifiant
        self.nb_de_tirs_emis = 0
        self.liste_id_tirs_recus = []
        self.est_actif = True
 
    def tire(self):
        if self.est_actif == True:
            self.nb_de_tirs_emis = self.nb_de_tirs_emis + 1
 
    def est_determine(self):
        return self.nb_de_tirs_emis > 500
 
    def subit_un_tir(self, id_recu):
        if self.est_actif == True:
            self.est_actif = False
            self.liste_id_tirs_recus.append(id_recu)

1. Parmi ces instructions, laquelle déclare correctement joueur1 (pseudo "Sniper", identifiant 319, équipe "A") ?

1. joueur1 = ["Sniper", 319, "A"]
2. joueur1 = new Joueur["Sniper", 319, "A"]
3. joueur1 = Joueur("Sniper", 319, "A")
4. joueur1 = Joueur{"pseudo":"Sniper", "id":319, "equipe":"A"}

2.a. Écrire redevenir_actif, qui réactive le joueur uniquement s'il était désactivé. 2.b. Écrire nb_de_tirs_recus, qui renvoie le nombre de tirs reçus (via liste_id_tirs_recus).

3. Classe Base (attributs equipe, liste_des_id_de_l_equipe, score initial 1000 ; méthodes est_un_id_allie, incremente_score, collecte_information) :

def collecte_information(self, participant):
    if participant.equipe == self.equipe:   # test 1
        for id in participant.liste_id_tirs_recus:
            if self.est_un_id_allie(id):   # test 2
                self.incremente_score(-20)
            else:
                self.incremente_score(-10)

3.a. Quel test (1 ou 2) vérifie qu'un participant égaré n'a pas rejoint par erreur la base adverse ? 3.b. Comment varie le score de la base quand un joueur de cette équipe est touché par un coéquipier ?

4. On veut un bonus de 40 points par joueur particulièrement déterminé (est_determine()). Compléter la fin de collecte_information (2 lignes) avec les méthodes des classes Joueur et Base.