1.Facile
Qu'est-ce qu'un algorithme ?
- AUne suite finie d'étapes bien définies qui résout un problème
- BUne structure de données qui stocke des nombres
- CTout programme informatique doté d'une interface graphique
- DUn langage de programmation conçu pour écrire des formules mathématiques
2.Facile
Comment appelle-t-on une croissance en O(2ⁿ) ?
- ALogarithmique
- BLinéaire
- CExponentielle
- DPolynomiale
3.Facile
Un algorithme en O(n) prend 3 secondes pour n = 1 million. Combien de temps prend-il environ pour n = 2 millions ?
- A6 secondes
- B3 secondes
- C9 secondes
- D12 secondes
4.Moyen
Un algorithme glouton :
- AEssaie toutes les solutions possibles
- BDonne toujours la solution optimale
- CN'utilise que la récursivité
- DFait le meilleur choix local à chaque étape
5.Moyen
Quel algorithme de tri est stable ?
- ATri par tas
- BTri rapide (version en place habituelle)
- CTri par sélection (version habituelle)
- DTri fusion
6.Moyen
Quelle est la solution de la récurrence T(n) = T(n/2) + O(1) ?
- AO(1)
- BO(log n)
- CO(n)
- DO(n log n)
7.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 ?
- AO(V × E)
- BO(V³)
- CO(V + E)
- DO((V + E) log V)
8.Difficile
Comment se comparent n! et 2ⁿ pour n grand ?
- An! croît plus vite que 2ⁿ
- Bn! est O(n²)
- CIls croissent au même rythme
- D2ⁿ croît plus vite que n!
Corrigé
- 1. A · Une suite finie d'étapes bien définies qui résout un problème
- 2. C · Exponentielle
- 3. A · 6 secondes
- 4. D · Fait le meilleur choix local à chaque étape
- 5. D · Tri fusion
- 6. B · O(log n)
- 7. D · O((V + E) log V)
- 8. A · n! croît plus vite que 2ⁿ
Corrigés complets pas à pas : entraînez-vous sur ce thème sur examproblems.com.