Algorithmes de recherche

mcq 1. En C, a quoi correspond la convention "NEANT" pour les indices de recherche ? debutant mcq 2. Combien de comparaisons pour premmin(x) quand |x| = 0 ? debutant truefalse 3. Pour un mot x de taille n > 0, premmin effectue exactement n-1 comparaisons. debutant mcq 4. Complexite temporelle de la recherche par dichotomie ? intermediaire mcq 5. Quel algorithme utilise un tableau des decalages ? intermediaire mcq 6. É 9.1 — En C, quel type et quelle valeur sont associés à la convention «NÉANT» pour les recherches en mémoire (tableaux)... debutant mcq 7. É 9.1 — Dans les fichiers, à quoi correspond le NÉANT ? debutant truefalse 8. É 9.1 — La comparaison supplémentaire dans l'algorithme «première occurrence (cas croissant)» peut être oubliée si l'on ... debutant truefalse 9. É 9.2 — Dans la recherche par dichotomie, l'invariant de boucle garantit que l'intervalle [j, k] contient potentiellemen... intermediaire mcq 10. É 9.2 — Dans la recherche par dichotomie, quel est le variant de boucle ? intermediaire mcq 11. É 9.3 — Dans l'algorithme de Horspool, quelle lettre du facteur courant détermine le décalage ? intermediaire fillblank 12. É 9.4 — Pour le tableau des décalages d[a]=1, d[E]=4, d[L]=3, d[Q]=2, d[U]=2, d[autre]=8, quel mot de 8 lettres pourrait... avance mcq 13. É 9.4 — Dans le tableau des décalages d'un mot x de longueur m, que vaut d[a] si la lettre a n'apparaît pas dans x (sauf... intermediaire mcq 14. É 9.6 — Pour calculer dern(a,x), l'indice de la dernière occurrence de a dans x, quel sens de parcours est optimal ? intermediaire mcq 15. B 9.9 — Si un mot x est ordonné (trié), comment calculer le nombre d'occurrences d'une lettre a efficacement ? intermediaire truefalse 16. B 9.9 — Dans un mot ordonné de taille 1 000 000, on peut compter les occurrences d'une lettre en moins de 42 comparaison... avance mcq 17. B 9.10 — Pour trouver la k-ième occurrence d'une lettre dans un mot quelconque, quelle est la complexité ? intermediaire

codage 1. Premiere occurrence du minimum debutant codage 2. Mot des occurrences debutant codage 3. Recherche dichotomique intermediaire codage 4. Dernière occurrence du minimum debutant codage 5. Nombre d'occurrences du minimum debutant codage 6. Recherche naïve — première occurrence intermediaire codage 7. Codage de strchr et strrchr intermediaire codage 8. Recherche Horspool avance codage 9. Codage de memcmp debutant