Bac NSI — Session 2021 (centre non confirmé)

Présentation de l'épreuve

Sujet officiel du baccalauréat général, épreuve de spécialité Numérique et Sciences Informatiques, session 2021. Durée 3h30, calculatrice et dictionnaire interdits. Le sujet comporte 5 exercices indépendants notés chacun sur 4 points ; le candidat en traite 3 au choix. Le document source ne comporte, dans le texte extrait, aucun code officiel de session du type XX-NSIJxYYn : le centre d'examen exact n'est donc pas confirmé (seule la mention « session 2021 » figure en en-tête).

Exercice 1 — Arbres binaires de recherche

On considère un arbre binaire de recherche (ABR) sans doublon de clé (un arbre à un seul nœud a pour hauteur 1). Sa racine est 18 ; son fils gauche est 15, son fils droit 23. 15 a pour fils gauche 13 et fils droit val (un entier inconnu). 13 a pour unique fils (gauche) 12. 23 a pour fils gauche 19 et fils droit 32. 19 a pour unique fils (droit) 21.

1. a) Nombre de feuilles de cet arbre et leur valeur. b) Sous-arbre gauche du nœud 23. c) Hauteur et taille de l'arbre. d) Valeurs entières possibles de val pour que ce soit bien un ABR.

On suppose désormais val = 16.

2. On rappelle qu'un parcours infixe visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit ; un parcours suffixe visite le sous-arbre gauche, puis le sous-arbre droit, puis le nœud. a) Valeurs affichées par un parcours infixe. b) Valeurs affichées par un parcours suffixe.

3. Classe Python :

class Noeud():
    def __init__(self, v):
        self.ag = None
        self.ad = None
        self.v = v
 
    def insere(self, v):
        n = self
        est_insere = False
        while not est_insere:
            if v == n.v:
                est_insere = True
            elif v < n.v:
                if n.ag != None:
                    n = n.ag
                else:
                    n.ag = Noeud(v)
                    est_insere = True
            else:
                if n.ad != None:
                    n = n.ad
                else:
                    n.ad = Noeud(v)
                    est_insere = True
 
    def insere_tout(self, vals):
        for v in vals:
            self.insere(v)

a) Représenter l'arbre obtenu par racine = Noeud(18) puis racine.insere_tout([12, 13, 15, 16, 19, 21, 32, 23]). b) Écrire les deux instructions construisant l'arbre décrit plus haut (avec val = 16). c) Sur cet arbre (celui décrit plus haut), déterminer l'ordre d'exécution des blocs suivants lors de l'appel racine.insere(19) : Bloc 1 (le if v == n.v), Bloc 2 (la création d'un fils gauche), Bloc 3 (la création d'un fils droit).

4. Écrire une méthode recherche(self, v) renvoyant True si v est une étiquette de l'arbre, False sinon.

Exercice 2 — Processus, ordonnancement et opérateurs booléens

Partie A (QCM, une seule réponse exacte, aucune justification demandée, aucun point retiré en cas d'erreur).

1. Quelle commande affiche les processus en cours d'exécution ? a) dir b) ps c) man d) ls
2. Quelle abréviation désigne l'identifiant d'un processus sous UNIX ? a) PIX b) SIG c) PID d) SID
3. Comment s'appelle la gestion du partage du processeur entre processus ? a) l'interblocage b) l'ordonnancement c) la planification d) la priorisation
4. Quelle commande interrompt un processus sous UNIX ? a) stop b) interrupt c) end d) kill

Partie B.

1. Un processeur exécute, à chaque cycle, le processus de plus petite valeur de priorité disponible (préemption possible). Processus P1 (durée 3, arrivée 3, priorité 1), P2 (durée 3, arrivée 2, priorité 2), P3 (durée 4, arrivée 0, priorité 3). Reproduire un chronogramme indiquant le processus exécuté à chaque cycle de 0 à 9.

2. On suppose que ces processus utilisent des ressources R1, R2, R3. Parmi les trois scénarios suivants, lequel provoque un interblocage ? Justifier.

   • Scénario 1 : P1 acquiert R1 ; P2 acquiert R2 ; P3 attend R1 ; P2 libère R2 ; P2 attend R1 ; P1 libère R1.
   • Scénario 2 : P1 acquiert R1 ; P2 acquiert R3 ; P3 acquiert R2 ; P1 attend R2 ; P2 libère R3 ; P3 attend R1.
   • Scénario 3 : P1 acquiert R1 ; P2 acquiert R2 ; P3 attend R2 ; P1 attend R2 ; P2 libère R2 ; P3 acquiert R2.

Partie C. On chiffre un message par la méthode du masque jetable : chaque caractère est converti en binaire (Unicode) puis combiné bit à bit par XOR avec une clé. Table de vérité du XOR : (0,0)->0, (0,1)->1, (1,0)->1, (1,1)->0.

1. Avant chiffrement, on a m = 0b 0110 0011 0100 0110 (deux caractères de 8 bits chacun). a) À l'aide de la table hexadécimale->caractère (ASCII, ex. 4A -> 'J'), identifier ces deux caractères. b) Avec la clé k = 0b 1110 1110 1111 0000, donner l'écriture binaire du message chiffré (XOR bit à bit de m et k).

2. a) Dresser la table de vérité de (a XOR b) XOR b. b) Bob connaît la clé utilisée par Alice : quelle opération doit-il effectuer pour déchiffrer le message ?

Exercice 3 — Bases de données et SQL (gestion d'une gare)

Schéma relationnel : Train(numT, provenance, destination, horaireArrivee, horaireDepart), Reservation(numR, nomClient, prenomClient, prix, #numT) (numT clé étrangère vers Train.numT). horaireArrivee/horaireDepart sont de type TIME (format "hh:mm").

1. Quel nom générique donne-t-on aux logiciels assurant la persistance des données, l'efficacité des requêtes et la sécurisation des accès ?

2. a) DELETE FROM Train WHERE numT = 1241; puis DELETE FROM Reservation WHERE numT = 1241; : pourquoi la première instruction renvoie-t-elle une erreur si des réservations existent pour ce train ? b) Citer un cas où l'insertion d'un enregistrement dans Reservation est impossible.

3. Écrire les requêtes SQL suivantes : a) tous les numéros de train dont la destination est « Lyon » ; b) ajouter une réservation n°1307 de 33 € pour M. Alan Turing dans le train n°654 ; c) mettre à jour l'horaire d'arrivée du train n°7869 à 08h11.

4. Que détermine SELECT COUNT(*) FROM Reservation WHERE nomClient = "Hopper" AND prenomClient = "Grace"; ?

5. Écrire la requête renvoyant les destinations et les prix des réservations de Grace Hopper.

Exercice 4 — Tri fusion (diviser pour régner)

1. a) Ordre de grandeur du coût (en comparaisons) du tri fusion pour une liste de longueur n. b) Citer un autre algorithme de tri, donner l'ordre de grandeur de son coût, et le comparer à celui du tri fusion (sans justification).

L'algorithme utilise moitie_gauche(L) (éléments d'indice < len(L)//2) et moitie_droite(L) (indice >= len(L)//2), ainsi que fusion(L1, L2) qui fusionne deux listes triées en une liste triée. Code partiel :

def tri_fusion(L):
    n = len(L)
    if n <= 1:
        return L
    print(L)
    mg = moitie_gauche(L)
    md = moitie_droite(L)
    L1 = tri_fusion(mg)
    L2 = tri_fusion(md)
    return fusion(L1, L2)

2. Donner la liste des affichages produits par tri_fusion([7, 4, 2, 1, 8, 5, 6, 3]).

3. Écrire la fonction moitie_droite.

4. Version incomplète de fusion :

def fusion(L1, L2):
    L = []
    n1 = len(L1)
    n2 = len(L2)
    i1 = 0
    i2 = 0
    while i1 < n1 or i2 < n2:
        if i1 >= n1:
            L.append(L2[i2])
            i2 = i2 + 1
        elif i2 >= n2:
            L.append(L1[i1])
            i1 = i1 + 1
        else:
            e1 = L1[i1]
            e2 = L2[i2]
            # lignes manquantes : ajouter le plus petit de e1/e2 a L
            # et decaler l'indice correspondant
    return L

Écrire les instructions manquantes.

Exercice 5 — Réseaux et protocoles de routage

Réseau à 6 routeurs R1 à R6 ; le réseau local L1 est relié à R1, le réseau local L2 à R6. Une adresse IP X1.X2.X3.X4/n a ses n premiers bits identifiant le réseau ; l'adresse dont tous les bits « hôte » sont à 0 est l'adresse du réseau.

Liaisons (avec leur réseau) : R1-R3 (112.44.65.0/24), R1-R2 (86.154.10.0/24), R3-R2 (176.139.8.0/24), R3-R4 (62.34.2.0/24), R2-R4 (212.194.171.0/24), R4-R5 (87.3.5.0/24), R2-R5 (10.94.75.0/24), R4-R6 (94.23.122.0/24), R2-R6 (37.49.236.0/24), R5-R6 (218.32.15.0/24), R1-L1 (192.168.1.0/24), R6-L2 (54.37.122.0/24).

Extraits de tables de routage (route vers 54.37.122.0/24 = réseau L2) :

1. Un paquet part de L1 vers L2. a) D'après la table de R1, vers quel routeur (R2 ou R3) l'envoie-t-il ? Justifier. b) Nommer les routeurs traversés du réseau L1 au réseau L2.

2. La liaison R1-R2 est rompue. a) Avec RIP (distance = nombre de sauts), donner l'un des deux chemins possibles de L1 vers L2. b) Quelle(s) ligne(s) du tableau ci-dessus est (sont) alors modifiée(s) ?

3. La liaison R1-R2 est rétablie. On passe au protocole OSPF (coût minimal). Coûts donnés : R1-R2:100, R1-R3:100, R2-R3:?, R2-R4:1, R2-R5:10, R2-R6:10, R3-R4:10, R4-R5:1, R4-R6:10, R5-R6:1. a) Le coût C d'une liaison vaut 10^9/BP (BP en bit/s). La bande passante de R2-R3 est 10 Mbps : calculer son coût. b) Déterminer le chemin de L1 à L2 selon OSPF. c) Indiquer pour quel(s) routeur(s) l'extrait de la table de routage vers L2 est modifié par rapport aux tables RIP initiales.