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

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. Quel est l’inconvénient principal de l’algorithme de tri par sélection ?

A Il est instable

B Il a une complexité en temps élevée dans le pire des cas

C Il nécessite un espace mémoire supplémentaire

D Il n’est pas adapté pour des petites tailles de données

Le tri par sélection a une complexité de O(n²), ce qui le rend inefficace pour les grandes tailles de données, même s’il a l’avantage d’être simple à implémenter.

2. Dans un arbre binaire de recherche (BST), si l’élément recherché n’est pas trouvé, quel est le cas typique dans lequel la recherche est arrêtée ?

A Lorsqu’un nœud feuille est atteint

B Lorsqu’un nœud avec deux enfants est atteint

C Lorsqu’un nœud avec un seul enfant est atteint

D Lorsqu’un nœud avec une valeur égale est trouvé

Dans un arbre binaire de recherche, la recherche d’un élément s’arrête lorsqu’un nœud feuille est atteint, c’est-à-dire un nœud sans enfants, et que l’élément recherché n’a pas été trouvé dans ce chemin.

3. Quelle structure de données est la plus efficace pour implémenter une table de symboles avec des opérations de recherche, d’insertion et de suppression rapides ?

A Liste chaînée

B Tableau

C Arbre binaire de recherche

D Table de hachage

Les tables de hachage offrent des performances optimales avec une complexité moyenne de O(1) pour les opérations de recherche, d’insertion et de suppression, grâce à leur capacité à « hacher » les clés en indices uniques.

4. Qu’est-ce qu’un « heap » ou tas dans un algorithme de gestion de priorité ?

A Un arbre binaire de recherche

B Une pile (stack)

C Une structure de données qui maintient l’ordre de priorité entre les éléments

D Une liste triée

Un tas (heap) est une structure de données binaire qui est utilisée pour implémenter une file de priorité. Dans un tas min, l’élément avec la plus petite priorité se trouve à la racine, et dans un tas max, l’élément avec la plus grande priorité se trouve à la racine.

5. Quelle est la principale différence entre une file d’attente (queue) et une pile (stack) ?

A La pile suit la politique FIFO, tandis que la file d’attente suit la politique LIFO

B La pile suit la politique LIFO, tandis que la file d’attente suit la politique FIFO

C Les deux suivent la politique LIFO

D Les deux suivent la politique FIFO

Une pile (stack) utilise la politique LIFO (Last In, First Out), où le dernier élément inséré est le premier à être retiré. Une file d’attente (queue) utilise la politique FIFO (First In, First Out), où le premier élément inséré est le premier à être retiré.

6. Lors de l’implémentation d’un arbre binaire, quel est le rôle d’un nœud interne ?

A Il contient la valeur de l’arbre

B Il a exactement un enfant

C Il a deux enfants ou aucun

D Il n’est pas utilisé dans un arbre binaire

Un nœud interne dans un arbre binaire a généralement deux enfants (s’il n’est pas une feuille) ou aucun enfant. Il ne s’agit pas d’un nœud terminal, comme une feuille, mais d’un nœud qui a un ou deux enfants.

7. Quelle est la complexité temporelle de l’ajout d’un élément dans un tableau dynamique (comme un ArrayList en Java) ?

A O(1) dans tous les cas

B O(n) dans tous les cas

C O(1) dans le cas moyen, O(n) dans le pire des cas

D O(n log n)

Ajouter un élément à la fin d’un tableau dynamique est généralement effectué en O(1). Cependant, si le tableau atteint sa capacité maximale et doit être redimensionné, cela prend O(n), où n est le nombre d’éléments dans le tableau.

8. Quelle est la complexité en temps de l’algorithme de tri par insertion dans le pire des cas ?

A O(n)

B O(n log n)

C O(n²)

D O(log n)

Le tri par insertion a une complexité de O(n²) dans le pire des cas, lorsque la liste est complètement inversée et que chaque élément doit être comparé avec tous les précédents.

9. Quelle est la meilleure structure de données pour implémenter une recherche par clé dans une base de données non triée ?

A Tableau trié

B Table de hachage

C Liste chaînée

D Arbre binaire de recherche

Une table de hachage permet de rechercher une clé en temps constant, O(1), dans le meilleur des cas, ce qui la rend optimale pour ce genre de recherche.

10. Quel est l’avantage principal d’un arbre B (B-tree) par rapport à un arbre binaire de recherche (BST) ?

A Il est plus facile à implémenter

B Il est plus rapide pour les petites bases de données

C Il est auto-équilibré et peut stocker plusieurs éléments dans un nœud

D Il nécessite moins d’espace mémoire

L’arbre B est un arbre équilibré qui peut contenir plusieurs éléments dans chaque nœud, ce qui réduit le nombre de niveaux et améliore l’efficacité des opérations d’insertion et de recherche sur de grandes bases de données.

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

QCMs qui pourraient vous intéresser :

1. Quel est l’inconvénient principal de l’algorithme de tri par sélection ?

2. Dans un arbre binaire de recherche (BST), si l’élément recherché n’est pas trouvé, quel est le cas typique dans lequel la recherche est arrêtée ?

3. Quelle structure de données est la plus efficace pour implémenter une table de symboles avec des opérations de recherche, d’insertion et de suppression rapides ?

4. Qu’est-ce qu’un « heap » ou tas dans un algorithme de gestion de priorité ?

5. Quelle est la principale différence entre une file d’attente (queue) et une pile (stack) ?

6. Lors de l’implémentation d’un arbre binaire, quel est le rôle d’un nœud interne ?

7. Quelle est la complexité temporelle de l’ajout d’un élément dans un tableau dynamique (comme un ArrayList en Java) ?

8. Quelle est la complexité en temps de l’algorithme de tri par insertion dans le pire des cas ?

9. Quelle est la meilleure structure de données pour implémenter une recherche par clé dans une base de données non triée ?

10. Quel est l’avantage principal d’un arbre B (B-tree) par rapport à un arbre binaire de recherche (BST) ?

Vous pourrez aussi aimer

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

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

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

Laisser un commentaire Annuler la réponse