Exercices corrigés — Tableaux associatifs, hachage et sérialisation (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- add empile, replace écrase
- Quatre besoins, quelle structure ?
- Sérialiser à la main, et compter les jetons
- Une mauvaise fonction de hachage, mesurée
- Le facteur de charge, et ce qu'il permet de prévoir
- L'ordre que le hachage ne donne pas
- Adressage ouvert : la suppression naïve casse la recherche
- Muter une clé rend l'entrée introuvable
- Hashtbl.hash ne regarde pas tout
- Le pire cas provoqué, chronométré
- Probleme – Une table de hachage par chaînage, sur tableaux statiques
- Probleme – Le paradoxe des anniversaires, démontré et mesuré
- Probleme – L'aller-retour de la sérialisation d'un arbre
- Probleme – Sérialiser une structure relationnelle : le graphe
- Probleme – Trois tableaux associatifs, chronométrés