Enoncé 23 : Listes linéaires chaînées - Récursivité - Arbres - Méthodes d'index - Hachage externe  Corrigé 23

Exercice 1 : Listes bilatérales

Utiliser le modèle de liste linéaire chaînée bilatérale pour écrire les algorithmes de :

- Recherche de l'adresse du K-ième élément.

- Insertion d'une valeur V à la P-ième position ( P donné ).

Exercice 2 : Sémantique de la récursion

Quelles sont les règles de passage automatique d'un algorithme récursif vers un algorithme itératif.

Utiliser le modèle des arbres de recherche binaires pour écrire les algorithmes de:

- Recherche d'un élément A donné,

- Insertion d'une valeur V donnée.

Citer les différents cas de la suppression d'une valeur V donnée.

Soit un fichier d'index à 2 niveaux. Faire un schéma, le décrire, puis écrire l'algorithme de recherche d'un article de clé donnée :

- dans le cas o� l 'index est supposé totalement en mémoire centrale,

- dans le cas ou seulement l'index de niveau 1 est en mémoire central.

On utilisera le module de recherche dichotomique (sans l’écrire).

Exercice 5 : Chaînage séparé externe

Soit un fichier composé de M blocs consécutifs o� chacun peut contenir B articles. On désire ranger les éléments par la technique du chaînage séparé. Proposer un schéma, le décrire puis développer

- le module d'initialisation,

- l'algorithme de recherche d'un article donné,

- l'algorithme d'insertion d'un article de clé donnée.

* * * * *