suivant: À propos de ce
Exercice 9.1
On désire distribuer des clés codées sous forme de chaînes de caractères sur
un intervalle d'entiers
. Chaque clé est codée dans un
tableau de caractères de longueur
et se termine par le
caractère '#'. La méthode de codage de la clé
est la suivante:
si
, alors
,
où
est une fonction transformant un caractère en
nombre entier.
- En pratique, on choisit pour B une puissance de 2, par exemple 128
ou 256, et pour M, un nombre premier. Expliquer ces choix.
- Ecrire la fonction d'adressage
en s'inspirant du schéma
de Horner pour l'évaluation d'un polynôme en un point donné.
Exercice 9.2
On considère un ensemble de clés données directement sous forme
numérique, que l'on veut stocker dans une table d'adressage dispersé, de
taille
. Soit la fonction de hachage:
.
- Décrire les structures de données et la gestion des collisions
pour la séquence d'ajouts suivante: 10, 22, 31, 4, 15, 28, 83, 88, 59, 37,
dans les cas suivants:
- chaînage externe;
- stockage interne et traitement des collisions par
placement dans la première case libre (modulo
) à partir de la case
calculée;
- stockage interne avec, pour rechercher une nouvelle case libre
en cas d'occupation, un pas donné par une seconde fonction
d'adressage
.
- Décrire ce qui se passe dans les trois cas si on poursuit par les 2
opérations suivantes, suppression de la clé 31 et recherche de la clé 59.
Exercice 9.3
Reprendre l'exercice 7.5, décrire la structure de donnée permettant de retrouver un avion dans le tas
- par sa destination
- par son indicatif
suivant: À propos de ce
Maylis Delest
2007-11-21