Fiche d’exercices de Algorithmes et complexité avec corrigé

Qu'exige la recherche dichotomique de son entrée ?

1. ALe tableau ne doit contenir que des nombres positifs
2. BLe tableau ne doit pas avoir plus de 1000 éléments
3. CLa longueur du tableau doit être une puissance de deux
4. DLe tableau doit être trié

Quelle est la complexité temporelle dans le pire cas du tri par insertion ?

1. AO(n)
2. BO(n²)
3. CO(n log n)
4. DO(log n)

Qu'est-ce que la récursivité ?

1. AUn type de structure de données
2. BUne boucle qui ne se termine jamais
3. CUne fonction qui s'appelle elle-même sur des entrées plus petites
4. DUne méthode de tri

Que mesure l'analyse amortie ?

1. ALe coût espéré sur des entrées aléatoires
2. BLe coût de l'unique opération la plus chère, où qu'elle se trouve dans la suite
3. CLe coût moyen par opération sur une suite d'opérations de pire cas
4. DLe coût d'un algorithme sur la meilleure entrée

Pourquoi de nombreuses routines de tri des bibliothèques passent-elles au tri par insertion pour les très petits sous-tableaux ?

1. ALe tri par insertion est en O(n log n) dans le pire cas
2. BLes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
3. CLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
4. DLe tri par insertion utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées

Quelle est la complexité temporelle de : pour i = 1 à n : pour j = 1 à i : faire un travail O(1) ?

1. AO(n³)
2. BO(n log n)
3. CO(n²)
4. DO(n)

Pourquoi la recherche dichotomique ne s'exécute-t-elle pas en O(log n) sur une liste simplement chaînée ?

1. ALes listes chaînées ne peuvent pas être triées
2. BLa recherche dichotomique nécessite au moins deux fois plus de mémoire
3. CLes comparaisons sur les nœuds d'une liste chaînée sont plus lentes
4. DAtteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice

Quel algorithme trouve un arbre couvrant de poids minimal en ajoutant de façon répétée l'arête la moins coûteuse qui ne forme pas de cycle ?

1. AFloyd-Warshall
2. BL'algorithme de Dijkstra
3. CL'algorithme de Kruskal
4. DL'algorithme de Prim à partir d'un seul nœud