Exercice 1 : Liste chainée

1.1. A l'aide de la classe Cellule, construire la liste chainée l1 suivante :

2

1.2. Coder une fonction somme qui a comme paramètre une liste chainée de nombre et qui retourne comme résultat la somme des valeurs de cette-ci.

 Tester avec :

print(somme(l1))

Résultat :

36

Exercice 2 : Pile et File 

2.1. Ecrire une fonction string_to_pile qui prend comme paramètre une chaine de caractère et qui retourne une pile avec un caractère de la chaine dans chaque case.

2.2. Ecrire une fonction string_to_file qui prend comme paramètre une chaine de caractère et qui retourne une file avec un caractère de la chaine dans chaque case.

2.3. Ecrire une fonction longueur_pile qui prend comme paramètre une pile et qui retourne sa longueur.

Tester avec :

texte = "ressasser"
p1 = string_to_pile(texte)
print(longueur_pile(p1))

 Résultat :

9

2.4. Un palindrome est une chaine de caractères qui se lit de la même manière de gauche à droite et de droite à gauche.

Exemples:
  - ressasser
  - 
laval 

En utilisant les fonctions string_to_file et string_to_pile, écrire une fonction palindrome qui prend comme paramètre une pile de caractère et une file de caractère et qui retourne True si c'est un palindrome et False sinon.

 Tester avec :

texte = "ressasser"
p1 = string_to_pile(texte)
f1 = string_to_file(texte)

print(texte,palindrome(p1,f1))


texte = "ramasser"
p1 = string_to_pile(texte)
f1 = string_to_file(texte)

print(texte,palindrome(p1,f1))

 

Résultat :

ressasser True
ramasser False

 

Exercice 3 : Arbre binaire

3.1. A l'aide de la classe Noeud construire l'arbre binaire suivant:

 

 3.2. Cette arbre, est-il un arbre binaire de recherche? Justifier.

3.3. Ecrire une fonction somme_noeuds qui calcule la somme de tous les sommets de l'arbre.

 Tester avec :

print(somme_noeuds(a1))

 Résultat :

66

 

Exercice 4 : Arbre binaire de recherche

4.1. A l'aide de la  méthode ajoute dans la classe ABR, construire l'arbre binaire suivant:

 

 

 Tester avec :

a1 = ABR()
a1.ajouter(32)
.........
......
a1.affiche()
 
Résultat :

(((9(13))17(25(27)))32((41(44))48((53)55)))
 
4.2. Ecrire une fonction largeur qui a comme paramètres la racine d'un ABR et le niveau des noeuds à afficher.
Pour notre ABR :
  • le niveau 0 à comme sommet 32;
  • le niveau 1 à comme sommets 17, 48;
  • le niveau 2 à comme sommets 55, 41, 25 et 9;
  • ... 
 
Tester avec :
largeur(a1.racine,2)
 
Résultat :
55
41
25
9

 

footer2

Richard GAUTHIER
Professeur de Physique Appliquée
Certification ISN
Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.

www.carhaix2020.bzh