Français
Menu

Structures de données et algorithmes

Quelle comparaison du chaînage (relier par une liste chaînée les éléments d'une même position) et de l'adressage ouvert (chercher une autre position libre dans la table), comme méthodes de résolution des collisions d'une table de hachage, est correcte ? Le facteur de charge est le nombre d'éléments stockés divisé par la taille de la table.

  1. ALe chaînage peut stocker des éléments même quand le facteur de charge dépasse 1, alors que l'adressage ouvert ne peut pas stocker plus d'éléments que la taille de la table, et son nombre de sondages augmente fortement quand le facteur de charge approche de 1
  2. BL'adressage ouvert n'a pas de collisions, si bien qu'une recherche demande toujours un seul sondage, quel que soit le facteur de charge
  3. CAvec le chaînage, le coût d'une recherche reste le même, aussi élevé que soit le facteur de charge
Afficher la réponse et l'explication

Réponse : A. Le chaînage peut stocker des éléments même quand le facteur de charge dépasse 1, alors que l'adressage ouvert ne peut pas stocker plus d'éléments que la taille de la table, et son nombre de sondages augmente fortement quand le facteur de charge approche de 1

Le chaînage relie en listes les éléments d'une même position : il peut donc stocker plus d'éléments que la taille de la table, mais la longueur moyenne des listes croît proportionnellement au facteur de charge, et le coût de recherche aussi. L'adressage ouvert range tout à l'intérieur de la table : il peut contenir au plus autant d'éléments que la taille de la table, et le nombre de sondages nécessaires pour trouver un emplacement libre augmente fortement quand le facteur de charge approche de 1. Quelle que soit la méthode, on agrandit généralement la table et on réinsère tous les éléments (rehachage) dès que le facteur de charge dépasse une limite choisie, par exemple de 0,5 à 0,75 environ. Les collisions se produisent aussi en adressage ouvert ; celui-ci les traite en cherchant une position libre.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. Quelle condition est nécessaire pour utiliser la recherche dichotomique, qui compare la cible à l'élément du milieu et réduit de moitié l'intervalle de recherche à chaque fois ?
  2. On effectue une recherche dichotomique parmi 1000 valeurs distinctes triées par ordre croissant. Si une comparaison indique si les valeurs sont égales, plus petites ou plus grandes, quel est le nombre maximal de comparaisons, en comptant les recherches réussies comme infructueuses ?
  3. Une recherche dichotomique cherche 38 dans le tableau croissant a[0] à a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. L'intervalle de recherche commence avec lo = 0 et hi = 9, et la position du milieu vaut (lo + hi) ÷ 2 arrondi à l'entier inférieur. Quelle liste donne, dans l'ordre, les éléments comparés à 38 ?
  4. On trie par ordre croissant le tableau 5, 3, 8, 1, 4 avec le tri à bulles. Quel est le tableau après une passe, au cours de laquelle les éléments voisins sont comparés du début jusqu'à la fin et échangés chaque fois que celui de gauche est le plus grand ?
  5. On trie par ordre croissant le tableau 29, 10, 14, 37, 13 avec le tri par sélection, qui cherche le minimum de la partie non triée et l'échange avec le premier élément de cette partie. Quel est le tableau après deux répétitions de cette étape ?