NSI.Algorithmes.Bases

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

Quel code parmi les quatre proposés ci-dessous s'exécute-t-il en un temps linéaire en n ?

• 
• 
• 
• Aucune des trois propositions ci-dessus.

Un algorithme de calcul de moyenne est implémenté de la façon suivante (voir image). Que vaut la variable t ?

• C'est le dernier nombre de la la liste.

• C'est la moyenne des nombres de la liste.

• C'est la somme des nombres de la liste.

• C'est le plus grand nombre de la liste.

Dans l'algorithme ci-dessus, le mot 'hello' s'affichera :

• 2 fois

• n fois

• 2n fois

• n² fois

Voici la liste suivante :

L = [-5 , -2 , 1 , 0 , 10 , 72 , 105 , 210 , 300 , 321 ]

Pour rechercher si l'occurrence 10 est dans la liste on peut :

• exécuter une recherche dichotomique.

• exécuter seulement une recherche séquentielle.

• on ne peut pas car il y a des nombres négatives.

• on peut écrire : if L[10] == True

La fonction mystere suivante prend en argument un tableau d'entiers (voir image). A quelle condition renvoie-t-elle True ?

• si le tableau passé en argument contient des entiers tous identiques.

• si le tableau passé en argument est trié en ordre décroissant.

• si le tableau passé en argument est trié en ordre croissant.

• si le tableau passé en argument est une suite d'entiers consécutifs.

Soit L une liste de n nombres réels (n entier naturel non nul). On considère l'algorithme suivant, 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 de ce script :

• reste le même.

• double aussi.

• est multiplié par n.

• est multiplié par 4.

Soit L une liste et x une valeur.

Que renvoie la fonction compteur ci-dessus ?

• Le nombre d'occurrences de la valeur x dans la liste L.

• Elle renvoie x si x n'est pas dans la liste.

• Elle renvoie 1 si x est au moins une fois dans la liste.

• Elle renvoie le nombre d'éléments de la liste L.

On exécute le script ci-dessus :

Quelle est la valeur renvoyée par l'appel f([1,2,2,8,3,5,6,0,10],5) ?

• 2

• 3

• 4

• 5

Quelle valeur permet de compléter l’affirmation suivante : « Le nombre d’opérations nécessaires pour rechercher un élément séquentiellement dans un tableau de longueur n est de l’ordre de … » ?

• 1

• n

• 2n

• n²