QCM Algorithmes, structures de données et complexité – Partie 15

juillet 6, 2024juillet 6, 2024 Thomas Aucun commentaire

Questions pratiques pour testez vos connaissances sur la complexité en espace et en temps des algorithmes et des structures de données courants. Testez votre connaissance et travaillez sur les questions que vous trompez le plus souvent.

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.

1. Dans le contexte des tables de hachage, à quoi fait référence le « facteur de charge » ?

A Le rapport entre le nombre d’entrées et le nombre d’emplacements dans la table.

B Le nombre maximal de collisions autorisées avant le redimensionnement

C Le pourcentage de clés nulles

D Le temps de recherche moyen pour une entrée

Le facteur de charge (load factor) d’une table de hachage est le rapport entre le nombre d’entrées (ou d’éléments stockés) et le nombre d’emplacements. Il mesure le degré de saturation de la table de hachage et influe sur la décision de redimensionner la table pour maintenir un fonctionnement efficace.

2. Quelle stratégie permet de réduire considérablement le risque de collisions dans une table de hachage ?

A L’utilisation d’un nombre premier pour la taille de la table de hachage

B Augmenter la taille des clés

C Diminuer le nombre d’entrées

D Utilisation de plusieurs fonctions de hachage pour la même clé

L’utilisation d’un nombre premier pour la taille de la table de hachage peut réduire considérablement le risque de collisions. En effet, les nombres premiers permettent de répartir les clés plus uniformément dans la table, surtout lorsqu’ils sont associés à une fonction de hachage bien conçue.

3. Comment accéder à une valeur stockée dans une table de hachage en fonction de sa clé ?

A En calculant le hachage de la clé et en effectuant une recherche linéaire

B En indexant directement le tableau avec la clé

C En calculant le hachage de la clé et en l’utilisant comme index

D En triant les clés et en effectuant une recherche binaire

Pour accéder à une valeur dans une table de hachage, vous calculez le hachage de la clé, ce qui donne un index dans le tableau ou le tableau de stockage où la valeur peut être trouvée. Cette opération est généralement O(1), ce qui rend les tables de hachage très efficaces pour la recherche de données.

4. Quelle est la méthode la plus courante pour gérer les collisions dans une table de hachage par programmation ?

A Adressage ouvert avec sondage linéaire

B Stockage des valeurs dans une liste à chaque index

C Doublement de la taille de la table de hachage en cas de collision

D Utilisation d’une fonction de hachage secondaire

L’adressage ouvert avec sondage linéaire est une méthode courante de gestion programmatique des collisions dans une table de hachage. Elle consiste à trouver le prochain emplacement disponible dans le tableau de la table en se déplaçant séquentiellement à partir du point de collision, ce qui permet de résoudre la collision sans nécessiter de structures de données supplémentaires.

5. Comment s’assurer qu’une table de hachage reste efficace au fur et à mesure de l’ajout d’entrées ?

A En diminuant périodiquement la taille de la table

B En réorganisant toutes les entrées dans une table plus grande lorsque le facteur de charge atteint un certain seuil

C En limitant le nombre d’entrées

D En convertissant la table en un arbre de recherche binaire en cas de débordement

Pour garantir l’efficacité au fur et à mesure de l’ajout d’entrées, il faut réorganiser toutes les entrées dans une table plus grande lorsque le facteur de charge atteint un certain seuil. Ce processus, connu sous le nom de redimensionnement ou de réorganisation, permet de maintenir un faible facteur de charge, de réduire la probabilité de collisions et de raccourcir les temps d’accès.

6. Quelle est la meilleure approche pour stocker des valeurs ayant la même clé de hachage dans une table de hachage ?

A L’écrasement de la valeur précédente

B Lier les nouvelles valeurs aux valeurs existantes dans une liste chaînée

C Ignorer les nouvelles valeurs dont les clés sont dupliquées

D Stockage des valeurs dans une table adjacente

L’association de nouvelles valeurs aux valeurs existantes dans une liste chaînée, connue sous le nom de chaînage, est une approche efficace pour gérer les collisions causées par plusieurs clés ayant le même hachage. Cette méthode permet à plusieurs valeurs de coexister au même index en étendant la résolution des collisions au-delà d’un seul emplacement.

7. Un développeur remarque que les temps de récupération d’une table de hachage sont constamment lents. Quelle en est la raison probable ?

A La fonction de hachage est trop complexe

B Le facteur de charge est trop élevé, ce qui provoque des collisions excessives

C Les clés ne sont pas distribuées uniformément

D Toutes les entrées sont stockées dans un seul conteneur

La lenteur des temps de recherche peut souvent être attribuée à un facteur de charge élevé, entraînant un nombre excessif de collisions. Lorsqu’un trop grand nombre d’entrées sont affectées aux mêmes emplacements, les mécanismes de résolution des collisions, tels que le sondage linéaire ou le chaînage, peuvent devenir inefficaces, ce qui augmente les temps de recherche.

8. Lors des tests, l’opération d’ajout dans une table de hachage échoue parfois à insérer de nouveaux éléments. Quel pourrait être le problème ?

A La fonction de hachage renvoie toujours la même valeur

B Les collisions ne sont pas gérées correctement

C La table est pleine et ne peut être redimensionnée

D La clé est nulle

Si l’ajout de nouveaux éléments à une table de hachage échoue parfois, cela peut indiquer que les collisions ne sont pas gérées correctement. Des stratégies efficaces de résolution des collisions, telles que l’adressage ouvert ou le chaînage, sont nécessaires pour garantir que tous les éléments peuvent être insérés, même lorsque les hachages entrent en collision.

9. L’implémentation d’une table de hachage subit une dégradation intermittente des performances. Quelle peut être la cause de ce problème ?

A Performances incohérentes de la fonction de hachage

B La variation de la taille des entrées

C Opérations périodiques de redimensionnement de la table

D Distribution non uniforme des clés

La dégradation intermittente des performances d’une table de hachage peut être due à des opérations périodiques de redimensionnement de la table. Le redimensionnement, en particulier le réassemblage de toutes les entrées dans une table plus grande, peut être coûteux en termes de calcul et peut affecter temporairement les performances, en particulier s’il est déclenché fréquemment au fur et à mesure que des entrées sont ajoutées.

10. Quel est le concept de base de la programmation dynamique ?

A La décomposition des problèmes en sous-problèmes plus petits

B Trouver la solution la plus rapide sans se soucier de l’exactitude des résultats

C Utiliser exclusivement la récursivité

D Mémoriser les résultats intermédiaires

La programmation dynamique repose sur la décomposition d’un problème complexe en sous-problèmes plus petits, la résolution de chaque sous-problème une seule fois et le stockage des solutions en vue d’une utilisation ultérieure (souvent appelé mémorisation), plutôt que de recalculer les solutions.

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.

QCMs qui pourraient vous intéresser :

1. Dans le contexte des tables de hachage, à quoi fait référence le « facteur de charge » ?

2. Quelle stratégie permet de réduire considérablement le risque de collisions dans une table de hachage ?

3. Comment accéder à une valeur stockée dans une table de hachage en fonction de sa clé ?

4. Quelle est la méthode la plus courante pour gérer les collisions dans une table de hachage par programmation ?

5. Comment s’assurer qu’une table de hachage reste efficace au fur et à mesure de l’ajout d’entrées ?

6. Quelle est la meilleure approche pour stocker des valeurs ayant la même clé de hachage dans une table de hachage ?

7. Un développeur remarque que les temps de récupération d’une table de hachage sont constamment lents. Quelle en est la raison probable ?

8. Lors des tests, l’opération d’ajout dans une table de hachage échoue parfois à insérer de nouveaux éléments. Quel pourrait être le problème ?

9. L’implémentation d’une table de hachage subit une dégradation intermittente des performances. Quelle peut être la cause de ce problème ?

10. Quel est le concept de base de la programmation dynamique ?

Vous pourrez aussi aimer

QCM Algorithmes, structures de données et complexité – Partie 11

QCM Algorithmes, structures de données et complexité – Partie 13

QCM Algorithmes, structures de données et complexité – Partie 6

Laisser un commentaire Annuler la réponse