PDF : pour impression
Compétence : Savoir décrire et caractériser un arbre ou un nœud.
Exercice 1 #
On donne l’arbre suivant :
arbre 1
- Déterminer pour cet arbre, sa racine, sa taille, sa hauteur, ses nœuds internes et ses feuilles
- Pour le noeud 4, déterminer son père, ses frères, sa hauteur, sa profondeur.
Exercice 2 #
On donne ci-dessous le tableau caractérisant un arbre :
| Noeud | Etiquette | Noeud du SAG | Noeud du SAD |
|---|---|---|---|
| 1 | * |
2 |
3 |
| 2 | + |
4 |
5 |
| 3 | - |
6 |
7 |
| 4 | 3 |
||
| 5 | / |
8 |
9 |
| 6 | 8 |
||
| 7 | * |
10 |
11 |
| 8 | 4 |
||
| 9 | 2 |
||
| 10 | 2 |
||
| 11 | 3 |
- Représenter l’arbre correspondant.
- Quelle est la hauteur de cet arbre ?
- Cet arbre est-il binaire, complet ?
- Quel est le résultat de cette suite d’opérations mathématiques ?
Compétence : Savoir évaluer quelques mesures sur les arbres binaires
Exercice 3 #
On donne l’arbre A suivant :
- Calculer toutes les longueurs de cheminement.
- En déduire toutes les profondeurs moyennes. On pourra essayer de les représenter sur l’arbre.
Compétence : Identifier des situations nécessitant des structures de données arborescentes.
Exercice 4 #
On donne ci-dessous une liste aléatoire de 14 nombres entiers :
25 60 35 10 5 20 65 45 70 40 50 55 40 15
Construire (dans l’ordre de la liste) l’arbre binaire de recherche associé.
Compétence : Savoir raisonner avec un type abstrait
Exercice 5 #
On donne la suite d’instructions suivantes :
A = creer_arbre(2, creer_arbre_feuille(4), creer_arbre_feuille(3))
B = creer_arbre(5, creer_arbre_vide(4), creer_arbre_feuille(6))
C = creer_arbre(1, A, B)
-
Représenter la situation sous forme d’un arbre
-
Donner l’arbre correspondant à l’instruction :
T = SAD(C) -
Quelle est la valeur retournée par l’instruction suivante :
r = racine(B)