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

avril 7, 2025avril 7, 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 vous avez une complexité algorithme de O(n²) et que vous augmentez la taille des données de 10 fois, combien de fois la durée d’exécution va-t-elle augmenter ?

A 10 fois

B 100 fois

C 1000 fois

D 10000 fois

Si la complexité est O(n²), alors si la taille des données est multipliée par 10, la durée d’exécution sera multipliée par 10²=100.

2. Quelle est la complexité de l’algorithme de recherche dans une table de hachage (hash table) dans le meilleur des cas ?

A O(n)

B O(log n)

C O(1)

D O(n log n)

Dans une table de hachage idéale, l’accès à un élément est effectué en temps constant O(1), à condition qu’il n’y ait pas de collisions, ce qui est le cas dans le meilleur des cas.

3. Quelle est la structure de données qui est la mieux adaptée pour représenter un graphe non orienté ?

A Tableau

B Liste d’adjacence

C Liste chaînée

D Pile

La liste d’adjacence est une représentation efficace d’un graphe non orienté, où chaque sommet contient une liste de ses voisins. Elle permet de réduire l’espace nécessaire comparé à une matrice d’adjacence.

4. Si un algorithme a une complexité de O(n³), quel sera l’impact d’une augmentation de la taille de l’entrée de 2 fois ?

A La durée d’exécution sera multipliée par 2

B La durée d’exécution sera multipliée par 4

C La durée d’exécution sera multipliée par 8

D La durée d’exécution restera inchangée

Si la taille de l’entrée est multipliée par 2, la durée d’exécution d’un algorithme ayant une complexité de O(n³) sera multipliée par 2³=8.

5. Dans une table de hachage, qu’est-ce qu’un « collision » ?

A Lorsque deux éléments ont des valeurs de hachage différentes

B Lorsque deux éléments ont des valeurs de hachage identiques

C Lorsque l’élément recherché n’existe pas

D Lorsque l’élément est ajouté dans la table

Une collision se produit lorsque deux éléments ont la même valeur de hachage, ce qui conduit à un conflit pour savoir où stocker les éléments dans la table de hachage.

6. Quel est l’avantage principal d’un arbre AVL par rapport à un arbre binaire de recherche classique ?

A Il permet une recherche plus rapide

B Il permet d’ajouter des éléments plus rapidement

C Il occupe moins de mémoire

D Il garantit un équilibre automatique

Un arbre AVL est un arbre binaire de recherche auto-équilibré. Cela garantit que la différence de hauteur entre les sous-arbres d’un nœud donné est toujours inférieure ou égale à 1, assurant des performances optimales de recherche, insertion et suppression en O(log⁡ n).

7. Quel est l’inconvénient principal des listes chaînées par rapport aux tableaux ?

A Elles sont plus lentes pour accéder à des éléments par index

B Elles utilisent plus de mémoire en raison des pointeurs

C Elles sont difficiles à redimensionner

D Elles ne supportent pas l’insertion d’éléments

Chaque élément d’une liste chaînée nécessite un pointeur pour lier l’élément suivant, ce qui entraîne une utilisation de mémoire supplémentaire par rapport à un tableau.

8. Parmi les algorithmes suivants, lequel est un algorithme de tri stable ?

A Tri rapide

B Tri par sélection

C Tri à bulles

D Tri par tas (heap sort)

Un algorithme de tri stable est celui qui conserve l’ordre relatif des éléments égaux. Le tri à bulles est stable, car les éléments égaux conservent leur position relative après le tri. En revanche, le tri rapide et le tri par tas ne sont pas stables par défaut.

9. Quel est le meilleur algorithme pour trier un tableau de n éléments où n est très grand et les éléments sont presque triés ?

A Tri par insertion

B Tri rapide

C Tri par sélection

D Tri à bulles

Le tri par insertion est particulièrement efficace lorsque la liste est presque triée. Dans ce cas, la complexité peut se rapprocher de O(n), ce qui est optimal par rapport à d’autres algorithmes comme le tri rapide ou le tri à bulles dans ce scénario particulier.

10. Quelle est la complexité temporelle de l’algorithme de Dijkstra pour trouver le plus court chemin dans un graphe avec une représentation par matrice d’adjacence et l’utilisation d’une liste de priorité ?

A O(V²)

B O(E log V)

C O(V log V)

D O(V + E)

Lorsque le graphe est représenté par une matrice d’adjacence, l’algorithme de Dijkstra nécessite un temps de O(V²) pour rechercher tous les voisins d’un sommet à chaque itération. Ici, V est le nombre de sommets dans le graphe.

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

QCMs qui pourraient vous intéresser :

1. Si vous avez une complexité algorithme de O(n2) et que vous augmentez la taille des données de 10 fois, combien de fois la durée d’exécution va-t-elle augmenter ?

2. Quelle est la complexité de l’algorithme de recherche dans une table de hachage (hash table) dans le meilleur des cas ?

3. Quelle est la structure de données qui est la mieux adaptée pour représenter un graphe non orienté ?

4. Si un algorithme a une complexité de O(n3), quel sera l’impact d’une augmentation de la taille de l’entrée de 2 fois ?

5. Dans une table de hachage, qu’est-ce qu’un « collision » ?

6. Quel est l’avantage principal d’un arbre AVL par rapport à un arbre binaire de recherche classique ?

7. Quel est l’inconvénient principal des listes chaînées par rapport aux tableaux ?

8. Parmi les algorithmes suivants, lequel est un algorithme de tri stable ?

9. Quel est le meilleur algorithme pour trier un tableau de n éléments où n est très grand et les éléments sont presque triés ?

10. Quelle est la complexité temporelle de l’algorithme de Dijkstra pour trouver le plus court chemin dans un graphe avec une représentation par matrice d’adjacence et l’utilisation d’une liste de priorité ?

Vous pourrez aussi aimer

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

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

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

Laisser un commentaire Annuler la réponse

1. Si vous avez une complexité algorithme de O(n²) et que vous augmentez la taille des données de 10 fois, combien de fois la durée d’exécution va-t-elle augmenter ?

4. Si un algorithme a une complexité de O(n³), quel sera l’impact d’une augmentation de la taille de l’entrée de 2 fois ?