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

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. Quelle est la complexité de la recherche dans une liste chaînée ?

A O(1)

B O(log n)

C O(n)

D O(n²)

Dans une liste chaînée, il n’est pas possible d’accéder directement à un élément par index, donc la recherche nécessite de parcourir les éléments un par un, ce qui donne une complexité en O(n).

2. Quel algorithme utilise la stratégie « diviser pour régner » ?

A Tri à bulles

B Tri par insertion

C Tri rapide (QuickSort)

D Tri par sélection

Le tri rapide utilise la stratégie « diviser pour régner », où il divise récursivement le tableau en sous-ensembles et trie ces sous-ensembles indépendamment avant de les combiner.

3. Quel est le rôle d’un algorithme de compression de données ?

A Réduire l’espace mémoire nécessaire pour stocker les données

B Améliorer la vitesse de traitement des données

C Augmenter la taille des données

D Diviser les données en plusieurs parties

L’algorithme de compression de données réduit l’espace mémoire nécessaire pour stocker les données, ce qui est utile pour économiser de la bande passante ou réduire les coûts de stockage.

4. Quelle est la structure de données la plus efficace pour effectuer des opérations d’insertion et de suppression dans les deux sens (début et fin) ?

A Pile

B File

C Arbre binaire

D Liste doublement chaînée

Une liste doublement chaînée permet une insertion et une suppression efficaces à la fois au début et à la fin de la liste, car chaque élément contient un pointeur vers son précédent et son suivant, ce qui rend ces opérations en O(1).

5. Quelle structure de données est idéale pour implémenter un algorithme de parcours en largeur dans un graphe ?

A Pile

B File

C Tableau

D Liste chaînée

Lors d’un parcours en largeur (BFS), on explore d’abord tous les voisins d’un sommet avant de passer aux sommets suivants. Une file (FIFO) est idéale pour garantir cet ordre.

6. Dans un algorithme de tri par fusion (Merge Sort), comment les sous-tableaux sont-ils fusionnés ?

A Les éléments sont insérés dans un tableau temporaire trié

B Les éléments sont échangés avec un tableau auxiliaire

C Les sous-tableaux sont combinés sans tri préalable

D Un seul sous-tableau est ajouté à la fois dans le tableau final

Dans l’algorithme de tri par fusion, les sous-tableaux sont fusionnés de manière triée dans un tableau temporaire. Cette opération est effectuée récursivement.

7. Quelle est la complexité temporelle de l’algorithme de tri par tas (Heap Sort) ?

A O(n log n)

B O(n)

C O(n²)

D O(log n)

Le tri par tas a une complexité de O(n log ⁡n). Il construit d’abord un tas, puis effectue une série d’extractions du maximum (ou minimum) et les place dans l’ordre approprié.

8. Quelle est la principale caractéristique d’un graphe orienté ?

A Chaque arête a une direction

B Les sommets sont connectés par des arêtes sans direction spécifique

C Les sommets ne peuvent être reliés que par des arcs

D Les arêtes ont des poids associés

Dans un graphe orienté, chaque arête a une direction spécifique, indiquant une relation unidirectionnelle entre deux sommets. Cela contraste avec un graphe non orienté où les arêtes n’ont pas de direction.

9. Dans un arbre binaire de recherche (BST), quelle est la propriété fondamentale pour que l’arbre soit valide ?

A Les valeurs dans le sous-arbre droit de chaque nœud doivent être plus petites que la valeur du nœud

B Les valeurs dans le sous-arbre gauche de chaque nœud doivent être plus grandes que la valeur du nœud

C La valeur d’un nœud doit être égale à la somme des valeurs de ses sous-arbres

D Chaque nœud doit avoir exactement deux enfants

Dans un arbre binaire de recherche (BST), la propriété fondamentale est que toutes les valeurs dans le sous-arbre gauche d’un nœud sont inférieures à la valeur du nœud, et toutes les valeurs dans le sous-arbre droit sont supérieures à la valeur du nœud.

10. Quelle est la complexité en temps de l’algorithme de recherche dichotomique dans un tableau trié ?

A O(n)

B O(log n)

C O(n log n)

D O(n²)

La recherche dichotomique (ou recherche binaire) divise l’espace de recherche en deux parties à chaque étape. Ainsi, sa complexité est logarithmique, O(log⁡ n).

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

QCMs qui pourraient vous intéresser :

1. Quelle est la complexité de la recherche dans une liste chaînée ?

2. Quel algorithme utilise la stratégie « diviser pour régner » ?

3. Quel est le rôle d’un algorithme de compression de données ?

4. Quelle est la structure de données la plus efficace pour effectuer des opérations d’insertion et de suppression dans les deux sens (début et fin) ?

5. Quelle structure de données est idéale pour implémenter un algorithme de parcours en largeur dans un graphe ?

6. Dans un algorithme de tri par fusion (Merge Sort), comment les sous-tableaux sont-ils fusionnés ?

7. Quelle est la complexité temporelle de l’algorithme de tri par tas (Heap Sort) ?

8. Quelle est la principale caractéristique d’un graphe orienté ?

9. Dans un arbre binaire de recherche (BST), quelle est la propriété fondamentale pour que l’arbre soit valide ?

10. Quelle est la complexité en temps de l’algorithme de recherche dichotomique dans un tableau trié ?

Vous pourrez aussi aimer

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

QCM Algorithmes – Notions de base – Partie 2

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

Laisser un commentaire Annuler la réponse