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

Qu'est-ce que la mémoïsation ?

  1. AConvertir automatiquement une récursion en boucle équivalente, si bien qu'aucune pile d'appels n'est nécessaire
  2. BLibérer la mémoire après le retour d'une fonction
  3. CÉcrire des commentaires à côté de chaque ligne de code
  4. DStocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
2.Facile

Qu'est-ce qu'un algorithme ?

  1. ATout programme informatique doté d'une interface graphique
  2. BUne structure de données qui stocke des nombres
  3. CUn langage de programmation conçu pour écrire des formules mathématiques
  4. DUne suite finie d'étapes bien définies qui résout un problème
3.Facile

Quelle est la complexité temporelle du parcours en profondeur d'un graphe stocké sous forme de listes d'adjacence ?

  1. AO(V²)
  2. BO(E log V)
  3. CO(V × E)
  4. DO(V + E)
4.Moyen

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)
  3. CO(n log n)
  4. DO(n³)
5.Moyen

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 utilise moins de mémoire que tout autre algorithme de tri sur les grandes entrées
  2. BLe tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
  3. CLes algorithmes récursifs ne peuvent pas traiter les tableaux de moins de 10 éléments
  4. DLe tri par insertion est en O(n log n) dans le pire cas
6.Moyen

Quelle est la complexité temporelle de : pour i = 1 à n : (j = 1 ; tant que j < n : j = j × 2) ?

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

Que se passerait-il si quelqu'un trouvait un algorithme en temps polynomial pour un problème NP-complet ?

  1. ATous les algorithmes en temps exponentiel s'exécuteraient immédiatement en temps linéaire
  2. BLe problème de l'arrêt deviendrait décidable
  3. CSeul ce problème passerait dans P
  4. DTout problème de NP pourrait être résolu en temps polynomial, donc P = NP
8.Difficile

Quel est le temps d'exécution de l'algorithme de Dijkstra avec un tas binaire sur un graphe à V sommets et E arêtes ?

  1. AO(V + E)
  2. BO(V³)
  3. CO(V × E)
  4. DO((V + E) log V)

Corrigé

  1. 1. D · Stocker les résultats des appels de fonction pour répondre aux appels répétés depuis la mémoire
  2. 2. D · Une suite finie d'étapes bien définies qui résout un problème
  3. 3. D · O(V + E)
  4. 4. A · O(n²)
  5. 5. B · Le tri par insertion a peu de surcoût et est rapide sur les entrées petites ou presque triées
  6. 6. C · O(n log n)
  7. 7. D · Tout problème de NP pourrait être résolu en temps polynomial, donc P = NP
  8. 8. D · O((V + E) log V)

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