Sujet n°29
Sujet original
Pour télécharger l'énoncé original, cliquer ici.
Exercice n°1☘
Un arbre binaire est implémenté par la classe Arbre
donnée ci-dessous.
Les attributs fg
et fd
prennent pour valeurs des instances de la classe Arbre
ou None
.
1 2 3 4 5 |
|
Exemples
L’arbre ci-contre sera donc implémenté de la manière suivante :
>>> a = Arbre(1)
>>> a.fg = Arbre(4)
>>> a.fd = Arbre(0)
>>> a.fd.fd = Arbre(7)
Écrire une fonction récursive taille
prenant en paramètre une instance a
de la classe
Arbre
et qui renvoie la taille de l’arbre que cette instance implémente.
Écrire de même une fonction récursive hauteur
prenant en paramètre une instance a
de la classe Arbre
et qui renvoie la hauteur de l’arbre que cette instance implémente.
Si un arbre a un seul nœud, sa taille et sa hauteur sont égales à 1. S’il est vide, sa taille et sa hauteur sont égales à 0.
Tester les deux fonctions sur l’arbre représenté ci-dessous :
Une solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
|
Exercice n°2☘
La méthode insert
de la classe list
permet d’insérer un élément dans une liste à un
indice donné.
Le but de cet exercice est, sans utiliser cette méthode, d’écrire une fonction ajoute
réalisant cette insertion en produisant une nouvelle liste.
Commentaires
Ici, le mot « liste » est à comprendre dans le sens « liste Python » (c'est-à-dire tableau) plutôt que dans le sens du type abstrait de données liste étudié en Terminale.
Cette fonction ajoute
prend en paramètres trois variables indice
, element
et liste
et renvoie une liste L
dans laquelle les éléments sont ceux de la liste liste
avec, en
plus, l’élément element
à l’indice indice
.
On considère que les variables indice
et element
sont des entiers positifs et que les
éléments de liste
sont également des entiers positifs.
Les éléments de la liste liste
, dont les indices sont supérieurs ou égaux à indice
apparaissent décalés vers la droite dans la liste L
.
Si indice
est supérieur ou égal au nombre d’éléments de la liste liste
, l’élément
element
est ajouté dans L
après tous les éléments de la liste liste
.
Exemples
>>> ajoute(1, 4, [7, 8, 9])
[7, 4, 8, 9]
>>> ajoute(3, 4, [7, 8, 9])
[7, 8, 9, 4]
>>> ajoute(4, 4, [7, 8, 9])
[7, 8, 9, 4]
Compléter et tester le code ci-dessous :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Commentaires sur le code original
Pour télécharger l'original du fichier à compléter, cliquer ici.
Une solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|