Accueil › Devoirs › Bac SI

Exercice 1 : le tri Shell (7 pts)

Le tri Shell est un tri par insertion appliqué d'abord aux éléments éloignés de h cases, puis avec des pas de plus en plus petits, jusqu'au pas 1 qui est un tri par insertion normal. On utilise la suite de pas 1, 4, 13, 40, … (chaque pas vaut 3h + 1) : on commence par le plus grand pas de cette suite qui est inférieur à n, puis on divise h par 3 (division entière) après chaque passe.

• 1) Donner les pas utilisés pour n = 5 et pour n = 20 (1 pt).
• 2) Écrire la procédure TriShell(T, n) qui trie T dans l'ordre croissant (4 pts).
• 3) Écrire le programme qui lit n (2 ≤ n ≤ 100, saisie contrôlée) et les n entiers, affiche les pas utilisés sur une ligne, puis le tableau trié (2 pts).

Pour n = 5 et les valeurs 9, 4, 7, 1, 3, le programme affiche :

Pas : 4 1
1 3 4 7 9

Exercice 2 : le tri par comptage (6 pts)

Les notes d'un devoir sont des entiers de 0 à 20. Pour les trier, on compte combien de fois chaque note apparaît dans un tableau C de 21 cases (C[v] = nombre d'élèves qui ont la note v), puis on réécrit les notes dans l'ordre.

• 1) Écrire la procédure Compter(T, n, C) (1,5 pt).
• 2) Écrire la procédure TriComptage(T, n) qui trie T dans l'ordre croissant à l'aide de C (2,5 pts).
• 3) Écrire la fonction Frequente(C) qui renvoie la note la plus fréquente (la plus petite en cas d'égalité) (1 pt).
• 4) Écrire le programme qui lit n (1 ≤ n ≤ 40) puis les n notes (saisies contrôlées), affiche les notes triées et la note la plus fréquente (1 pt).

Pour n = 7 et les notes 12, 8, 15, 12, 8, 20, 12, le programme affiche :

8 8 12 12 12 15 20
Note la plus fréquente : 12

Exercice 3 : fusionner deux tableaux triés (7 pts)

Deux classes ont chacune un tableau de scores (entiers de 0 à 100) trié dans l'ordre croissant : A (n éléments) et B (m éléments). On veut obtenir un seul tableau C trié de n + m éléments, sans utiliser de tri.

• 1) Écrire la procédure RemplirTrie(T, n) qui lit n entiers entre 0 et 100, chacun supérieur ou égal au précédent (saisie contrôlée) (2 pts).
• 2) Écrire la procédure Fusion(A, n, B, m, C) (4 pts).
• 3) Écrire le programme principal qui lit n et m (1 ≤ n, m ≤ 30), les deux tableaux, et affiche C (1 pt).

Pour A = 40, 55, 70 et B = 45, 50, 76, 85, le programme affiche :

40 45 50 55 70 76 85

Correction détaillée

Sujet original écrit pour Mission Carthage, dans le style des devoirs de synthèse du 2e trimestre du bac Sciences de l'informatique (tris avancés).

Tout le programme : Bac Sciences de l'informatique · Revoir le cours · Tous les devoirs