QCM : Introduction aux algorithmes de tri et leur complexité — 9 questions

Questions et réponses du QCM

1. Quelle est la définition précise du tri par sélection en algorithmique de tri?

C’est un algorithme qui trie en déplaçant chaque élément vers sa position correcte en décalant les autres éléments.
C’est un algorithme qui consiste à parcourir le tableau pour trouver le minimum dans la partie non triée, puis à l’échanger avec l’élément en début de cette partie, et à répéter jusqu’à ce que tout soit trié.
C’est un algorithme qui construit un tableau trié en insérant chaque élément à sa place en décalant les autres.
C’est un algorithme qui trie en comparant chaque élément avec tous les autres et en échangeant si nécessaire, sans chercher de minimum.

C’est un algorithme qui consiste à parcourir le tableau pour trouver le minimum dans la partie non triée, puis à l’échanger avec l’élément en début de cette partie, et à répéter jusqu’à ce que tout soit trié.

Explication

Le tri par sélection fonctionne en sélectionnant à chaque étape le plus petit élément du sous-tableau non trié, puis en l’échangeant avec l’élément en début de cette sous-partie, et en répétant ce processus jusqu’à ce que le tableau soit entièrement trié.

2. Quelle est la principale opération effectuée dans l'algorithme de tri par sélection ?

Trouver le maximum dans le sous-tableau non trié.
Trouver le minimum dans le sous-tableau non trié.
Insérer un élément dans la partie déjà triée.
Décaler les éléments pour faire de la place.

Trouver le minimum dans le sous-tableau non trié.

Explication

Le tri par sélection consiste à identifier le minimum dans la partie non triée pour le placer au début, ce qui est différent de trouver le maximum ou faire des décalages.

3. Quel est le rôle principal du tri par insertion et décalages dans l'organisation d'un tableau?

Réorganiser le tableau en échangeant des éléments aléatoires
Diviser le tableau en sous-parties pour les trier séparément
Sélectionner le plus petit élément à chaque étape
Construire un tableau trié en insérant chaque élément à sa place, en décalant les autres

Construire un tableau trié en insérant chaque élément à sa place, en décalant les autres

Explication

Le tri par insertion construit le tableau trié en insérant chaque élément à sa position correcte dans la partie déjà triée, en décalant les éléments plus grands vers la droite pour faire de la place.

4. Quelle est la complexité en temps du tri par sélection dans son pire cas ?

O(n)
O(n log n)
O(n²)
O(2^n)

O(n²)

Explication

Le tri par sélection a une complexité en O(n²) dans le pire cas, une caractéristique classique des algorithmes de tri simples comme celui-là.

5. En quoi le tri par sélection et le tri par insertion diffèrent-ils ou se ressemblent-ils dans leur principe de fonctionnement ?

Le tri par sélection trouve le minimum et l’échange, tandis que le tri par insertion insère chaque élément à sa place en décalant.
Le tri par sélection trie en divisant le tableau en sous-parties, tandis que le tri par insertion trie en comparant chaque élément avec tous les autres.
Les deux algorithmes sélectionnent le maximum à chaque étape, mais le tri par insertion utilise une méthode différente de décalage.
Le tri par sélection et le tri par insertion utilisent tous deux la méthode de fusion pour trier efficacement.

Le tri par sélection trouve le minimum et l’échange, tandis que le tri par insertion insère chaque élément à sa place en décalant.

Explication

Le tri par sélection consiste à sélectionner le minimum dans la partie non triée et à l’échanger avec le début de cette partie, tandis que le tri par insertion construit le tableau trié en insérant chaque élément à sa position correcte en décalant les autres éléments. Leur principe diffère, mais leur complexité dans le pire cas est en O(n²).

6. Quelle caractéristique distingue principalement le tri par insertion ?

Il construit le tableau trié en insérant chaque élément à sa place.
Il utilise une recherche binaire pour trouver la position d'insertion.
Il fonctionne en divisant le tableau en sous-tableaux récursivement.
Il trie en comparant des paires d'éléments spécifiques.

Il construit le tableau trié en insérant chaque élément à sa place.

Explication

Le tri par insertion construit le tableau trié un élément à la fois, en insérant chaque nouvel élément à la bonne place dans la partie déjà triée.

7. Dans le contexte du tri par insertion, qu'est-ce qu'un décalage ?

Une opération de suppression d'un élément maladroitement placé.
Une opération de déplacement d'un ou plusieurs éléments pour faire de la place.
Une opération d'échange entre deux éléments.
Une étape pour inverser le sens du tri.

Une opération de déplacement d'un ou plusieurs éléments pour faire de la place.

Explication

Le décalage implique de déplacer plusieurs éléments pour insérer un nouvel élément à sa place, ce qui est une opération centrale dans le tri par insertion.

8. Quelle est la principale faiblesse du tri par sélection en termes de performance ?

Sa complexité en O(n log n) le rend peu efficace.
Il nécessite beaucoup d'échanges.
Sa complexité en O(n²) le rend inefficace pour de grands ensembles.
Il est difficile à implémenter.

Sa complexité en O(n²) le rend inefficace pour de grands ensembles.

Explication

Sa complexité en O(n²) pour les gros tableaux rend le tri par sélection inefficace comparé à des algorithmes plus rapides comme le tri rapide ou fusion.

9. Quel est le principal avantage pédagogique du tri par sélection ?

Sa simplicité d'implémentation et sa compréhension.
Sa performance remarquable pour de très grands tableaux.
Sa capacité à trier en temps logarithmique.
Son efficacité dans le pire cas.

Sa simplicité d'implémentation et sa compréhension.

Explication

Le tri par sélection est souvent utilisé pour l'apprentissage en raison de sa simplicité à comprendre et à coder, malgré sa faible performance sur de grands ensembles.

Révisez avec les flashcards

Mémorisez les réponses avec 10 flashcards sur Introduction aux algorithmes de tri et leur complexité.

Tri par sélection — principe ?

Trouve le minimum, échange avec début, répète.

Tri par sélection — principe?

Trouver le minimum, échanger en début, répéter.

Tri par insertion — mécanisme ?

Insère chaque élément à sa place en décalant.

Voir les flashcards →

Approfondir avec la fiche

Consultez la fiche de révision complète sur Introduction aux algorithmes de tri et leur complexité.

Voir la fiche →

Cours similaires

Introduction à l'Intelligence Artificielle Symbolique

Intelligence Artificielle

Introduction aux documents et sécurité en construction

Bases de données

Introduction à l'Informatique et IA

Introduction aux marchés publics et réglementations du bâtiment

Bases de données

Gestion des imprimantes Windows et PDF

Introduction aux bases de données relationnelles

Bases de données

Crée tes propres QCM

Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.

Générateur de QCM