Tris par insertion et par sélection : quiz de Première NSI

Quiz

14 questions · correction immédiate · ton score reste sur ton appareil.

1. Quelle phrase décrit correctement une étape du tri par sélection ?

   On cherche le minimum de la partie non triée, puis on le place en tête de cette partie.On prend l'élément suivant et on le glisse à sa place dans la partie déjà triée.On compare deux voisins et on les échange s'ils sont dans le mauvais ordre, jusqu'à la fin du tableau.On coupe le tableau en deux moitiés égales que l'on trie séparément.
   Valider

2. On applique le tri par sélection au tableau [7, 3, 9, 1]. Quel est le tableau après la première étape (minimum échangé avec la case d'indice 0) ?

   [1, 3, 9, 7][1, 7, 3, 9][3, 7, 9, 1][3, 1, 9, 7]
   Valider

3. On applique le tri par insertion au tableau [4, 2, 5, 1]. Quel est le tableau une fois les trois premières cases traitées (le 1 n'est pas encore inséré) ?

   [2, 4, 5, 1][1, 2, 4, 5][2, 4, 1, 5][4, 2, 5, 1]
   Valider

4. Combien de comparaisons le tri par sélection effectue-t-il pour trier un tableau de $n = 10$ éléments ?

   Ta réponse comparaisons
   Valider

5. Combien de comparaisons le tri par sélection effectue-t-il pour un tableau de $n = 6$ éléments déjà trié ?

   Ta réponse comparaisons
   Valider

6. Le tri par sélection est un tri en place.

   VraiFaux
   Valider

7. Le nombre de comparaisons du tri par sélection est plus petit quand le tableau est presque trié.

   VraiFaux
   Valider

8. Un tableau contient 5 valeurs. Quels sont ses indices en Python ?

   De 0 à 4De 1 à 5De 0 à 5De 1 à 4
   Valider

9. Parmi ces affirmations, lesquelles sont vraies ? (plusieurs réponses)

   Plusieurs réponses possibles.

   Le tri par insertion et le tri par sélection sont tous deux quadratiques dans le pire cas.Le tri par sélection effectue au plus un nombre linéaire d'échanges.Le tri par sélection est le plus efficace de tous les tris connus.Le tri par insertion est toujours plus lent que le tri par sélection.
   Valider

10. On considère ce code Python :

    def indice_min(t, i):
        m = i
        for j in range(i + 1, len(t)):
            if t[j] < t[m]:
                m = j
        return m
    

    Que renvoie indice_min([8, 5, 9, 2, 6], 1) ?

    3124
    Valider

11. Pour le tri par insertion, quelle propriété est vraie au début de l'étape où l'on traite la case d'indice $i$ ? (c'est un invariant de boucle)

    Les cases d'indices $0$ à $i-1$ sont triées par ordre croissant.Les cases d'indices $0$ à $i-1$ contiennent les $i$ plus petites valeurs du tableau entier.Les cases d'indices $i$ à $n-1$ sont triées.Le tableau entier est trié sauf la dernière case.
    Valider

12. Pour le tri par sélection, quel invariant est valable au début de l'étape $i$ ?

    Les $i$ premières cases sont triées et chacune de leurs valeurs est inférieure ou égale à toutes celles des cases suivantes.Les $i$ premières cases sont triées, mais elles peuvent contenir de grandes valeurs.Le minimum du tableau se trouve toujours en case $n-1$.Aucune case n'a encore été déplacée.
    Valider

13. On double la taille $n$ d'un tableau à trier avec un algorithme de coût quadratique. Par combien le temps d'exécution est-il à peu près multiplié ?

    428Il ne change pas
    Valider

14. Sur un tableau déjà trié, que peut-on dire de la comparaison entre l'insertion et la sélection ?

    L'insertion peut être nettement plus rapide, car elle n'a presque rien à déplacer.La sélection est plus rapide, car elle n'échange rien.Les deux font exactement le même nombre de comparaisons.Aucun des deux ne peut traiter un tableau déjà trié.
    Valider