Тест: Introduction aux algorithmes de tri et leur complexité — 9 въпроса

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

A. C’est un algorithme qui trie en déplaçant chaque élément vers sa position correcte en décalant les autres éléments.

B. 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. C’est un algorithme qui construit un tableau trié en insérant chaque élément à sa place en décalant les autres.

D. 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.

Answer: (B)

Обяснение

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 ?

A. Trouver le maximum dans le sous-tableau non trié.

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

C. Insérer un élément dans la partie déjà triée.

D. Décaler les éléments pour faire de la place.

Answer: (B)

Обяснение

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?

A. Réorganiser le tableau en échangeant des éléments aléatoires

B. Diviser le tableau en sous-parties pour les trier séparément

C. Sélectionner le plus petit élément à chaque étape

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

Answer: (D)

Обяснение

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 ?

A. O(n)

B. O(n log n)

C. O(n²)

D. O(2^n)

Answer: (C)

Обяснение

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 ?

A. 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.

B. 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.

C. Les deux algorithmes sélectionnent le maximum à chaque étape, mais le tri par insertion utilise une méthode différente de décalage.

D. Le tri par sélection et le tri par insertion utilisent tous deux la méthode de fusion pour trier efficacement.

Answer: (A)

Обяснение

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 ?

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

B. Il utilise une recherche binaire pour trouver la position d'insertion.

C. Il fonctionne en divisant le tableau en sous-tableaux récursivement.

D. Il trie en comparant des paires d'éléments spécifiques.

Answer: (A)

Обяснение

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 ?

A. Une opération de suppression d'un élément maladroitement placé.

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

C. Une opération d'échange entre deux éléments.

D. Une étape pour inverser le sens du tri.

Answer: (B)

Обяснение

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 ?

A. Sa complexité en O(n log n) le rend peu efficace.

B. Il nécessite beaucoup d'échanges.

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

D. Il est difficile à implémenter.

Answer: (C)

Обяснение

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 ?

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

B. Sa performance remarquable pour de très grands tableaux.

C. Sa capacité à trier en temps logarithmique.

D. Son efficacité dans le pire cas.

Answer: (A)

Обяснение

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.