Тест: Techniques de tri et recherche optimisée — 8 въпроса

1. Qu'est-ce que le tri par sélection ?

A. Une méthode de tri qui divise la liste en deux parties, trie chacune, puis fusionne.

B. Une méthode de tri qui utilise la récursion pour trier la liste en divisant en sous-listes plus petites.

C. Une méthode de tri qui consiste à sélectionner le plus grand élément et à l'échanger avec le dernier de la liste.

D. Une méthode de tri qui recherche, à chaque étape, le minimum dans une sous-liste non triée, puis échange cet élément avec celui en début de sous-liste.

Answer: (D)

Обяснение

Le tri par sélection consiste à rechercher, à chaque étape, le minimum dans la partie non triée de la liste, puis à l’échanger avec l’élément en début de cette sous-liste. Cette opération est répétée jusqu’à ce que la liste soit entièrement triée. La méthode trie en place en modifiant directement la liste.

2. Quelle est la complexité en termes de nombre d'opérations du tri par sélection, selon le contenu ?

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(log n)

Answer: (A)

Обяснение

La complexité du tri par sélection est en O(n^2) car il nécessite de parcourir la liste pour chaque élément afin de trouver le minimum, ce qui entraîne une croissance quadratique du nombre d'opérations.

3. Quel est le rôle principal du tri en place dans le processus de tri d'une liste ?

A. Permettre de trier la liste sans la modifier en utilisant une nouvelle structure

B. Utiliser une fonction de recherche pour localiser le minimum dans la liste

C. Créer une copie triée de la liste pour éviter de modifier l'originale

D. Modifier directement la liste originale en échangeant ses éléments

Answer: (D)

Обяснение

Le tri en place consiste à modifier directement la liste originale en échangeant ses éléments, ce qui évite la création d'une nouvelle structure et optimise l'utilisation de la mémoire.

4. Quand a été publié ou établi le principe que la recherche de couples proches peut être optimisée en utilisant une liste triée plutôt que la méthode naïve ?

A. Après la mise en évidence de la complexité en O(n²) de la méthode naïve, l'optimisation a été proposée dans des travaux de recherche en algorithmie dans les années 1980.

B. Ce principe a été développé dans le contexte de l'apprentissage automatique en 2010, pour améliorer la recherche de proches voisins.

C. L'idée a été introduite dans un manuel de programmation en 2000 comme une optimisation standard.

D. Ce principe a été formulé pour la première fois dans un article de 1995 sur l'optimisation des algorithmes de recherche.

Answer: (A)

Обяснение

L'optimisation basée sur le tri préalable pour réduire la complexité de la recherche de couples proches a été établie après avoir reconnu que la méthode naïve est en O(n²). Cette approche a été formalisée dans la littérature algorithmique dès les années 1980, lorsque l'on a commencé à exploiter la propriété des listes triées pour limiter le nombre de comparaisons.

5. En quoi la méthode de recherche naïve de couples proches diffère-t-elle ou ressemble-t-elle à l'algorithme de tri par sélection ?

A. Le tri par sélection est plus efficace que la recherche naïve pour de grandes listes.

B. Le tri par sélection ne modifie pas la liste, alors que la recherche naïve la modifie en échangeant des éléments.

C. Le tri par sélection trie la liste en place en utilisant la fonction mini, tandis que la recherche naïve compare toutes les paires sans tri préalable.

D. Les deux méthodes utilisent la fonction mini pour rechercher un minimum dans une sous-liste.

Answer: (C)

Обяснение

Le tri par sélection trie la liste en place en recherchant le minimum dans la sous-liste restante grâce à la fonction mini, puis en échangeant cet élément avec celui en début de sous-liste. La recherche naïve de couples proches, en revanche, compare toutes les paires possibles sans tri préalable, ce qui la rend moins efficace. La principale différence est que le tri en place modifie la liste en échangeant des éléments, tandis que la recherche naïve ne modifie pas la liste mais compare toutes les paires.

6. À qui est généralement attribuée la méthode de suppression des doublons dans une liste triée, en tant que pratique standard en informatique ?

A. À Alan Turing

B. À Donald Knuth

C. À Edsger Dijkstra

D. À la communauté de l'informatique comme une pratique standard

Answer: (D)

Обяснение

La suppression des doublons dans une liste triée est une opération standard en informatique, souvent enseignée comme une pratique courante ou une méthode classique, et n'est pas attribuée à un auteur précis. La réponse correcte reflète cette attribution à la communauté ou à une pratique standard.

7. Quelles sont les causes de la complexité élevée de l'algorithme de recherche naïve de couples proches dans une liste non triée ?

A. Le fait que tous les éléments soient identiques, ce qui complique la recherche

B. L'échange d'éléments dans le tri par sélection

C. L'utilisation de la fonction mini pour rechercher le minimum dans chaque sous-liste

D. L'absence de tri qui empêche de limiter le nombre de comparaisons aux éléments adjacents

Answer: (D)

Обяснение

La recherche naïve compare toutes les paires possibles dans une liste non triée, ce qui entraîne une complexité en O(n²). L'absence de tri empêche de réduire le nombre de comparaisons en limitant celles-ci aux éléments adjacents, contrairement à une liste triée où cette optimisation est possible.

8. Comment appliquer la recherche efficace pour optimiser le tri par sélection dans une liste ?

A. En supprimant tous les doublons avant de commencer le tri pour réduire le nombre de comparaisons

B. En parcourant la liste une seule fois en comparant chaque élément avec tous les autres

C. En triant la liste puis en utilisant une recherche binaire pour trouver rapidement chaque élément

D. En utilisant la fonction mini pour rechercher le minimum dans la sous-liste non triée à chaque étape

Answer: (D)

Обяснение

L'application de la recherche efficace dans le tri par sélection consiste à utiliser la fonction mini pour rechercher le minimum dans la sous-liste non triée à chaque étape, ce qui permet de réduire la complexité en évitant une recherche naïve exhaustive. La recherche binaire n'est pas adaptée ici car la liste n'est pas encore triée, et parcourir la liste en comparant chaque élément avec tous les autres reste une méthode naïve. La suppression des doublons ne concerne pas directement l'optimisation de la recherche du minimum dans le tri par sélection.