Quiz : algorithmes de seuil et de dichotomie en Terminale

Quiz

15 questions · correction immédiate · ton score reste sur ton appareil.

1. Que fait un algorithme de dichotomie à chaque étape de sa recherche ?

   Il parcourt un par un tous les éléments restantsIl coupe l'intervalle de recherche en deux et conserve une moitiéIl double la taille de l'intervalle de rechercheIl trie à nouveau tout le tableau
   Valider

2. La recherche dichotomique d'une valeur dans un tableau fonctionne sur un tableau dont les valeurs sont rangées dans un ordre quelconque.

   VraiFaux
   Valider

3. D'où vient le mot « dichotomie » ?

   Du latin pour « chercher vite »Du grec, avec l'idée de « en deux » et « couper »De l'arabe, avec l'idée de « calcul »Du nom d'un mathématicien du XIXe siècle
   Valider

4. Un tableau trié contient 64 éléments. On applique la dichotomie et on garde à chaque étape une moitié exactement. Combien d'éléments restent à explorer après 3 étapes ?

   Ta réponse éléments
   Valider

5. Quelle structure de boucle convient pour un algorithme de seuil, quand on ignore combien de tours seront nécessaires ?

   Une boucle for avec un nombre de tours fixé à l'avanceUne boucle while avec une condition d'arrêtAucune boucle, une simple instruction conditionnelleUne boucle for qui ne s'arrête jamais
   Valider

6. On définit $u_n = 2^n$. On cherche le plus petit entier $n$ tel que $u_n > 1000$. Que vaut $n$ ?

   Ta réponse
   Valider

7. Soit la suite définie par $u_0 = 100$ et $u_{n+1} = 0{,}9\,u_n$. Quel est le plus petit entier $n$ tel que $u_n < 50$ ?

   Ta réponse
   Valider

8. Observe cet algorithme :

   u = 1
   n = 0
   while u <= 100:
       u = 2 * u
       n = n + 1
   

   Quelle est la valeur de n à la fin ?

   Ta réponse
   Valider

9. Dans l'algorithme précédent, on remplace while u <= 100 par while u < 100. Pour la même suite $2^n$, que change ce remplacement ?

   Rien, les deux conditions donnent toujours le même résultatLe résultat peut changer quand la suite atteint exactement le seuilLa boucle ne s'arrête plus jamaisL'algorithme calcule alors un terme de rang négatif
   Valider

10. Une liste triée de 1000 éléments est explorée par dichotomie. On garde la plus grande moitié à chaque coupure (en arrondissant vers le haut). Au bout de combien de coupures au plus reste-t-il un seul élément ?

    Ta réponse coupures
    Valider

11. La recherche linéaire parcourt la liste élément par élément. Quand on double la longueur de la liste, son temps de recherche double aussi.

    VraiFaux
    Valider

12. On cherche la valeur 14 dans le tableau trié [2, 5, 8, 11, 14, 17, 20] par dichotomie. Les bornes de départ sont g = 0 et d = 6. Le milieu est m = 3 (valeur 11). Quelle borne faut-il modifier, et quelle est sa nouvelle valeur ?

    d devient 2g devient 4g devient 3d devient 4
    Valider

13. Dans une dichotomie, on remplace par erreur g = m + 1 par g = m. Quel risque principal cela crée-t-il ?

    L'algorithme renvoie toujours la première caseLes bornes peuvent cesser d'évoluer et la boucle ne s'arrête plusLe tableau est trié automatiquementL'algorithme devient plus rapide
    Valider

14. Quelles affirmations sont correctes ? (plusieurs réponses possibles)

    Plusieurs réponses possibles.

    La dichotomie élimine une moitié de l'intervalle à chaque étapeUn algorithme de seuil s'arrête dès que la condition de la boucle devient fausseLa dichotomie fonctionne sur un tableau non triéUn seuil se programme toujours avec une boucle for
    Valider

15. On cherche le plus petit rang $n$ tel que $u_n \geq 500$, où $u_0 = 5$ et $u_{n+1} = u_n + 12$. Que vaut $n$ ?

    Ta réponse
    Valider