25-NSIJ2G11-2

  Énoncé   Sujet

1. Le mot 'EW' a pour clé 0x45 + 0x57 = 0x9C.

2. Puisque les mots 'SAC' et 'CAS' partagent les mêmes caractères et que l'addition est commutative, ils partagent la même clé suivant la fonction de hachage donnée.

3. def code_hachage(mot):
       somme = 0
       for caractere in mot:
           somme = somme + ord(caractere)
       return somme % 0x100  # somme & 0xFF serait plus pertinent
   

4. L'expression somme % 0x100 permet d'extraire l'octet de poids faible de la somme totale des codes ASCII. Puisque la clé est stockée sur un octet, elle varie entre 0 (0x00) et 255 (0xFF).

5. Dans le pire des cas, le mot à ajouter se place en fin de liste : la fonction parcourt alors toute la liste et compare le mot à chacun des \(n\) mots déjà présents. Ainsi, dans le pire ces cas, \(n\) comparaisons de chaînes sont effectuées.

6. L'expression c in dico renvoie True si la clé c est présent dans le dictionnaire dico, False sinon.

7. def ajouter_mot_dict(dict_mots, mot):
       cle = code_hachage(mot)
       if cle in dict_mots:
           ajouter_mot_liste(dict_mots[cle], mot)
       else:
           dict_mots[cle] = [mot]
   

8. Appel №	debut	fin
   1	0	5
   2	0	1
   3	1	1

9. La recherche dichotomique est plus efficace, car à chaque comparaison, elle écarte la moitié des mots restants, là où une recherche linéaire simple n'en écarte qu'un seul.

10. La recherche dichotomique effectue \(\boxed{O(\log n)}\) comparaisons pour une liste de longueur \(n\).

11. def mot_present(dict_mots, mot):
        cle = code_hachage(mot)
        if cle not in dict_mots:
            return False
        liste = dict_mots[cle]
        return est_present(liste, mot, 0, len(liste))