Enoncé 9 : Hachage interne - Arbres - Piles   Corrigé 9

Exercice 1 : Hachage

Soit une table T(0..9).

1. Définir la structure de T avec les 3 méthodes de hachage suivantes :

- Essai linéaire

- Chaînage interne

- Chaînage séparé

2. Pour chacune de 3 méthodes, remplir T avec les insertions ( dans l'ordre indiqué) de clés suivantes avec leurs transformées respectives mises entre parenthèses :

a(2), b(4), c(2), d(3), e(5), f(3), g(9), h(2), i(8)

3. Donner les états successifs de T après la suppression de a et i ( dans cet ordre) dans le cas du chaînage interne.

Exercice 2 : Arbres de recherche binaire (arb)

1. Construire l'arb avec les clés suivantes (dans cet ordre) : 12, 8, 3, 15, 13, 20, 35, 66, 9, 11, 10

2. Donner la liste des clés avec les parcours inordre, préordre et postordre.

3. Donner l'algorithme récursif qui parcourt tous les éléments d'un arb en ordre décroissant.

4. Donner les états de la pile au moment o� les feuilles de l'arb construit en 1. sont visités en inordre.

5. Soit � = n1, n2, . . ,np la suite des nœuds se trouvant sur le chemin qui mène de la racine d'un arb vers une feuille d'adresse F. On veut utiliser � pour déterminer le suivant de F.

- Quelle structure donner à � ?

- Ecrire la fonction Suivant(F).

* * * * *