Question posée au contrôle continu du 16 juin 1997
Soient deux fonctions de hash-code H1 et H2 retournant les valeurs numériques suivantes:
| mot: | les | examens | du | premier | cycle | pour | lesquels | il | n | y | aurait | qu |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H1(mot): | 15 | 6 | 11 | 1 | 3 | 6 | 2 | 5 | 7 | 15 | 2 | 9 |
| H2(mot): | 8 | 5 | 12 | 14 | 2 | 10 | 17 | 7 | 5 | 13 | 8 | 22 |
| mot: | un | examen | oral | a | subir | sont | admis | si | chaque | note | atteint | quatre |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| H1(mot): | 13 | 18 | 16 | 11 | 10 | 23 | 8 | 8 | 9 | 20 | 15 | 22 |
| H2(mot): | 9 | 6 | 1 | 4 | 3 | 7 | 13 | 6 | 17 | 2 | 12 | 16 |
On suppose que l'on utilise la méthode du chaînage externe à partir d'un tableau de 11 positions, en utilisant H1 pour déterminer quelle chaîne utiliser et H2 pour trier les éléments d'une même chaîne (c'est-à-dire qu'au sein d'une même chaîne, un mot mi sera placé avant un autre mot mj si H2(mi)<H2(mj)). Dessinez le tableau des chaînes que l'on obtient, en mettant un mot et le résultat de H2 pour ce mot dans chaque élément de chaîne. Indiquez quelle expression basée sur H1 vous avez utilisée pour le choix de la chaîne.
Site Hosting: Bronco