Aller au contenu

QCM
Les tris☘

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☘

Un tri par sélection sur un tableau de taille n présente une complexité :

  • constante
  • linéaire
  • quadratique
  • exponentielle
Réponse
  • constante
  • linéaire
  • quadratique - en O(n²)
  • exponentielle

QCM 2☘

On trie par insertion un tableau de taille n.
Dans le pire des cas, la complexité est :

  • constante
  • linéaire
  • quadratique
  • exponentielle
Réponse
  • constante
  • linéaire
  • quadratique - en O(n²)
  • exponentielle

QCM 3☘

On trie par insertion un tableau de taille n.
Dans le meilleur des cas, la complexité est :

  • constante
  • linéaire
  • quadratique
  • exponentielle
Réponse
  • constante
  • linéaire - en O(n)
  • quadratique
  • exponentielle

QCM 4☘

On considère le code suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def f(tab, debut, fin):
    m = tab[debut]  
    indice = debut  
    for i in range(debut+1, fin+1):
        if tab[i] < m:
            m = tab[i]
            indice = i
    return indice 

def triSelection(tab):
    for i in range(0, len(tab)-1):
        print(tab)
        im = f(tab, i, len(tab)-1)
        tab[i], tab[im] = tab[im], tab[i]

Quels seront les affichages obtenus dans la console suite à l'appel triSelection([3, 7, 2, 4, 1]) ?

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


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


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


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

Réponse

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


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


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


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

QCM 5☘

On considère le code suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def tri_insertion(tab):
    """
    tab - list, tableau d'entiers
    Sortie: None - trie le tableau tab suivant le principe du tri insertion
            (effet de bord)
    """
    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

Quels seront les affichages obtenus dans la console suite à l'appel triSelection([2, 5, 1, 6, 3]) ?

  • [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]

QCM 6☘

On a implémenté ci-dessous une version du tri par insertion dans laquelle il manque une ligne (signalée en pointillés) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def tri_insertion(tab):
    """
    tab - list, tableau d'entiers
    Sortie: None - trie le tableau tab suivant le principe du tri insertion
            (effet de bord)
    """
    for i in range(1, len(tab)):
        v = tab[i]
        j = i
        while j > 0 and tab[j-1] > v:
            ............
            j = 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 7☘

On considère le code suivant :

1
2
3
4
5
6
7
8
def rechercheIndiceMax(tab, debut, fin):
    m = tab[debut]  
    indice = debut  
    for i in range(debut+1, fin+1):
        if tab[i] > m:
            m = tab[i]
            indice = i
    return indice

On exécute ensuite les instructions suivantes dans la console : 

>>> tab = [3, 7, 8, 2, 1, 9, 5, 10]
>>> rechercheIndiceMax(tab, 1, 4)

Combien de comparaisons (ligne 5) seront effectuées ?

  • 1
  • 3
  • 4
  • 7
Réponse
  • 1
  • 3
  • 4
  • 7

QCM 8☘

On considère le code suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def tri_insertion(tab):
    """
    tab - list, tableau d'entiers
    Sortie: None - trie le tableau tab suivant le principe du tri insertion
            (effet de bord)
    """
    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 = j-1
        tab[j] = v

On exécute ensuite l'instruction suivante dans la console : 

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

Combien de fois l'affectation de la ligne 11 sera-t-elle effectuée ?

  • 6
  • 7
  • 8
  • 9
Réponse
  • 6
  • 7
  • 8
  • 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 9☘

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 10☘

On considère le code suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def rechercheIndiceMin(tab, debut, fin):
    m = tab[debut] 
    indice = debut 
    for i in range(debut+1, fin+1):
        if tab[i] < m:
            m = tab[i]
            indice = i
    return indice

def triSelection(tab):
    for i in range(0, len(tab)-1):
        im = rechercheIndiceMin(tab, i, len(tab)-1)
        tab[i], tab[im] = tab[im], tab[i]


# TESTS
if __name__ == '__main__":
    from random import randint
    A = [randint(-10,10) for i in range(10)]
    triSelection(A)

Combien de fois l'échange de la ligne 13 est-il effectué ?

  • 8 fois
  • 9 fois
  • 10 fois
  • 11 fois
Réponse
  • 8 fois
  • 9 fois
  • 10 fois
  • 11 fois

QCM 11☘

On définit la fonction insertion() suivante :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def insertion(tab, indice):
    """
    tab - list, tableau de chaînes de caractères
    """
    valeur = tab[indice] 
    j = indice
    while j > 0 and tab[j-1][0] > valeur[0]:
        tab[j] = tab[j-1]
        j = j-1
    tab[j] = valeur

On exécute ensuite les instructions suivantes : 

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

Quel sera l'affichage dans la console ?

  • ["Antoine", "Achille", "Fabrice", "Félicie", "Fabien", "Manu", "Marie", "Melvin"]
  • ["Antoine", "Achille", "Fabrice", "Fabien", "Félicie", "Manu", "Marie", "Melvin"]
  • ["Antoine", "Achille", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]
  • ["Achille", "Antoine", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]
Réponse
  • ["Antoine", "Achille", "Fabrice", "Félicie", "Fabien", "Manu", "Marie", "Melvin"]
  • ["Antoine", "Achille", "Fabrice", "Fabien", "Félicie", "Manu", "Marie", "Melvin"]
  • ["Antoine", "Achille", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]
  • ["Achille", "Antoine", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]

QCM 12☘

On définit la fonction insertion() suivante :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def insertion(tab, indice):
    """
    tab - list, tableau de chaînes de caractères
    """
    valeur = tab[indice] 
    j = indice
    while j > 0 and tab[j-1][0] >= valeur[0]:
        tab[j] = tab[j-1]
        j = j-1
    tab[j] = valeur

On exécute ensuite les instructions suivantes : 

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

Quel sera l'affichage dans la console ?

  • ["Antoine", "Achille", "Fabrice", "Félicie", "Fabien", "Manu", "Marie", "Melvin"]
  • ["Antoine", "Achille", "Fabrice", "Fabien", "Félicie", "Manu", "Marie", "Melvin"]
  • ["Antoine", "Achille", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]
  • ["Achille", "Antoine", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]
Réponse
  • ["Antoine", "Achille", "Fabrice", "Félicie", "Fabien", "Manu", "Marie", "Melvin"]
  • ["Antoine", "Achille", "Fabrice", "Fabien", "Félicie", "Manu", "Marie", "Melvin"]
  • ["Antoine", "Achille", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]
  • ["Achille", "Antoine", "Fabien", "Fabrice", "Félicie", "Manu", "Marie", "Melvin"]