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

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. Quelle ligne initialise correctement le point central dans le tri rapide pour un segment de tableau compris entre le point le plus bas et le point le plus haut ?

A int pivot = arr[haut];

B int pivot = arr[(bas + haut) / 2];

C int pivot = arr[bas];

D int pivot = haut;

Le choix de l’élément central comme pivot, int pivot = arr[(bas + haut) / 2];, permet d’éviter les pires performances sur des tableaux déjà triés ou triés à l’envers en visant une partition équilibrée.

2. Quelle technique permet d’améliorer les performances du tri rapide sur les petits tableaux ?

A Tri par insertion hybride

B Sélection aléatoire des pivots

C Profondeur de récursion décroissante

D Augmentation de la taille de la pile

Pour les petits tableaux, les performances du tri rapide sont améliorées par le passage au tri par insertion, un algorithme de tri plus simple et plus efficace pour les petits ensembles de données en raison de sa faible surcharge.

3. Quelle est l’action principale de la fonction merge dans le tri par fusion ?

A Diviser le tableau

B Trier les sous-tableaux

C Fusionner les sous-ensembles triés

D Comparaison de chaque élément

La fonction de fusion du tri par fusion combine deux sous-ensembles triés en un seul tableau trié, ce qui constitue une étape cruciale pour obtenir l’ordre de tri global.

4. L’algorithme de tri par insertion d’un développeur ne trie pas correctement. Quelle est l’erreur la plus courante à vérifier ?

A Le mauvais placement de l’élément clé

B Mauvais calcul de l’index

C Saut d’éléments

D Comparaison incorrecte des éléments

Une erreur fréquente dans le tri par insertion est la comparaison incorrecte des éléments, ce qui entraîne l’insertion incorrecte de l’élément clé dans la partie triée du tableau.

5. Le tri rapide provoque une erreur de dépassement de pile. Quelle est la cause probable ?

A Récursion excessive sur de grands ensembles de données

B Sélection incorrecte des pivots entraînant des partitions déséquilibrées

C Appels récursifs non terminés

D Toutes les conditions sont remplies mais l’échec persiste

Une sélection incorrecte des pivots dans le tri rapide peut conduire à des partitions fortement déséquilibrées, entraînant une profondeur de récursion excessive sur des ensembles de données presque triés ou sur certains ensembles de données à motifs, ce qui peut entraîner une erreur de dépassement de pile.

6. Qu’est-ce qu’une table de hachage ?

A Une structure de données qui stocke des paires clé-valeur dans un tableau linéaire.

B Une structure de données qui organise les données en vue d’une recherche, d’une insertion et d’une suppression rapides en fonction des clés.

C Une structure de données permettant de stocker des données hiérarchiques

D Une structure de données qui stocke les données dans des nœuds avec une clé et des valeurs multiples

Une table de hachage est une structure de données qui organise efficacement les données pour des opérations rapides telles que la recherche, l’insertion et la suppression en utilisant une fonction de hachage pour calculer un index dans un tableau d’emplacements, à partir duquel la valeur souhaitée peut être trouvée.

7. Lequel des cas suivants est un cas d’utilisation courant d’une table de hachage ?

A Mise en œuvre d’un système d’indexation de base de données

B Stocker les préférences d’un utilisateur dans une application web

C Effectuer des recherches rapides dans un grand ensemble de données

D Toutes les réponses ci-dessus

Les tables de hachage sont des structures de données polyvalentes utilisées dans diverses applications telles que l’indexation de bases de données, le stockage des préférences des utilisateurs et la recherche rapide au sein de grands ensembles de données grâce à leur efficacité en matière de récupération des données par clé.

8. Qu’est-ce qu’une collision dans une table de hachage ?

A Lorsque deux clés ont la même valeur

B Lorsqu’une fonction de hachage renvoie le même index pour des clés différentes

C Lorsqu’une table de hachage dépasse son facteur de charge

D Lorsqu’une clé est perdue à la suite d’un écrasement

Une collision dans une table de hachage se produit lorsqu’une fonction de hachage associe deux clés ou plus au même index dans le tableau. La gestion des collisions est essentielle pour maintenir l’efficacité et la précision d’une table de hachage.

9. Quelle est la principale difficulté liée à la conception d’une fonction de hachage pour une table de hachage ?

A S’assurer qu’elle est réversible

B Minimiser l’occurrence des collisions

C S’assurer qu’il produit une sortie unique pour chaque entrée

D Maximiser la complexité de calcul

Le principal défi dans la conception d’une fonction de hachage est de minimiser l’occurrence des collisions. Une bonne fonction de hachage distribue les clés uniformément dans la table de hachage, ce qui réduit la probabilité de collisions et permet de maintenir des temps d’accès efficaces.

10. Quelle technique est couramment utilisée pour résoudre les collisions dans une table de hachage ?

A Sondage linéaire

B Utilisation d’un arbre de recherche binaire

C Doubler la taille de la table lorsqu’elle est pleine

D Stockage de toutes les entrées dans une seule liste chaînée

Le sondage linéaire (Linear probing) est une technique courante de résolution des collisions dans laquelle, en cas de collision, la table de hachage recherche le prochain emplacement disponible en se déplaçant séquentiellement dans la table. Cette méthode est simple à mettre en œuvre et peut s’avérer efficace pour répartir les entrées de manière homogène dans la table.

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

QCMs qui pourraient vous intéresser :

1. Quelle ligne initialise correctement le point central dans le tri rapide pour un segment de tableau compris entre le point le plus bas et le point le plus haut ?

2. Quelle technique permet d’améliorer les performances du tri rapide sur les petits tableaux ?

3. Quelle est l’action principale de la fonction merge dans le tri par fusion ?

4. L’algorithme de tri par insertion d’un développeur ne trie pas correctement. Quelle est l’erreur la plus courante à vérifier ?

5. Le tri rapide provoque une erreur de dépassement de pile. Quelle est la cause probable ?

6. Qu’est-ce qu’une table de hachage ?

7. Lequel des cas suivants est un cas d’utilisation courant d’une table de hachage ?

8. Qu’est-ce qu’une collision dans une table de hachage ?

9. Quelle est la principale difficulté liée à la conception d’une fonction de hachage pour une table de hachage ?

10. Quelle technique est couramment utilisée pour résoudre les collisions dans une table de hachage ?

Vous pourrez aussi aimer

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

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

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

Laisser un commentaire Annuler la réponse