Terminale NSI
Evaluation n°1
Nom : Prénom : Note :
Exercice n° 1 -- 4 pts

On considère la fonction ci-contre.

  1. Quel est le résultat renvoyé par mystere(5) ?
  2. Décrire en français ce que fait cette fonction.
  3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

    Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest


     

Exercice n° 2 -- 2 pts

On souhaite écrire une fonction récursive compter(v,liste,i=0) qui compte le nombre d'occurrences de v dans la liste liste entre la case d'indice i et la dernière case de la liste.


     

  1. Donner la relation entre compter(s,liste,i) et compter(s,liste,i+1) et liste[i] si i est strictement inférieur à la longueur de la liste liste.

  2. Ecrire le code de la fonction récursive compter().

    Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

  3. Proposer le code d'une version non récursive de cette fonction compter().

    Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

Exercice n° 3 -- 2 pts

On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.


         

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    Dans une administration, on souhaite insérer dans une structure de données les doléances reçues afin de les traiter selon leur ordre d'arrivée. On aura alors plutôt intérêt à les enregistrer dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Pour un logiciel, on doit enregistrer la liste les actions dans une structure de données de sorte à voir la dernière action en priorité. On enregistrera donc les actions dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une pile contenant n éléments avec un tableau P[0..n] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la prochaine case vide.
    • Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la pile ou bien sont vides. La dernière case non vide du tableau est le sommet de la pile.

    Exemple :

    1. Ecrire le code Python de la fonction Python DEPILER(P) qui dépile un élément de la pile P.
    2. Ecrire le code Python de la fonction Python EST_VIDE(P) qui retourne True si la pile P est vide et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • Son nombre de noeuds
      • Sa racine
      • Son nombre de feuilles
      • La liste de ses branches
      • La liste de ses noeuds internes

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la hauteur de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [27, 53, 65, 37, 41, 60, 84, 56, 49, 15, 51].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(4) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(v,liste,i=0) qui compte le nombre d'occurrences de v dans la liste liste entre la case d'indice i et la dernière case de la liste.

    
         

    1. Donner la relation entre compter(s,liste,i) et compter(s,liste,i+1) et liste[i] si i est strictement inférieur à la longueur de la liste liste.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    Dans une administration, on souhaite insérer dans une structure de données les doléances reçues afin de les traiter selon leur ordre d'arrivée. On aura alors plutôt intérêt à les enregistrer dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Dans une association, on souhaite enregistrer une liste d'informations pour cahque adhérent : taille, poids, etc ... La meilleure structure de données pour cela est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une file contenant n éléments avec un tableau F[0..n+2] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la tête de la file.
    • La deuxième case du tableau (d'indice 1) contient l'indice de la queue de la file,c'est-à-dire la prochaine case disponible pour la queue.
    • La troisième case du tableau (d'indice 2) contient le nombre d'éléments de la file.
    • Les cases suivantes du tableau (d'indices 3 à n+2) contiennent les éléments de la file ou sont vides.

    Remarques :

    • A chaque fois qu'on enfile un élément, on augmente la taille de la file d'une unité ainsi que l'indice de la queue.
    • A chaque fois qu'on défile un élément, on diminue la taille de la file d'une unité et on augmente l'indice de la tête d'une unité.
    • Quand les indices de tête ou de queue dépasse la longueur du tableau, ils repartent au début du tableau (indice 3). Il s'agit d'une gestion circulaire d'un tableau.

    Exemple :

    1. Ecrire le code Python de la fonction Python DEFILER(F) qui défile un élément de la file F.
    2. Ecrire le code Python de la fonction Python EST_VIDE(F) qui retourne True si la file F est vide et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • Sa racine
      • Ses feuilles
      • Ses branches
      • La liste de ses noeuds internes

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la taille de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [38, 17, 14, 54, 57, 73, 97, 19, 63, 2, 42].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(2,5) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(v,liste,i=0) qui compte le nombre d'occurrences de v dans la liste liste entre la case d'indice i et la dernière case de la liste.

    
         

    1. Donner la relation entre compter(s,liste,i) et compter(s,liste,i+1) et liste[i] si i est strictement inférieur à la longueur de la liste liste.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    On souhaite insérer dans une structure de données les différentes hauteur d'un arbre au fil des années sans y insérer les années. La structure de données la plus adaptée en Python est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Pour un logiciel, on doit enregistrer la liste les actions dans une structure de données de sorte à voir la dernière action en priorité. On enregistrera donc les actions dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une pile contenant n éléments avec un tableau P[0..n] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la prochaine case vide.
    • Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la pile ou bien sont vides. La dernière case non vide du tableau est le sommet de la pile.

    Exemple :

    1. Ecrire le code Python de la fonction Python EMPILER(P,x) qui empile un élément x dans la pile P.
    2. Ecrire le code Python de la fonction Python EST_PLEINE(P) qui retourne True si la pile P est pleine et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • Son nombre de noeuds
      • Sa racine
      • Son nombre de feuilles
      • Son nombre de branches
      • La liste de ses noeuds internes

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la taille de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [45, 96, 44, 18, 28, 53, 21, 6, 88, 87, 64].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(2,5) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(c,chaine,i=0) qui compte le nombre d'occurrences du caractère c dans la chaîne de caractères chaine entre la position d'indice i et la fin de la chaîne de caractères.

    1. Donner la relation entre compter(c,chaine,i) et compter(c,chaine,i+1) et chaine[i] si i est strictement inférieur à la longueur de la chaîne de caractères chaine.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    On souhaite insérer dans une structure de données les différentes hauteur d'un arbre au fil des années sans y insérer les années. La structure de données la plus adaptée en Python est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Dans une association, on souhaite enregistrer une liste d'informations pour cahque adhérent : taille, poids, etc ... La meilleure structure de données pour cela est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une file contenant n éléments avec un tableau F[0..n+2] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la tête de la file.
    • La deuxième case du tableau (d'indice 1) contient l'indice de la queue de la file,c'est-à-dire la prochaine case disponible pour la queue.
    • La troisième case du tableau (d'indice 2) contient le nombre d'éléments de la file.
    • Les cases suivantes du tableau (d'indices 3 à n+2) contiennent les éléments de la file ou sont vides.

    Remarques :

    • A chaque fois qu'on enfile un élément, on augmente la taille de la file d'une unité ainsi que l'indice de la queue.
    • A chaque fois qu'on défile un élément, on diminue la taille de la file d'une unité et on augmente l'indice de la tête d'une unité.
    • Quand les indices de tête ou de queue dépasse la longueur du tableau, ils repartent au début du tableau (indice 3). Il s'agit d'une gestion circulaire d'un tableau.

    Exemple :

    1. Ecrire le code Python de la fonction Python ENFILER(F,x) qui enfile un élément x dans la file F.
    2. Ecrire le code Python de la fonction Python EST_PLEINE(F) qui retourne True si la file F est pleine et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • Son nombre de noeuds
      • Sa racine
      • Son nombre de feuilles
      • Son nombre de branches
      • La liste de ses noeuds internes

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la taille de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [45, 96, 44, 18, 28, 53, 21, 6, 88, 87, 64].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(2,5) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(c,chaine,i=0) qui compte le nombre d'occurrences du caractère c dans la chaîne de caractères chaine entre la position d'indice i et la fin de la chaîne de caractères.

    1. Donner la relation entre compter(c,chaine,i) et compter(c,chaine,i+1) et chaine[i] si i est strictement inférieur à la longueur de la chaîne de caractères chaine.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    Dans une administration, on souhaite insérer dans une structure de données les doléances reçues afin de les traiter selon leur ordre d'arrivée. On aura alors plutôt intérêt à les enregistrer dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Pour un logiciel, on doit enregistrer la liste les actions dans une structure de données de sorte à voir la dernière action en priorité. On enregistrera donc les actions dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une file contenant n éléments avec un tableau F[0..n+2] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la tête de la file.
    • La deuxième case du tableau (d'indice 1) contient l'indice de la queue de la file,c'est-à-dire la prochaine case disponible pour la queue.
    • La troisième case du tableau (d'indice 2) contient le nombre d'éléments de la file.
    • Les cases suivantes du tableau (d'indices 3 à n+2) contiennent les éléments de la file ou sont vides.

    Remarques :

    • A chaque fois qu'on enfile un élément, on augmente la taille de la file d'une unité ainsi que l'indice de la queue.
    • A chaque fois qu'on défile un élément, on diminue la taille de la file d'une unité et on augmente l'indice de la tête d'une unité.
    • Quand les indices de tête ou de queue dépasse la longueur du tableau, ils repartent au début du tableau (indice 3). Il s'agit d'une gestion circulaire d'un tableau.

    Exemple :

    1. Ecrire le code Python de la fonction Python DEFILER(F) qui défile un élément de la file F.
    2. Ecrire le code Python de la fonction Python EST_VIDE(F) qui retourne True si la file F est vide et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • La liste de ses feuilles
      • Son nombre de branches
      • La liste de ses noeuds internes
      • Son arité

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la taille de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [45, 96, 44, 18, 28, 53, 21, 6, 88, 87, 64].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(2,5) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(c,chaine,i=0) qui compte le nombre d'occurrences du caractère c dans la chaîne de caractères chaine entre la position d'indice i et la fin de la chaîne de caractères.

    1. Donner la relation entre compter(c,chaine,i) et compter(c,chaine,i+1) et chaine[i] si i est strictement inférieur à la longueur de la chaîne de caractères chaine.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    Dans une administration, on souhaite insérer dans une structure de données les doléances reçues afin de les traiter selon leur ordre d'arrivée. On aura alors plutôt intérêt à les enregistrer dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Dans une association, on souhaite enregistrer une liste d'informations pour cahque adhérent : taille, poids, etc ... La meilleure structure de données pour cela est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une pile contenant n éléments avec un tableau P[0..n] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la prochaine case vide.
    • Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la pile ou bien sont vides. La dernière case non vide du tableau est le sommet de la pile.

    Exemple :

    1. Ecrire le code Python de la fonction Python EMPILER(P,x) qui empile un élément x dans la pile P.
    2. Ecrire le code Python de la fonction Python EST_PLEINE(P) qui retourne True si la pile P est pleine et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • Son nombre de noeuds
      • Sa racine
      • Son nombre de feuilles
      • Son nombre de branches
      • La liste de ses noeuds internes

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la hauteur de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [27, 53, 65, 37, 41, 60, 84, 56, 49, 15, 51].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(2,5) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(c,chaine,i=0) qui compte le nombre d'occurrences du caractère c dans la chaîne de caractères chaine entre la position d'indice i et la fin de la chaîne de caractères.

    1. Donner la relation entre compter(c,chaine,i) et compter(c,chaine,i+1) et chaine[i] si i est strictement inférieur à la longueur de la chaîne de caractères chaine.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    Dans une administration, on souhaite insérer dans une structure de données les doléances reçues afin de les traiter selon leur ordre d'arrivée. On aura alors plutôt intérêt à les enregistrer dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Dans une association, on souhaite enregistrer une liste d'informations pour cahque adhérent : taille, poids, etc ... La meilleure structure de données pour cela est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une file contenant n éléments avec un tableau F[0..n+2] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la tête de la file.
    • La deuxième case du tableau (d'indice 1) contient l'indice de la queue de la file,c'est-à-dire la prochaine case disponible pour la queue.
    • La troisième case du tableau (d'indice 2) contient le nombre d'éléments de la file.
    • Les cases suivantes du tableau (d'indices 3 à n+2) contiennent les éléments de la file ou sont vides.

    Remarques :

    • A chaque fois qu'on enfile un élément, on augmente la taille de la file d'une unité ainsi que l'indice de la queue.
    • A chaque fois qu'on défile un élément, on diminue la taille de la file d'une unité et on augmente l'indice de la tête d'une unité.
    • Quand les indices de tête ou de queue dépasse la longueur du tableau, ils repartent au début du tableau (indice 3). Il s'agit d'une gestion circulaire d'un tableau.

    Exemple :

    1. Ecrire le code Python de la fonction Python DEFILER(F) qui défile un élément de la file F.
    2. Ecrire le code Python de la fonction Python EST_VIDE(F) qui retourne True si la file F est vide et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • Son nombre de noeuds
      • Sa racine
      • Son nombre de feuilles
      • La liste de ses branches
      • La liste de ses noeuds internes

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la hauteur de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [27, 53, 65, 37, 41, 60, 84, 56, 49, 15, 51].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(5) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(c,chaine,i=0) qui compte le nombre d'occurrences du caractère c dans la chaîne de caractères chaine entre la position d'indice i et la fin de la chaîne de caractères.

    1. Donner la relation entre compter(c,chaine,i) et compter(c,chaine,i+1) et chaine[i] si i est strictement inférieur à la longueur de la chaîne de caractères chaine.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    On souhaite insérer dans une structure de données les différentes hauteur d'un arbre au fil des années sans y insérer les années. La structure de données la plus adaptée en Python est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Dans une association, on souhaite enregistrer une liste d'informations pour cahque adhérent : taille, poids, etc ... La meilleure structure de données pour cela est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une pile contenant n éléments avec un tableau P[0..n] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la prochaine case vide.
    • Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la pile ou bien sont vides. La dernière case non vide du tableau est le sommet de la pile.

    Exemple :

    1. Ecrire le code Python de la fonction Python DEPILER(P) qui dépile un élément de la pile P.
    2. Ecrire le code Python de la fonction Python EST_VIDE(P) qui retourne True si la pile P est vide et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • Sa racine
      • Ses feuilles
      • Ses branches
      • La liste de ses noeuds internes

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la hauteur de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [27, 53, 65, 37, 41, 60, 84, 56, 49, 15, 51].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(2,5) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(v,liste,i=0) qui compte le nombre d'occurrences de v dans la liste liste entre la case d'indice i et la dernière case de la liste.

    
         

    1. Donner la relation entre compter(s,liste,i) et compter(s,liste,i+1) et liste[i] si i est strictement inférieur à la longueur de la liste liste.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    Dans une administration, on souhaite insérer dans une structure de données les doléances reçues afin de les traiter selon leur ordre d'arrivée. On aura alors plutôt intérêt à les enregistrer dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Dans une association, on souhaite enregistrer une liste d'informations pour cahque adhérent : taille, poids, etc ... La meilleure structure de données pour cela est :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une file contenant n éléments avec un tableau F[0..n+2] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la tête de la file.
    • La deuxième case du tableau (d'indice 1) contient l'indice de la queue de la file,c'est-à-dire la prochaine case disponible pour la queue.
    • La troisième case du tableau (d'indice 2) contient le nombre d'éléments de la file.
    • Les cases suivantes du tableau (d'indices 3 à n+2) contiennent les éléments de la file ou sont vides.

    Remarques :

    • A chaque fois qu'on enfile un élément, on augmente la taille de la file d'une unité ainsi que l'indice de la queue.
    • A chaque fois qu'on défile un élément, on diminue la taille de la file d'une unité et on augmente l'indice de la tête d'une unité.
    • Quand les indices de tête ou de queue dépasse la longueur du tableau, ils repartent au début du tableau (indice 3). Il s'agit d'une gestion circulaire d'un tableau.

    Exemple :

    1. Ecrire le code Python de la fonction Python DEFILER(F) qui défile un élément de la file F.
    2. Ecrire le code Python de la fonction Python EST_VIDE(F) qui retourne True si la file F est vide et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • La liste de ses feuilles
      • Son nombre de branches
      • La liste de ses noeuds internes
      • Son arité

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la taille de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [38, 17, 14, 54, 57, 73, 97, 19, 63, 2, 42].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.

    Terminale NSI
    Evaluation n°1
    Nom : Prénom : Note :
    Exercice n° 1 -- 4 pts

    On considère la fonction ci-contre.

    1. Quel est le résultat renvoyé par mystere(5) ?
    2. Décrire en français ce que fait cette fonction.
    3. Ecrire le code d'une version itérative de cette fonction en utilisant une boucle.

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest

    
         

    Exercice n° 2 -- 2 pts

    On souhaite écrire une fonction récursive compter(v,liste,i=0) qui compte le nombre d'occurrences de v dans la liste liste entre la case d'indice i et la dernière case de la liste.

    
         

    1. Donner la relation entre compter(s,liste,i) et compter(s,liste,i+1) et liste[i] si i est strictement inférieur à la longueur de la liste liste.

    2. Ecrire le code de la fonction récursive compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    3. Proposer le code d'une version non récursive de cette fonction compter().

      Ne pas oublier de commenter la fonction avec les docstring et de prévoir des tests avec doctest.

    Exercice n° 3 -- 2 pts

    On dispose de plusieurs objets possédant chacun un poids et une valeur, et d’un sac à dos acceptant un poids maximum. Quels objets faut-il mettre dans le sac à dos de manière à maximiser la valeur totale sans dépasser le poids maximum autorisé ? Voici une fonction Python itérative qui résout ce problème à l'aide algorithme glouton.

    
             

  • Proposer une version récursive de cette fonction nommé sac_a_dos_glouton_recursif()
  • Exercice n° 4 -- 2 pts

    A l'aide du module PythonTurtle, on souhaite dessiner la fractale suivante :

    A chaque étape la longueur du segment est divisée par 2 et chaque nouveau segment est dessiné à partir du milieu des segments de l'étape précédente.

    1. Compléter le code suivant afin de réaliser le dessin de cette fractale.

                                   
       import turtle as t
       K = 0.5
       def fractale(x,y,l,etapes,etape=0):
           """
           Dessine la fractale à l'étape étape : 2 segments de longueur l
           :param x: l'abscisse x
           :param y: l'abscisse y
           :param l: la longueur des segments à dessiner
           :param etapes: le nombre d'étapes pour la fractalisation
           :param etape: l'étape courante un entier
           :return:
           """
           segment(x,y,x+l,y)
           segment(x, y, x, y + l)
           if etape < etapes:
               fractale(.....,y,...,etapes,etape + 1)
               fractale(x, .....,...., etapes, .......)
       
       def segment(x1,y1,x2,y2):
           """
           Dessine un segment d'extrémités les points de coordonnées (x1,y1) et (x2,y2)
           :param x1: l'abscisse de l'extrémité du premier point du segment
           :param y1: l'ordonnée de l'extrémité du premier point du segment
           :param x2: l'abscisse de l'extrémité du deuxième point du segment
           :param y2: l'ordonnée de l'extrémité du premier point du segment
           :return:
           """
           t.penup()
           t.goto(x1,y1)
           t.pendown()
           t.goto(x2, y2)
       
       
       t.speed(1000)
       #Appel de la fonction qui dessine la fractale jusqu'à l'étape 4
       fractale(-200,-200,200,4)
       t.done()
                                   
                               

    2. Donner le nombre de segments dessinés à l'étape n°6.

    Exercice n° 5 -- 1 pts

    Dans une administration, on souhaite insérer dans une structure de données les doléances reçues afin de les traiter selon leur ordre d'arrivée. On aura alors plutôt intérêt à les enregistrer dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 6 -- 1 pts

    Pour un logiciel, on doit enregistrer la liste les actions dans une structure de données de sorte à voir la dernière action en priorité. On enregistrera donc les actions dans :

    1. une liste;
    2. un dictionnaire;
    3. une pile;
    4. une file.

    Justifier la réponse.

    Exercice n° 7 -- 3 pts

    On peut représenter une pile contenant n éléments avec un tableau P[0..n] comme suit :

    • La première case du tableau (d'indice 0) contient l'indice de la prochaine case vide.
    • Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la pile ou bien sont vides. La dernière case non vide du tableau est le sommet de la pile.

    Exemple :

    1. Ecrire le code Python de la fonction Python DEPILER(P) qui dépile un élément de la pile P.
    2. Ecrire le code Python de la fonction Python EST_VIDE(P) qui retourne True si la pile P est vide et False sinon.

    Exercice n° 8 -- 4 pts

    On considère l'arbre suivant :

    1. Donner les caractéritiques suivantes de cet arbre :

      • Son nombre de noeuds
      • Sa racine
      • Son nombre de feuilles
      • La liste de ses branches
      • La liste de ses noeuds internes

    2. Cet arbre est-il un arbre binaire ? Justifier.
    3. Calculer (en détaillant) les mesures suivantes de cet arbre :

      • Sa taille
      • Sa hauteur
      • Sa longueur de cheminement
      • Sa longueur de cheminement externe
      • Sa longueur de cheminement interne
      • Sa profondeur moyenne
      • Sa profondeur moyenne externe
      • Sa profondeur moyenne interne

    Exercice n° 9 -- 4 pts

    Voici le tableau décrivant un arbre :

    1. Représenter graphiquement l'arbre correspondant.
    2. Quelle est la taille de cet arbre ?
    3. Cet arbre est-il binaire ? Justifier
    4. Cet arbre est-il localement complet ? Justifier
    5. Cet arbre est-il complet ? Justifier
    6. Donner l'expression numérique représentée par cet arbre et son résultat.

    Exercice n° 10 -- 2 pts

    On définit les deux méthodes suivantes pour créer un arbre de type abstrait :

    Représenter l'arbre correspondant à la suite d'instructions suivantes :

    Exercice n° 11 -- 3 pts

    On donne une liste de 11 entiers : [45, 96, 44, 18, 28, 53, 21, 6, 88, 87, 64].

    1. Construire dans l'ordre de la liste unarbre binaire de recherche associé à cette liste.

    2. L'arbre ainsi construit est-il équilibré ? Justifier.

    3. Essayer (si ce ne n'est pas déjà le cas) d'obtenir un arbre équilibré de hauteur minimale.