QCM

Note

Les QCM 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 refaire des lectures des pages précédentes.

Cocher la ou les bonnes réponses.

QCM 1

On trie par insertion les éléments du tableau tab = [3,6,2,7,1,4].

Les étapes sont:

• [3,6,2,7,1,4], [1,3,6,2,7,4], [1,2,3,6,7,4], [1,2,3,6,7,4], [1,2,3,4,6,7],[1,2,3,4,6,7].
• [3,6,2,7,1,4], [3,6,2,7,1,4], [2,3,6,7,1,4], [2,3,6,7,1,4], [1,2,3,6,7,4], [1,2,3,4,6,7].
• [3,6,2,7,1,4], [3,2,6,7,1,4], [3,2,6,1,7,4], [3,2,6,1,4,7], [2,3,6,1,4,7], [3,2,1,6,4,7], [3,2,1,4,6,7], [2,3,1,4,6,7], [2,1,3,4,6,7], [1,2,3,4,6,7].
• [3,6,2,7,1,4], [2,3,6,7,1,4], [1,2,3,4,6,7]

Réponse

• [3,6,2,7,1,4], [1,3,6,2,7,4], [1,2,3,6,7,4], [1,2,3,6,7,4], [1,2,3,4,6,7],[1,2,3,4,6,7].
• [3,6,2,7,1,4], [3,6,2,7,1,4], [2,3,6,7,1,4], [2,3,6,7,1,4], [1,2,3,6,7,4], [1,2,3,4,6,7].
• [3,6,2,7,1,4], [3,2,6,7,1,4], [3,2,6,1,7,4], [3,2,6,1,4,7], [2,3,6,1,4,7], [3,2,1,6,4,7], [3,2,1,4,6,7], [2,3,1,4,6,7], [2,1,3,4,6,7], [1,2,3,4,6,7].
• [3,6,2,7,1,4], [2,3,6,7,1,4], [1,2,3,4,6,7]

QCM 2

On trie par insertion un tableau de taille n. Dans le pire cas, le nombre de comparaisons

• est une fonction du second degré en n (fonction de la forme $n \longmapsto an^2+bn+c$).
• est une fonction affine en n (fonction de la forme $n \longmapsto an+b$).
• est une fonction polynôme de degré 3 en n (fonction de la forme $n \longmapsto an^3+bn^2+cn+d)$.

Réponse

• est une fonction du second degré en n (fonction de la forme $n \longmapsto an^2+bn+c$).
• est une fonction affine en n (fonction de la forme $n \longmapsto an+b$).
• est une fonction polynôme de degré 3 en n (fonction de la forme $n \longmapsto an^3+bn^2+cn+d$).

QCM 3

On trie par insertion un tableau de taille n. Dans le meilleur des cas, le nombre de comparaisons

• est une fonction du second degré en n (fonction de la forme $n \longmapsto an^2+bn+c$).
• est une fonction affine en n (fonction de la forme $n \longmapsto an+b$).
• est une fonction polynôme de degré 3 en n (fonction de la forme $n \longmapsto an^3+bn^2+cn+d)$.

Réponse

• est une fonction du second degré en n (fonction de la forme $n \longmapsto an^2+bn+c$).
• est une fonction affine en n (fonction de la forme $n \longmapsto an+b$).
• est une fonction polynôme de degré 3 en n (fonction de la forme $n \longmapsto an^3+bn^2+cn+d$).

QCM 4

Le code suivant est celui d'une implémentation du tri par insertion.

Il manque une ligne (les pointillés):

def tri_insertion(tab):
    """
    tab -- liste d'entiers

    trie sur place tab suivant le principe du tri insertion
    """
    for i in range(1, len(tab)):
        v = tab[i]
        j = i
        while j > 0 and tab[j-1] > v:
            ............
            j -= 1
        tab[j] = v

La ligne manquante est:

• tab[j-1] = tab[j]
• tab[j+1] = tab[j]
• tab[j] = tab[j-1]
• tab[j] = tab[j+1]

Réponse

• tab[j-1] = tab[j]
• tab[j+1] = tab[j]
• tab[j] = tab[j-1]
• tab[j] = tab[j+1]

QCM 5

Avec la fonction suivante:

def tri_insertion(tab):
    """
    tab -- liste d'entiers

    trie sur place tab suivant le principe du tri insertion
    """
    for i in range(1, len(tab)):
        v = tab[i]
        j = i
        while j > 0 and tab[j-1] > v:
            tab[j] = tab[j-1]
            j -= 1
        tab[j] = v

et l'appel:

tri_insertion([7, 3, 8, 2, 1])

le nombre d'exécution de la ligne 11 (tab[j] = tab[j-1]) est:

• 7
• 8
• 6
• 9

Réponse

• 7
• 8
• 6
• 9

Avec i = 1, l'instruction de la ligne 11 est exécutée 1 fois.
Avec i = 2, l'instruction de la ligne 11 n'est pas exécutée.
Avec i = 3, l'instruction de la ligne 11 est exécutée 3 fois.
Avec i = 4, l'instruction de la ligne 11 est exécutée 4 fois.

QCM 6

Avec la fonction insertion suivante:

def insertion(tab, indice):
    """
    tab -- liste de chaîne de caractères
    """
    valeur = tab[indice] 
    j = indice
    while j > 0 and tab[j-1][0] > valeur[0]:
        tab[j] = tab[j-1]
        j -= 1
    tab[j] = valeur

et l'appel suivant:

A = ["Antoine", "Achille", "Fabrice", "Félicie", "Manu", "Marie", "Melvin", "Fabien"]
insertion(A, len(A)-1)

on obtient:

• A = ["Antoine", "Achille", "Fabrice", "Félicie", "Fabien", "Manu", "Marie", "Melvin"]
• A = ["Antoine", "Achille", "Fabrice", "Fabien", "Félicie", "Manu", "Marie", "Melvin"]
• A = ["Antoine", "Achille", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]

Réponse

• A = ["Antoine", "Achille", "Fabrice", "Félicie", "Fabien", "Manu", "Marie", "Melvin"]
• A = ["Antoine", "Achille", "Fabrice", "Fabien", "Félicie", "Manu", "Marie", "Melvin"]
• A = ["Antoine", "Achille", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]

QCM 7

Avec la fonction insertion suivante:

def insertion(tab, indice):
    """
    tab -- liste de chaîne de caractères
    """
    valeur = tab[indice] 
    j = indice
    while j > 0 and tab[j-1][0] >= valeur[0]:
        tab[j] = tab[j-1]
        j -= 1
    tab[j] = valeur

et l'appel suivant:

A = ["Antoine", "Achille", "Fabrice", "Félicie", "Manu", "Marie", "Melvin", "Fabien"]
insertion(A, len(A)-1)

on obtient:

• A = ["Antoine", "Achille", "Fabrice", "Félicie", "Fabien", "Manu", "Marie", "Melvin"]
• A = ["Antoine", "Achille", "Fabrice", "Fabien", "Félicie", "Manu", "Marie", "Melvin"]
• A = ["Antoine", "Achille", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]

Réponse

• A = ["Antoine", "Achille", "Fabrice", "Félicie", "Fabien", "Manu", "Marie", "Melvin"]
• A = ["Antoine", "Achille", "Fabrice", "Fabien", "Félicie", "Manu", "Marie", "Melvin"]
• A = ["Antoine", "Achille", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]

QCM 8

Avec le code suivant:

def tri_insertion(tab):
    """
    tab -- liste d'entiers

    trie sur place tab suivant le principe du tri insertion
    """
    for i in range(1, len(tab)):
        v = tab[i]
        j = i
        while j > 0 and tab[j-1] > v:
            tab[j] = tab[j-1]
            j -= 1
            print(a)
        tab[j] = v

et l'appel:

a = [2,5, 1, 6, 3]
tri_insertion(a)

les affichages obtenus sont:

• [2, 5, 1, 6, 3]
  [2, 5, 5, 6, 3]
  [1, 2, 5, 6, 3]
  [1, 2, 5, 6, 6]
  

• [2, 5, 5, 6, 3]
  [2, 2, 5, 6, 3]
  [1, 2, 5, 6, 6]
  [1, 2, 5, 5, 6]
  

• [2, 5, 1, 6, 3]
  [2, 2, 5, 6, 3]
  [1, 2, 5, 6, 3]
  [1, 2, 5, 5, 6]
  

• [2, 5, 1, 6, 3]
  [2, 5, 1, 6, 3]
  [1, 2, 5, 6, 3]
  [1, 2, 5, 6, 3]
  

Réponse

• [2, 5, 1, 6, 3]
  [2, 5, 5, 6, 3]
  [1, 2, 5, 6, 3]
  [1, 2, 5, 6, 6]
  

• [2, 5, 5, 6, 3]
  [2, 2, 5, 6, 3]
  [1, 2, 5, 6, 6]
  [1, 2, 5, 5, 6]
  

• [2, 5, 1, 6, 3]
  [2, 2, 5, 6, 3]
  [1, 2, 5, 6, 3]
  [1, 2, 5, 5, 6]
  

• [2, 5, 1, 6, 3]
  [2, 5, 1, 6, 3]
  [1, 2, 5, 6, 3]
  [1, 2, 5, 6, 3]