Index des sujets 2021

21-NSIJ1G11 : Corrigé

Année : 2021
Centre : Etranger
Jour : 1
Enoncé :

Exercice 1

programmation objet (code de César)

Exercice 2

structures de données (dictionnaires)

Exercice 3

arbres binaires de recherche

        graph TD
        N0["26.noeud00"] --> N1["3.noeud01"]
        N0 --> N2["42.noeud02"]
        N1 --> N7["1.noeud07"]
        N1 --> N3["15.noeud03"]
        N2 --> N4["29.noeud04"]
        N2 --> V1[" "]
        N3 --> N6["13.noeud06"]
        N3 --> N5["19.noeud05"]
        N4 --> V2[" "]
        N4 --> N8["32.noeud08"]
        N8 --> N10["30.noeud10"]
        N8 --> N9["37.noeud09"]
        N5 -->   V3[" "]
        N5 --> N11["25.noeud11"]
        style V1 fill:#FFFFFF, stroke:#FFFFFF
        style V2 fill:#FFFFFF, stroke:#FFFFFF
        style V3 fill:#FFFFFF, stroke:#FFFFFF
        style N11 fill:#AA2222,stroke:#333
        linkStyle 0,3,7,13 stroke:#FF0000,stroke-width:2px

1. Etapes de l'insertion du noeud 11 de valeur 25 :

   • A gauche du noeud00 car il a pour valeur 26 et \(25<26\)

   • A droite du noeud01 car il a pour valeur 3 et \(25>3\)

   • A droite du noeud03 car il a pour valeur 15 et \(25>15\)

   • A droite du noeud05 car il a pour valeur 19 et \(25>19\)

2. A gauche du noeud04, on peut stocker les valeurs strictement inférieures à 29 et supérieures ou égales à 26. C'est à dire : 26,27, et 28.

   Note

   Le sujet précise dans son introduction que :

   les valeurs du sous-arbre droit sont supérieures ou égales à valeur du noeud.

   Avec cette définition, la valeur 26 est donc possible même si elle est déjà présente dans l'arbre. Si on considère que les valeurs sont uniques seules 27 et 28 sont possibles.

3.  

   a. 26, 3, 1, 15, 13, 19, 25, 42, 29, 32, 30, 37

   b. C'est un parcours préfixé car la valeur du noeud est listé avant celle des valeurs présentes dans le sous arbre gauche et le sous arbre droit. La valeur du noeud serait listé entre ces valeurs pour un parcours infixe et après pour un parcours suffixé.

4. Afin d'afficher les valeurs par ordre croissant, on doit effectuer un parcours infixe. C'est à dire afficher la valeur du noeud entre les valeurs du sous arbre gauche et du sous arbre droit.

   Parcours2(A): 
       Parcours(A.fils_gauche)
       Afficher(A.valeur)
       Parcours(A.fils_droit)
   

Exercice 4

réseau

Exercice 5

structure de données (piles)

1.

2.

3.

def maximum(pile):
    if est_vide(pile):
        return None
    maxi = depiler(pile)
    while not est_vide(pile):
        elt = depiler(pile)
        if elt>maxi:
            maxi = elt
    return maxi

Note

• Le sujet ne précise pas le comportement à adopter si la pile est vide. Dans cette correction, on renvoie None.
• On a dépilé un premier élément à la ligne 4 de façon à initialiser le maximum.

1. a. On dépile les éléments de pile tant que pile n'est pas vide et on incrémente un compteur à chaque élément dépilé. De façon à pouvoir restituer la pile dans sont état d'origine, on empile les éléments de pile dans une pile de sauvegarde qu'on empile dans P lorsque le comptage est terminé.

   b.

   def taille(pile):
       compteur = 0
       pile_sauvegarde = creer_pile()
       while not est_vide(pile):
           compteur += 1
           elt = depiler(pile)
           empiler(pile_sauvegarde,elt)
       while not est_vide(pile_sauvegarde):
           elt = depiler(pile_sauvegarde)
           empiler(pile,elt)
       return compteur