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

Que décrit le temps d'exécution dans le pire cas d'un algorithme ?

  1. ALe temps sur un ordinateur lent
  2. BLe temps espéré sur une entrée aléatoire de taille n
  3. CLe temps maximal sur toutes les entrées de taille n
  4. DLe temps sur la plus petite entrée
2.Facile

Un algorithme en O(n²) prend 1 seconde pour n = 1000. Combien de temps prend-il environ pour n = 2000 ?

  1. A1 seconde
  2. B8 secondes
  3. C4 secondes
  4. D2 secondes
3.Facile

Le temps d'exécution d'un algorithme est O(n). Comment appelle-t-on cette croissance ?

  1. ALogarithmique
  2. BLinéaire
  3. CQuadratique
  4. DConstante
4.Moyen

La programmation dynamique est utile lorsqu'un problème présente :

  1. ADes sous-problèmes qui se chevauchent et une sous-structure optimale
  2. BUne seule boucle
  3. CUniquement des entrées aléatoires
  4. DAucun sous-problème, de sorte qu'il peut être résolu en une seule étape
5.Moyen

Quel énoncé sur une fonction récursive sans cas de base atteignable est correct ?

  1. AElle continue de s'appeler jusqu'au débordement de la pile d'appels
  2. BElle renvoie automatiquement 0
  3. CLe compilateur la transforme toujours en une boucle qui se termine sans danger
  4. DElle s'exécute en temps O(1)
6.Moyen

Quelle est la complexité temporelle de l'algorithme standard de programmation dynamique pour la plus longue sous-séquence commune de chaînes de longueurs m et n ?

  1. AO(2m+n)
  2. BO(m + n)
  3. CO(mn log n)
  4. DO(mn)
7.Difficile

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

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

Le tri par insertion s'exécute en O(n) sur une entrée triée. Cela contredit-il la borne inférieure Ω(n log n) des tris par comparaisons ?

  1. AOui, la borne inférieure est donc fausse
  2. BNon, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée
  3. CNon, car le tri par insertion n'est pas un tri par comparaisons
  4. DOui, mais seulement pour les tableaux de moins de 100 éléments

Corrigé

  1. 1. C · Le temps maximal sur toutes les entrées de taille n
  2. 2. C · 4 secondes
  3. 3. B · Linéaire
  4. 4. A · Des sous-problèmes qui se chevauchent et une sous-structure optimale
  5. 5. A · Elle continue de s'appeler jusqu'au débordement de la pile d'appels
  6. 6. D · O(mn)
  7. 7. D · Atteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice
  8. 8. B · Non, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée

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