Quiz · Algorithmique
0/19 questions réussie
Connecte-toi pour persister tes réponses entre appareils.
1/2 · arbres-binaires-algos-c1
Quelle est la hauteur de l'arbre dessiné ci-dessus ?
2/2 · arbres-binaires-algos-c2
Quelle structure de données est essentielle au parcours en largeur ?
1/2 · graphes-parcours-c1
La version itérative de DFS utilise une…
2/2 · graphes-parcours-c2
DFS et BFS ont un coût en…
1/2 · diviser-pour-regner-c1
Pour T(n) = 2 T(n/2) + O(n), la complexité est…
2/2 · diviser-pour-regner-c2
Le tri fusion garantit un coût en O(n log n) dans le pire cas.
1/2 · programmation-dynamique-c1
Quelle est la complexité du rendu de monnaie tabulé ?
2/2 · programmation-dynamique-c2
Sans mémoïsation, le rendu de monnaie naïf est…
1/2 · recherche-textuelle-c1
Boyer-Moore compare le motif et le texte…
2/2 · recherche-textuelle-c2
Le BO demande-t-il la preuve du coût de Boyer-Moore ?
1/9 · te-algorithmique-1-q1
Sur un arbre binaire de recherche, le parcours qui affiche les valeurs dans l'ordre croissant est :
2/9 · te-algorithmique-1-q2
Quelle structure de données est utilisée par un parcours en largeur (BFS) ?
3/9 · te-algorithmique-1-q3
Pour le tri fusion, la récurrence est T(n)=2T(n/2)+O(n)T(n) = 2 T(n/2) + \mathcal(n)T(n)=2T(n/2)+O(n). Quel est le coût total ?
4/9 · te-algorithmique-1-q4
Le coût de DFS et BFS sur un graphe représenté par liste de successeurs est :
5/9 · te-algorithmique-1-q5
La programmation dynamique se distingue de « diviser pour régner » par :
6/9 · te-algorithmique-1-q6
L'algorithme de Boyer-Moore compare le motif et le texte de la fin vers le début, c'est-à-dire de droite à ______.
7/9 · te-algorithmique-1-q7
Quel est le coût asymptotique en pire cas du tri fusion (notation de Landau) ?
8/9 · te-algorithmique-1-q8
Ordonnez les étapes d'un algorithme « diviser pour régner » :
Glisser-déposer pour réordonner (ou utiliser les flèches).
- 1. Tester le cas de base et y répondre directement si applicable
- 2. Diviser le problème en sous-problèmes plus petits du même type
- 3. Résoudre chaque sous-problème par appel récursif
- 4. Combiner les sous-solutions en une solution globale
9/9 · te-algorithmique-1-q9
Ordonnez les étapes d'une recherche de motif par l'algorithme de Boyer-Moore :
Glisser-déposer pour réordonner (ou utiliser les flèches).
- 1. Prétraiter le motif pour construire la table du mauvais caractère
- 2. Aligner le motif sur le texte à la position courante
- 3. Comparer le motif et le texte de droite à gauche
- 4. En cas d'échec, décaler le motif selon la règle du mauvais caractère