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 linéaire dans un tableau non trié de n éléments (pire cas) ?

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

Qu'est-ce qu'un algorithme ?

  1. AUne structure de données qui stocke des nombres
  2. BUn langage de programmation conçu pour écrire des formules mathématiques
  3. CTout programme informatique doté d'une interface graphique
  4. DUne suite finie d'étapes bien définies qui résout un problème
3.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)
4.Moyen

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

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

Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?

  1. AO(n²)
  2. BO(dn log k)
  3. CO(d(n + k))
  4. DO(n log n)
6.Moyen

Dans un tableau trié, vous cherchez deux éléments dont la somme vaut une cible en déplaçant un pointeur depuis chaque extrémité vers l'intérieur. Quelle est la complexité temporelle ?

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

Pourquoi une recherche dans une table de hachage est-elle en O(1) en moyenne mais en O(n) dans le pire cas ?

  1. AL'accès aux tableaux est en O(n)
  2. BDe nombreuses clés peuvent entrer en collision dans le même compartiment
  3. CLes fonctions de hachage sont lentes
  4. DLes clés doivent d'abord être triées
8.Difficile

Quelle est la différence entre un problème indécidable et un problème intraitable ?

  1. ALes problèmes intraitables ne peuvent être résolus par aucun algorithme, tandis que les indécidables demandent seulement un temps exponentiel
  2. BLes deux signifient que le problème n'a aucun algorithme
  3. CLes problèmes indécidables sont dans NP, tandis que les problèmes intraitables sont dans P
  4. DUn problème indécidable n'a aucun algorithme valable pour toutes les entrées ; un problème intraitable en a un, mais il est trop lent

Corrigé

  1. 1. B · O(n)
  2. 2. D · Une suite finie d'étapes bien définies qui résout un problème
  3. 3. D · Grand O (Big O)
  4. 4. C · Elle continue de s'appeler jusqu'au débordement de la pile d'appels
  5. 5. C · O(d(n + k))
  6. 6. D · O(n)
  7. 7. B · De nombreuses clés peuvent entrer en collision dans le même compartiment
  8. 8. D · Un problème indécidable n'a aucun algorithme valable pour toutes les entrées ; un problème intraitable en a un, mais il est trop lent

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