Domaine : Récursivité 1 - Question n° 1

On considère la fonction ci-contre.

  1. Quel est le résultat renvoyé par mystere(5) ?

    mystere(5) renvoie 5 + 4 + 3 + 2 + 1 + 0 = 15.

  2. Décrire en français ce que fait cette fonction.

    Cette fonction renvoie la somme des entiers de 1 à n (n étant le paramètre d'entrée de la 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


     

Domaine : Récursivité 1 - Question n° 2

On considère la fonction ci-contre.

  1. Quel est le résultat renvoyé par mystere(4) ?

    mystere(4) renvoie 4 x 3 x 2 x 1 = 24.

  2. Décrire en français ce que fait cette fonction.

    Cette fonction renvoie le produit des entiers de 1 à n (n étant le paramètre d'entrée de la fonction).

    Il s'agit de la fonction mathématique nommée factorielle : n!

  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


     

Domaine : Récursivité 1 - Question n° 3

On considère la fonction ci-contre.

  1. Quel est le résultat renvoyé par mystere(2,5) ?

    mystere(2,5) renvoie 1 x 2 x 2 x 2 x 2 x 2 = 25 = 32.

  2. Décrire en français ce que fait cette fonction.

    Cette fonction renvoie le nombre xn (x puissance n).

  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.


     

Domaine : Récursivité 2 - Question n° 4

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(v,liste,i) et compter(v,liste,i+1) et liste[i] si i est strictement inférieur à la longueur de la liste liste.

                 
                   si liste[i] == v alors
                     compter(v,liste,i+1) = compter(v, liste,i) + 1
                   sinon
                     compter(v,liste,i+1) = compter(v, liste,i)
                   finSi
                 
               

  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.

    
         


     

Domaine : Récursivité 2 - Question n° 5

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.              
                   si chaine[i] == c alors
                     compter(c,chaine,i+1) = compter(c, chaine,i) + 1
                   sinon
                     compter(c,chaine,i+1) = compter(c, chaine,i)
                   finSi
                 
               

    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.

    
         


     

Domaine : Récursivité 5 - Question n° 6

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ée sac_a_dos_glouton_recursif()


         

Domaine : Récursivité 6 - Question n° 7

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(x+K*l,y,l/2,etapes,etape+1)
             fractale(x, y+K*l,l/2, etapes, etape + 1)
     
     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.

    Le nombre de segments dessinés à l'étape n°6 est 26+1 = 128.

Domaine : Structures linéaires et dictionnaires 1 - Question n° 8

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.

Quand on observe l'évolution d'une quantité numérique, ce n'est pas en général pour sortir le premier ou le dernier élément en premier, donc pile et file sont à exclure. De plus, il n'y a pas d'association donc un dictionnaire ne convient pas. Seule la liste convient pour ce problème.

Domaine : Structures linéaires et dictionnaires 1 - Question n° 9

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.

On enregistre les doléances selon le principe : "première arrivée, première traitée" (First In, First Out : FIFO) ce qui correspond à une file.

Domaine : Structures linéaires et dictionnaires 2 - Question n° 10

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.

Il s'agit ici d'enregistrer des associations, c'est-à-dire des éléments qui sont rattachés à d'autres (adhérents -> informations) donc le dictionnaire est le plus adapté. Ici, les clés seront les adhérents et les valeurs seront les informations.

Domaine : Structures linéaires et dictionnaires 2 - Question n° 11

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.

Il s'agit d'enregistrer les actions selon le principe "dernière action faire, première action affichée" (Last In, First Out : LIFO, ce qui correspond à une pile.

Domaine : Structures linéaires et dictionnaires 4 - Question n° 12

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

Remarques :

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.

    
                             

Domaine : Structures linéaires et dictionnaires 4 - Question n° 13

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

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.

    
                         

Domaine : Structures linéaires et dictionnaires 4 - Question n° 14

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

Remarques :

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.

    
                             

Domaine : Structures linéaires et dictionnaires 4 - Question n° 15

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

Exemple :

  1. Ecrire le code Python de la fonction Python DEPILER(P,x) 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.

    
                         

Domaine : Arbres 1 - Question n° 16

On considère l'arbre suivant :

    Donner les caractéritiques suivantes de cet arbre :

    • Sa racine

      La racine de cet arbre est le noeud A.

    • La liste de ses feuilles.

      Les feuilles de cet arbre sont les noeuds suivants : D, G, H et I

    • Son nombre de branches

      Cet arbre possède 4 branches : A-B-D; A-C-E-G; A-C-E-H et A-C-F-I

    • La liste de ses noeuds internes

      Les noeuds internes de cet arbre sont : B, C; E et F.

    • Son arité

      L'arité d'un arbre est le nombre maximal d'enfants qu'un noeud peut avoir. L'arité de cet arbre est 2.

  1. Cet arbre est-il un arbre binaire ? Justifier.

    Cet arbre est un arbre binaire car chaque noeud possède au plus 2 enfants (son arité est inférieure ou égale à 2).

  2. Calculer (en détaillant) les mesures suivantes de cet arbre :

    • Sa taille

      La taille d'un arbre est le nombre de ses noeuds. La taille de cet arbre est 9.

    • Sa hauteur

      La hauteur d'un arbre est le nombre de noeuds de la branche la plus longue - 1. La hauteur de cet arbre est : 3 (3 branches de même longueur : A-C-E-G; A-C-E-H; A-C-F-I)

    • Sa longueur de cheminement

      La longueur de cheminement d'un arbre est égale à la somme des hauteurs de ses noeuds.

      Pour cet arbre :

      • H(A) = 0
      • H(B) = H(C) = 1
      • H(D) = H(E) = H(F) = 2
      • H(G) = H(H) = H(I) = 3

      Donc la longueur de cheminement de cet arbre est : $LC = 0 \times 1 + 1 \times 2 + 2 \times 3 + 3 \times 3 = 0 + 2 + 6 + 9 = 17$

    • Sa longueur de cheminement externe

      La longueur de cheminement externe d'un arbre est égale à la somme des hauteurs de ses feuilles.

      La longueur de cheminement externe de cet arbre est : $LCE = H(D) + H(G) + H(H) + H(I) = 2 + 3 + 3 + 3 = 11$.

    • Sa longueur de cheminement interne

      La longueur de cheminement interne est LCI = LC - LCE = 17 - 11 = 6.

    • Sa profondeur moyenne

      La profondeur moyenne d'un arbre est égale à la longueur du cheminement divisée par sa taille.

      La profondeur moyenne de cet arbre est : $PM = \frac{LC}{T} = \frac{17}{9}$

    • Sa profondeur moyenne externe

      La profondeur moyenne externe d'un arbre est égale à la longueur du cheminement externe divisée par le nombre de ses feuilles.

      La profondeur moyenne externe de cet arbre est : $PME = \frac{LCE}{NF} = \frac{11}{4}$

    • Sa profondeur moyenne interne

      La profondeur moyenne interne de cet arbre est : $PMI = \frac{LCI}{T-NF} = \frac{6}{9-4} = \frac{6}{5}$

Domaine : Arbres 1 - Question n° 17

On considère l'arbre suivant :

    Donner les caractéritiques suivantes de cet arbre :

    • Sa racine

      La racine de cet arbre est le noeud A.

    • Son nombre de feuilles
    • Cet arbre possède 5 feuilles : E, F, G, I et J.

    • La liste de ses branches

      Cet arbre possède 5 branches : A-B-E; A-C-F; A-C-G; A-D-H-I et A-D-H-J

    • La liste de ses noeuds internes

      Les noeuds internes de cet arbre sont : B, C; D et H.

    • Son arité

      L'arité d'un arbre est le nombre maximal d'enfants qu'un noeud peut avoir. L'arité de cet arbre est 3.

  1. Cet arbre est-il un arbre binaire ? Justifier.

    Cet arbre n'est pas un arbre binaire car sa racine A possède plus de 2 fils (son arité est strictement supérieure à 2).

  2. Calculer (en détaillant) les mesures suivantes de cet arbre :

    • Sa taille

      La taille d'un arbre est le nombre de ses noeuds. La taille de cet arbre est 10.

    • Sa hauteur

      La hauteur d'un arbre est le nombre de noeuds de la branche la plus longue - 1. La hauteur de cet arbre est : 3 (2 branches de même longueur : A-D-H-I; A-D-H-J)

    • Sa longueur de cheminement

      La longueur de cheminement d'un arbre est égale à la somme des hauteurs de ses noeuds.

      Pour cet arbre :

      • H(A) = 0
      • H(B) = H(C) = H(D) = 1
      • H(E) = H(F) = H(G) = H(H) = 2
      • H(I) = H(J) = 3

      Donc la longueur de cheminement de cet arbre est : $LC = 0 \times 1 + 1 \times 3 + 2 \times 4 + 3 \times 2 = 0 + 3 + 8 + 6 = 17$

    • Sa longueur de cheminement externe

      La longueur de cheminement externe d'un arbre est égale à la somme des hauteurs de ses feuilles.

      La longueur de cheminement externe de cet arbre est : $LCE = H(E) + H(F) + H(G) + H(I) + H(J) = 2 + 2 + 2 + 3 + 3 = 12$.

    • Sa longueur de cheminement interne

      La longueur de cheminement interne est LCI = LC - LCE = 17 - 12 = 5.

    • Sa profondeur moyenne

      La profondeur moyenne d'un arbre est égale à la longueur du cheminement divisée par sa taille.

      La profondeur moyenne de cet arbre est : $PM = \frac{LC}{T} = \frac{17}{12} = 1,4$

    • Sa profondeur moyenne externe

      La profondeur moyenne externe d'un arbre est égale à la longueur du cheminement externe divisée par le nombre de ses feuilles.

      La profondeur moyenne externe de cet arbre est : $PME = \frac{LCE}{NF} = \frac{11}{5} = 2,2$

    • Sa profondeur moyenne interne

      La profondeur moyenne interne de cet arbre est : $PMI = \frac{LCI}{T-NF} = \frac{5}{10-5} = \frac{5}{5} = 1$

Domaine : Arbres 1 - Question n° 18

On considère l'arbre suivant :

    Donner les caractéritiques suivantes de cet arbre :

    • Sa racine

      La racine de cet arbre est le noeud A.

    • Ses feuilles
    • Cet arbre possède 5 feuilles : E, F, L, J et K.

    • La liste de ses branches

      Cet arbre possède 5 branches : A-B-E; A-B-F; A-C-G-I-L; A-D-H-J et A-D-H-K

    • La liste de ses noeuds internes

      Les noeuds internes de cet arbre sont : B, C; D; G; H et I.

    • Son arité

      L'arité d'un arbre est le nombre maximal d'enfants qu'un noeud peut avoir. L'arité de cet arbre est 2.

  1. Cet arbre est-il un arbre binaire ? Justifier.

    Cet arbre est un arbre binaire car chaque noeud possède au plus 2 enfants (son arité est inférieure ou égale à 2).

  2. Calculer (en détaillant) les mesures suivantes de cet arbre :

    • Sa taille

      La taille d'un arbre est le nombre de ses noeuds. La taille de cet arbre est 12.

    • Sa hauteur

      La hauteur d'un arbre est le nombre de noeuds de la branche la plus longue - 1. La hauteur de cet arbre est : 4 (A-C-G-I-L)

    • Sa longueur de cheminement

      La longueur de cheminement d'un arbre est égale à la somme des hauteurs de ses noeuds.

      Pour cet arbre :

      • H(A) = 0
      • H(B) = H(C) = H(D) = 1
      • H(E) = H(F) = H(G) = H(H) = 2
      • H(I) = H(J) = H(K) = 3
      • H(L) = 4

      Donc la longueur de cheminement de cet arbre est : $LC = 0 \times 1 + 1 \times 3 + 2 \times 4 + 3 \times 2 + 1 \times 4 = 0 + 3 + 8 + 6 + 4 = 21$

    • Sa longueur de cheminement externe

      La longueur de cheminement externe d'un arbre est égale à la somme des hauteurs de ses feuilles.

      La longueur de cheminement externe de cet arbre est : $LCE = H(E) + H(F) + H(L) + H(J) + H(K) = 2 + 2 + 4 + 3 + 3 = 14$.

    • Sa longueur de cheminement interne

      La longueur de cheminement interne est LCI = LC - LCE = 21 - 14 = 7.

    • Sa profondeur moyenne

      La profondeur moyenne d'un arbre est égale à la longueur du cheminement divisée par sa taille.

      La profondeur moyenne de cet arbre est : $PM = \frac{LC}{T} = \frac{21}{12} = 1,75$

    • Sa profondeur moyenne externe

      La profondeur moyenne externe d'un arbre est égale à la longueur du cheminement externe divisée par le nombre de ses feuilles.

      La profondeur moyenne externe de cet arbre est : $PME = \frac{LCE}{NF} = \frac{14}{5} = 2,8$

    • Sa profondeur moyenne interne

      La profondeur moyenne interne de cet arbre est : $PMI = \frac{LCI}{T-NF} = \frac{7}{12-5} = \frac{7}{7} = 1$

Domaine : Arbres 1 - Question n° 19

On considère l'arbre suivant :

    Donner les caractéritiques suivantes de cet arbre :

    • Sa racine

      La racine de cet arbre est le noeud A.

    • Ses feuilles
    • Cet arbre possède 4 feuilles : E, I, J et K.

    • La liste de ses branches

      Cet arbre possède 4 branches : A-B-E; A-B-D-H-J; A-B-D-H-K et A-C-G-I.

    • La liste de ses noeuds internes

      Les noeuds internes de cet arbre sont : B, C; D; G et H.

    • Son arité

      L'arité d'un arbre est le nombre maximal d'enfants qu'un noeud peut avoir. L'arité de cet arbre est 2.

  1. Cet arbre est-il un arbre binaire ? Justifier.

    Cet arbre est un arbre binaire car chaque noeud possède au plus 2 enfants (son arité est inférieure ou égale à 2).

  2. Calculer (en détaillant) les mesures suivantes de cet arbre :

    • Sa taille

      La taille d'un arbre est le nombre de ses noeuds. La taille de cet arbre est 10.

    • Sa hauteur

      La hauteur d'un arbre est le nombre de noeuds de la branche la plus longue - 1. La hauteur de cet arbre est : 4 (2 branches de longueur max : A-B-D-H-J et A-B-D-H-K)

    • Sa longueur de cheminement

      La longueur de cheminement d'un arbre est égale à la somme des hauteurs de ses noeuds.

      Pour cet arbre :

      • H(A) = 0
      • H(B) = H(C) = 1
      • H(D) = H(E) = H(G) = 2
      • H(H) = H(I) = 3
      • H(J) = H(K) = 4

      Donc la longueur de cheminement de cet arbre est : $LC = 0 \times 1 + 1 \times 2 + 2 \times 3 + 3 \times 2 + 2 \times 4 = 0 + 2 + 6 + 6 + 8 = 22$

    • Sa longueur de cheminement externe

      La longueur de cheminement externe d'un arbre est égale à la somme des hauteurs de ses feuilles.

      La longueur de cheminement externe de cet arbre est : $LCE = H(E) + H(I) + H(J) + H(K) = 2 + 3 + 4 + 4 = 13$.

    • Sa longueur de cheminement interne

      La longueur de cheminement interne est LCI = LC - LCE = 22 - 13 = 9.

    • Sa profondeur moyenne

      La profondeur moyenne d'un arbre est égale à la longueur du cheminement divisée par sa taille.

      La profondeur moyenne de cet arbre est : $PM = \frac{LC}{T} = \frac{22}{10} = 2,2$

    • Sa profondeur moyenne externe

      La profondeur moyenne externe d'un arbre est égale à la longueur du cheminement externe divisée par le nombre de ses feuilles.

      La profondeur moyenne externe de cet arbre est : $PME = \frac{LCE}{NF} = \frac{13}{4} = 3,25$

    • Sa profondeur moyenne interne

      La profondeur moyenne interne de cet arbre est : $PMI = \frac{LCI}{T-NF} = \frac{7}{10-4} = \frac{7}{5}$

Domaine : Arbres 2 - Question n° 20

Voici le tableau décrivant un arbre :

  1. Représenter graphiquement l'arbre correspondant.

  2. Quelle est la hauteur de cet arbre ?

    La hauteur d'un arbre est la longueur de la branche la plus longue (sans compter le noeud racine) : ici (A-B-D) : 2.

  3. Cet arbre est-il binaire ? Justifier

    Chaque noeud de cet arbre possède au plus deux fils; donc c'est un arbre binaire..

  4. Cet arbre est-il localement complet ? Justifier

    Chaque noeud de cet arbre possède 0 ou 2 fils; donc c'est un arbre localement complet.

  5. Cet arbre est-il complet ? Justifier

    C'est un arbre localement complet donc chaque feuille est au même niveau hiérarchique : donc il s'agit bien d'un arbre complet.

  6. Donner l'expression numérique représentée par cet arbre et son résultat.

    L'expression numérique représentée par l'arbre est $(7 - 3) + (8 / 2) = 4 + 4 = 8$.

Domaine : Arbres 2 - Question n° 21

Voici le tableau décrivant un arbre :

  1. Représenter graphiquement l'arbre correspondant.

  2. Quelle est la taille de cet arbre ?

    La taille d'un arbre est le nombre de ces noeuds : ici : 7.

  3. Cet arbre est-il binaire ? Justifier

    Chaque noeud de cet arbre possède au plus deux fils; donc c'est un arbre binaire..

  4. Cet arbre est-il localement complet ? Justifier

    Chaque noeud de cet arbre possède 0 ou 2 fils; donc c'est un arbre localement complet.

  5. Cet arbre est-il complet ? Justifier

    C'est un arbre localement complet donc chaque feuille est au même niveau hiérarchique : donc il s'agit bien d'un arbre complet.

  6. Donner l'expression numérique représentée par cet arbre et son résultat.

    L'expression numérique représentée par l'arbre est $(8 + 2) \times (17 - 7) = 10 \times 10 = 100$.

Domaine : Arbres 2 - Question n° 22

Voici le tableau décrivant un arbre :

  1. Représenter graphiquement l'arbre correspondant.

  2. Quelle est la taille de cet arbre ?

    La taille d'un arbre est le nombre de ces noeuds : ici : 9.

  3. Cet arbre est-il binaire ? Justifier

    Chaque noeud de cet arbre possède au plus deux fils; donc c'est un arbre binaire..

  4. Cet arbre est-il localement complet ? Justifier

    Chaque noeud de cet arbre possède 0 ou 2 fils; donc c'est un arbre localement complet.

  5. Cet arbre est-il complet ? Justifier

    C'est un arbre localement complet maistous les feuilles ne sont pas au même niveau hiérarchique : donc il ne s'agit pas d'un arbre complet.

  6. Donner l'expression numérique représentée par cet arbre et son résultat.

    L'expression numérique représentée par l'arbre est $(10 - 8) \times 2 - (7 + 3) = 2 \times 2 - 10 = 4 - 10 = -6$.

Domaine : Arbres 2 - Question n° 23

Voici le tableau décrivant un arbre :

  1. Représenter graphiquement l'arbre correspondant.

  2. Quelle est la hauteur de cet arbre ?

    La hauteur d'un arbre est la longueur de la branche la plus longue (sans compter le noeud racine) : ici (A-C-F-H) : 3.

  3. Cet arbre est-il binaire ? Justifier

    Chaque noeud de cet arbre possède au plus deux fils; donc c'est un arbre binaire..

  4. Cet arbre est-il localement complet ? Justifier

    Chaque noeud de cet arbre possède 0 ou 2 fils; donc c'est un arbre localement complet.

  5. Cet arbre est-il complet ? Justifier

    C'est un arbre localement complet maistous les feuilles ne sont pas au même niveau hiérarchique : donc il ne s'agit pas d'un arbre complet.

  6. Donner l'expression numérique représentée par cet arbre et son résultat.

    L'expression numérique représentée par l'arbre est $(14 + 2) /(2 \times 3 - 4) = 16 /(6 \times 4) = 16 / 2 = 8$.

Domaine : Arbres 3 - Question n° 24

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 :

Domaine : Arbres 3 - Question n° 25

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 :

Domaine : Arbres 4 - Question n° 26

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 un arbre binaire de recherche associé à cette liste.

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

    La hauteur de la branche la plus longue est de 4. La hauteur de la branche la plus courte est de 3. La différence entre la longueur de la branche la plus longue et la longueur de la branche la plus courte est de 1, inférieure ou égale à 1; donc cet arbre est équilibré.

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

Domaine : Arbres 4 - Question n° 27

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 un arbre binaire de recherche associé à cette liste.

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

    La hauteur de la branche la plus longue est de 5. La hauteur de la branche la plus courte est de 1. La différence entre la longueur de la branche la plus longue et la longueur de la branche la plus courte est de 4, supérieure à 1; donc cet arbre n'est pas équilibré.

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

Domaine : Arbres 4 - Question n° 28

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 un arbre binaire de recherche associé à cette liste.

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

    La hauteur de la branche la plus longue est de 4. La hauteur de la branche la plus courte est de 2. La différence entre la longueur de la branche la plus longue et la longueur de la branche la plus courte est de 2, supérieure à 1; donc cet arbre n'est pas équilibré.

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