QCM☘

Rappel

Les questions ci-dessous sont là pour vous aider à contrôler ce que vous avez retenu.
Si vous ne répondez pas à toutes les questions sans hésitation, c'est sans doute qu'il faut retravailler les pages précédentes.

Pour chaque question, il faut trouver la (ou les) bonne(s) réponse(s).

QCM 1☘

Avec un algorithme de recherche dichotomique, combien d'étapes sont nécessaires pour déterminer que 35 est présent dans le tableau [1, 7, 12, 16, 18, 20, 24, 28, 35, 43, 69] ?

1
2
9
11

Réponse

1
2
9
11

Je vous laisse chercher...

QCM 2☘

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

Le tableau ne doit pas comporter de doublons.
Le tableau doit comporter uniquement des entiers positifs.
Le tableau doit être trié.
La longueur du tableau doit être une puissance de 2.

Réponse

Le tableau ne doit pas comporter de doublons.
Le tableau doit comporter uniquement des entiers positifs.
Le tableau doit être trié.
La longueur du tableau doit être une puissance de 2.

QCM 3☘

On a effectué une recherche dichotomique dans un tableau (trié) de taille n (n > 100000). Cela demande $k$ exécutions du corps de la boucle de l'algorithme de recherche dans le pire des cas.

Pour un tableau de taille 2n, quel sera le nombre d'exécutions dans le pire des cas ?

$k$
$k+1$
$2 k$
$k^2$

Réponse

$k$
$k+1$
$2 k$
$k^2$

Dans le principe de dichotomie, on divise par 2 la taille du tableau à chaque étape.
Avec un tableau de taille 2n, en une étape on est ramené à un tableau de taille n. Par rapport à un tableau de taille n, il n'y a donc qu'une seule étape en plus pour un tableau de taille 2n. Le nombre de passages dans la boucle est donc $k+1$ au pire cas.

QCM 4☘

On considère le code suivant:

def f(n):
    """
    n - int, entier positif ou nul
    """
    x = 1
    while x < n:
        x = 2*x
    return x

On s'intéresse au coût en termes de nombre d'opérations en fonction de l'entrée n.

Ce coût est similaire à celui d'une recherche dichotomique sur un tableau de taille n.
Ce coût est linéaire en n (c'est-à-dire presqu'une fonction affine de la variable n)
Ce coût est quadratique en n (c'est-à-dire presqu'une fonction du second degré de la variable n)
Ce coût est de l'ordre de √n.

Réponse

Ce coût est similaire à celui d'une recherche dichotomique sur un tableau de taille n.
Ce coût est linéaire en n (c'est-à-dire presqu'une fonction affine de la variable n)
Ce coût est quadratique en n (c'est-à-dire presqu'une fonction du second degré de la variable n)
Ce coût est de l'ordre de √n.

On pourrait réécrire le code comme suit:

def g(n):
    """
    n - int, entier positif ou nul
    """
    x = 1
    m = n
    while 1 < m:
        x = 2*x
        m = m//2
    return x

On divise par 2 la « taille » du problème, comme pour une recherche dichotomique.