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

Fiche d’exercices de Algorithmes et complexité gratuite et imprimable : 8 exercices, du niveau facile au niveau examen, avec corrigé. Imprimez-la ou enregistrez-la en PDF.

Nouvelle ficheS’entraîner en ligne avec indices

Pour les enseignants : gratuite à imprimer, copier et utiliser en classe. Chaque nouvelle fiche a de nouvelles valeurs et son propre corrigé. Un lien vers ExamProblems sur la page de votre cours est apprécié.

Nom: ____________________   Date: ____________

1.Facile

Quelle est la complexité temporelle de la recherche de la plus grande valeur dans un tableau non trié de n nombres ?

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

Quelle notation décrit une borne supérieure de la croissance ?

  1. AGrand Oméga (Big Omega)
  2. BGrand Thêta (Big Theta)
  3. CPetit oméga (little omega)
  4. DGrand O (Big O)
3.Facile

Laquelle de ces fonctions croît le plus lentement quand n devient grand ?

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

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

  1. ALes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
  2. BLe tri par insertion est en O(n log n) dans le pire cas
  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
5.Moyen

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
6.Moyen

Quel algorithme trouve les plus courts chemins depuis une source dans un graphe dont les poids des arêtes sont positifs ou nuls ?

  1. ABellman-Ford est nécessaire dans tous les cas
  2. BLe parcours en profondeur (DFS)
  3. CL'algorithme de Kruskal
  4. DL'algorithme de Dijkstra
7.Difficile

Quelle technique donne au tri rapide un temps d'exécution espéré en O(n log n) pour toute entrée ?

  1. ATrier l'entrée avant d'exécuter le tri rapide
  2. BN'utiliser la récursivité que sur la partie gauche
  3. CToujours choisir le premier élément
  4. DChoisir le pivot uniformément au hasard
8.Difficile

L'algorithme de programmation dynamique de Held-Karp résout exactement le problème du voyageur de commerce. Quel est son temps d'exécution pour n villes ?

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

Corrigé

  1. 1. D · O(n)
  2. 2. D · Grand O (Big O)
  3. 3. C · O(log n)
  4. 4. C · Le tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
  5. 5. C · Le coût moyen par opération sur une suite d'opérations de pire cas
  6. 6. D · L'algorithme de Dijkstra
  7. 7. D · Choisir le pivot uniformément au hasard
  8. 8. D · O(n² 2ⁿ)

Corrigés complets pas à pas : entraînez-vous sur ce thème sur examproblems.com.