Cours Stage - Recherche d'une occurence
QCM
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

L'énoncé

Répondre aux questions suivantes


Tu as obtenu le score de


Question 1

Que fait l'algorithme de recherche d'occurrence ? 

Il recherche le mot "occurrence" dans une liste.

Il teste la présence d'un élément dans un tableau. 

On cherche par balayage la présence d'une valeur dans un tableau grâce à l'algorithme. 

On résout une équation selon le principe d'occurrence.

Question 2

Par quel moyen vérifie-t-on la présence d'un élément ? 

Par balayage

On cherche par balayage la présence d'une valeur dans un tableau.

Par dichotomie 

Par la méthode des moindres carrés

Question 3

Que signifie un algorithme par balayage ? 

On nettoie la liste : en d'autres termes, on doit la trier avant d'effectuer le test. 

On vérifie successivement toutes les valeurs. 

On vérifie successivement toutes les valeurs que l'on compare à la valeur recherchée et l'on s'arrête dès lors que cette valeur apparait.  

On divise la liste en plein de branches, comme les poils d'un balais. 

Question 4

Quand l'algorithme s'arrête-il ? 

Toujours après avoir parcouru toute la liste.

Lorsque le nombre apparait pour la deuxième fois.

Lorsque le nombre apparait pour la première fois.

On vérifie successivement toutes les valeurs que l'on compare à la valeur recherchée et l'on s'arrête dès lors que cette valeur apparait.  

Question 5

Quel autre problème utilise la méthode du balayage ? 

La résolution de l'équation $f(x) = 0$

On peut résoudre par balayage l'équation $f(x) = 0$ où $f$ est une fonction continue et strictement monotone. 

Lors du tri d'une liste

Lors de la recherche par dichotomie

Question 6

L'algorithme affiche forcément un résultat.

Vrai

Faux

En effet, si le nombre $a$ n'appartient pas à la liste, alors l'algorithme n'affiche rien.

Question 7

Pourquoi impose-t-on la condition if $i<n$ ? 

Pour éviter de sortir de la liste

Car cela correspond au cas où la liste ne contient que la valeur $a$.

Car cela correspond au cas où la liste ne contient pas la valeur $a$.

En effet, lors de la dernière itération si $a$ n'appartient pas à la liste, $i$ prend la valeur $n$. La condition $i < n$ n'est donc plus rempli et on n'affiche aucun résultat : c'est normal $a$ n'appartient pas à la liste. 

Question 8

Quelle variable joue le rôle de variant dans l'algorithme ? 

$n$

C'est la taille de la liste donc $n$ ne varie pas. 

$i$

$i$ correspond à l'indice successif des éléments de la liste $L$.

$a$

C'est la valeur cherchée, qui ne varie donc pas. 

Question 9

Quel est le pire des cas ? 

Lorsque le soleil explosera.

Lorsque la liste ne contient que des $a$. 

Lorsque l'algorithme parcourt toute la liste.

Cela nécessite le plus grand nombre d'itérations.

Question 10

Quelle est la complexité de l'algorithme ? 

Linéaire

Dans le pire des cas, il y a $2n + 1$ opérations élémentaires: c'est la définition d'une complexité élémentaire. 

Quadratique

Assez facile