NSI.Algorithmes.Bases.Test.2

Pour pouvoir utiliser un algorithme de recherche par dichotomie dans une liste, quelle précondition doit être vraie ?

• la liste doit être triée

• la liste ne doit pas comporter de doublons

• la liste doit comporter uniquement des entiers positifs

• la liste doit être de longueur inférieure à 1024

Quelle est la valeur de c à la fin de l'exécution du code ci-dessus :

• 0

• 2

• 3

• 10

On exécute le code ci-dessus. Que vaut la variable S à la fin de l'exécution ?

• 1

• 8

• 18

• 3.6

La fonction maximum doit renvoyer la valeur maximale d'un tableau de nombres. Par quoi doit-on remplacer les pointillés pour qu'elle donne le résultat attendu ?

• while puis, sur la ligne suivante, maxi = maxi + 1

• if puis, sur la ligne suivante, maxi = maxi + 1

• while puis, sur la ligne suivante, maxi = T[i]

• if puis, sur la ligne suivante, maxi = T[i]

Qu'affiche le programme ci-dessus :

• vert

  rouge

• bleu

  jaune

• bleu

• vert

  jaune

Quelle est la valeur de X/m à la fin de l'exécution du code ci-dessus ?

• 2

• 2.2

• 10

• 22

Soit L une liste de n nombres réels (n entier naturel non nul). On considère l'algorithme ci-dessus, en langage Python, calculant la moyenne des éléments de L.

Si le nombre n de données double alors le temps d'exécution du script :

• reste le même

• double aussi

• est multiplié par n

• est multiplié par 4

Une liste de n éléments est triée. Si la recherche d'un élément dans la liste précédente nécessite y opérations, alors, si la liste comporte deux fois plus d'éléments, le nombre d'opérations nécessaires sera égal à :

• y²

• 2y

• y + 1

• Cela dépend du type des éléments

On considère une liste L. Que fait le programme ci-dessus ?

• il vérifie si l'élément x est bien dans la liste

• il compte le nombre d'occurrences de l'élément x dans la liste L

• il renvoie la somme des valeurs de la liste L

• il renvoie 1 si l'élément x est présent, sinon, il renvoie 0

On décide d'effectuer une recherche dans un tableau trié contenant 42000 valeurs. On procède par dichotomie. Le nombre maximal d'itérations de l'algorithme sera :

• 21000 car une recherche dichotomique divise le nombre de tests maximal par deux.

• 42000 car la valeur recherchée pourrait très bien être la dernière du tableau.

• 41999 car si on n'a pas trouvé l'élément recherché à l'avant-dernière position du tableau, il n'est plus utile d'effectuer de test pour la dernière position.

• 16 car à chaque itération, le nombre d'éléments à examiner est divisé par deux et que 2¹⁵ <= 42000 <= 2¹⁶