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

Les algorithmes, les structures de données et la complexité sont des concepts fondamentaux en informatique, essentiels pour concevoir des systèmes performants et efficaces. Que vous soyez étudiant, professionnel en développement logiciel ou passionné par l’informatique, comprendre ces notions est crucial pour résoudre des problèmes complexes et optimiser les performances des applications. Dans cet article, nous vous proposons un QCM (Questionnaire à Choix Multiples) couvrant ces trois domaines clés. À travers ce test, vous pourrez évaluer vos connaissances en matière de conception d’algorithmes, de choix de structures de données appropriées et d’analyse de la complexité des algorithmes. Que vous soyez débutant ou confirmé, ce QCM vous aidera à tester vos compétences et à améliorer votre compréhension de ces concepts fondamentaux.

 
 

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

Réponse

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é

Réponse

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

Réponse  
 

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

Réponse

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

Réponse

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

Réponse  
 

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

Réponse

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

Réponse

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

Réponse  
 

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

Réponse