next up previous
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 $ [0..M-1]$. Chaque clé est codée dans un tableau de caractères de longueur $ LMAX$ et se termine par le caractère '#'. La méthode de codage de la clé $ x$ est la suivante:
si $ x = x_1 x_2,...x_l\char93 $, alors $ h(x) = (\hbox{\it cvn}(x_1)*B^{l-1} +
\hbox{\it cvn}(x_2)*B^{l-2} + \ldots+ \hbox{\it cvn}(x_l)) \hbox{\it
mod } M$,
$ \hbox{\it cvn}$ est une fonction transformant un caractère en nombre entier.

  1. En pratique, on choisit pour B une puissance de 2, par exemple 128 ou 256, et pour M, un nombre premier. Expliquer ces choix.
  2. Ecrire la fonction d'adressage $ h$ 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 $ M = 11$. Soit la fonction de hachage: $ h(x)= x \hbox{\it\ mod } M$.

  1. 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:
    1. chaînage externe;
    2. stockage interne et traitement des collisions par placement dans la première case libre (modulo $ M$) à partir de la case calculée;
    3. stockage interne avec, pour rechercher une nouvelle case libre en cas d'occupation, un pas donné par une seconde fonction d'adressage $ h'(x) = 1 + x \hbox{\it\ mod } (M-1)$.
  2. 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

  1. par sa destination
  2. par son indicatif




next up previous
suivant: À propos de ce
Maylis Delest 2007-11-21