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

avril 8, 2025avril 8, 2025 Thomas Aucun commentaire

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. Si un algorithme a une complexité de O(n log⁡ n), cela signifie que :

A Le temps d’exécution augmente de manière linéaire avec la taille de l’entrée.

B Le temps d’exécution est constant pour toute taille d’entrée.

C Le temps d’exécution augmente de manière logarithmique.

D Le temps d’exécution augmente de manière plus rapide que linéaire mais moins rapide que quadratique.

Une complexité de O(n log⁡ n) est plus rapide que O(n²) mais plus lente que O(n). Cela se produit typiquement dans des algorithmes efficaces comme le tri fusion et le tri rapide.

2. Quelle est la complexité de l’algorithme de Dijkstra (avec une implémentation utilisant un tas binaire) pour un graphe avec n sommets et m arêtes ?

A O(n + m)

B O(n log⁡ n)

C O(n log⁡ m)

D O((n + m) log ⁡n)

L’algorithme de Dijkstra avec un tas binaire a une complexité de O((n + m) log ⁡n), où n est le nombre de sommets et m le nombre d’arêtes, car chaque opération d’extraction du minimum et de mise à jour d’un sommet peut être effectuée en temps O(log⁡ n).

3. Qu’est-ce qu’une liste chaînée ?

A Une structure de données où les éléments sont stockés dans des cases de mémoire contiguës.

B Une structure de données où chaque élément pointe vers le suivant.

C Une structure de données utilisée pour organiser les données en piles.

D Une structure de données qui permet une recherche binaire efficace.

Une liste chaînée est une structure de données dans laquelle chaque élément (ou « nœud ») contient deux parties: une donnée et un pointeur vers le nœud suivant. Ce n’est pas nécessairement une séquence contiguë en mémoire, contrairement à un tableau.

4. Qu’est-ce qu’une pile (Stack) ?

A Une structure de données qui permet d’ajouter et de supprimer des éléments dans l’ordre dans lequel ils ont été ajoutés.

B Une structure de données où les éléments sont ajoutés et retirés selon le principe LIFO (Last In, First Out).

C Une structure de données qui permet d’accéder directement à n’importe quel élément.

D Une structure de données qui permet une insertion rapide d’éléments à des indices spécifiques.

Une pile fonctionne selon le principe LIFO, ce qui signifie que le dernier élément ajouté est le premier à être retiré. Elle est utilisée dans de nombreuses situations, comme la gestion de la mémoire ou les algorithmes de parcours récursifs.

5. Dans un algorithme avec une complexité de O(2ⁿ), que se passe-t-il lorsque la taille d’entrée double ?

A Le temps d’exécution est divisé par deux.

B Le temps d’exécution double.

C Le temps d’exécution est multiplié par un facteur constant.

D Le temps d’exécution est multiplié par un facteur de 2ⁿ.

Dans un algorithme avec une complexité O(2ⁿ), lorsque la taille de l’entrée double, le temps d’exécution double également, car chaque augmentation de la taille entraîne une augmentation exponentielle du nombre d’opérations.

6. Quel algorithme utilise la technique de programmation dynamique pour résoudre un problème d’optimisation ?

A Tri fusion

B Algorithme de Dijkstra

C Algorithme de Bellman-Ford

D Résolution du problème du sac à dos

La programmation dynamique est utilisée pour résoudre des problèmes d’optimisation, comme le problème du sac à dos. Cet algorithme permet de trouver la meilleure solution en résolvant des sous-problèmes plus petits et en mémorisant leurs résultats pour éviter les recalculs.

7. Quelle est la complexité de la recherche dans un tableau non trié ?

A O(1)

B O(log n)

C O(n)

D O(n log n)

Dans un tableau non trié, la recherche d’un élément nécessite de parcourir chaque élément jusqu’à ce que l’élément recherché soit trouvé, ce qui donne une complexité de O(n).

8. Quelle est la complexité de la suppression d’un élément dans une pile (Stack) ?

A O(1)

B O(log n)

C O(n)

D O(n log n)

La suppression d’un élément dans une pile (par exemple, via l’opération pop) se fait en temps constant, O(1), car il suffit de retirer l’élément du dessus de la pile.

9. Qu’est-ce qu’un graphique pondéré ?

A Un graphe où chaque arête a une direction.

B Un graphe où les nœuds sont étiquetés avec des poids.

C Un graphe où chaque arête est associée à un poids (ou coût).

D Un graphe qui contient des cycles.

Un graphe pondéré est un graphe dans lequel chaque arête est associée à un poids, représentant souvent le coût ou la distance entre les nœuds. Cela permet d’appliquer des algorithmes comme Dijkstra ou Bellman-Ford pour trouver le chemin le plus court.

10. Quel est l’impact de la taille d’un problème sur un algorithme avec une complexité
O(n log⁡ n) ?

A Le temps d’exécution augmente de façon linéaire.

B Le temps d’exécution augmente de façon logarithmique.

C Le temps d’exécution augmente de façon exponentielle.

D Le temps d’exécution augmente plus rapidement qu’avec une complexité O(n), mais plus lentement qu’avec une complexité O(n²).

Une complexité de O(n log⁡ n) est considérée comme efficace par rapport à O(n²), et elle augmente plus rapidement que la complexité linéaire O(n), mais moins rapidement que la complexité quadratique O(n²).

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

QCMs qui pourraient vous intéresser :

1. Si un algorithme a une complexité de O(n log⁡ n), cela signifie que :

2. Quelle est la complexité de l’algorithme de Dijkstra (avec une implémentation utilisant un tas binaire) pour un graphe avec n sommets et m arêtes ?

3. Qu’est-ce qu’une liste chaînée ?

4. Qu’est-ce qu’une pile (Stack) ?

5. Dans un algorithme avec une complexité de O(2n), que se passe-t-il lorsque la taille d’entrée double ?

6. Quel algorithme utilise la technique de programmation dynamique pour résoudre un problème d’optimisation ?

7. Quelle est la complexité de la recherche dans un tableau non trié ?

8. Quelle est la complexité de la suppression d’un élément dans une pile (Stack) ?

9. Qu’est-ce qu’un graphique pondéré ?

10. Quel est l’impact de la taille d’un problème sur un algorithme avec une complexité O(n log⁡ n) ?

Vous pourrez aussi aimer

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

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

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

Laisser un commentaire Annuler la réponse

5. Dans un algorithme avec une complexité de O(2ⁿ), que se passe-t-il lorsque la taille d’entrée double ?

10. Quel est l’impact de la taille d’un problème sur un algorithme avec une complexité
O(n log⁡ n) ?