Exercices par capacités · BTS
Dernière mise à jour : 21 juin 2026
On effectue une recherche séquentielle de la valeur 8 dans le tableau \(t = [5, 3, 8, 1, 9, 2]\) (indices à partir de 0). Indiquer les comparaisons effectuées et l'indice retourné.
On parcourt le tableau de gauche à droite :
3 comparaisons sont effectuées ; l'algorithme retourne l'indice 2.
On recherche la valeur 8 dans le tableau trié \(t = [1, 2, 3, 5, 8, 9]\) par recherche dichotomique. Détailler chaque étape (calcul du milieu, comparaison).
Le tableau a 6 éléments, indices 0 à 5.
2 comparaisons suffisent ; l'algorithme retourne l'indice 4.
On recherche la valeur 7 (absente) dans le tableau trié \(t = [1, 2, 3, 5, 8, 9]\) par dichotomie. Détailler les étapes et donner la valeur retournée.
La valeur n'a pas été trouvée : l'algorithme retourne -1.
Pour un tableau trié de \(n = 1\,000\,000\) éléments, comparer le nombre maximal de comparaisons d'une recherche séquentielle et d'une recherche dichotomique.
Recherche séquentielle : pire cas \(O(n)\), soit jusqu'à 1 000 000 comparaisons.
Recherche dichotomique : pire cas \(\lceil\log_2 n\rceil\). Or \(\log_2(10^6) \approx 19{,}9\), donc \(\lceil\log_2(10^6)\rceil = 20\). Soit au maximum 20 comparaisons.
La dichotomie est radicalement plus efficace, mais elle exige un tableau préalablement trié.
Dérouler la première passe du tri à bulles sur le tableau \([5, 3, 1, 4, 2]\). Indiquer chaque comparaison, l'échange éventuel et l'état du tableau à la fin de la passe.
On compare les éléments adjacents et on échange si le gauche est plus grand.
À la fin de la passe 1, le plus grand élément (5) est en dernière position : \([3, 1, 4, 2, \mathbf{5}]\).
Dérouler le tri par sélection sur \([4, 2, 7, 1]\). À chaque tour, indiquer le minimum sélectionné et l'état du tableau après échange.
Tableau trié : \([1, 2, 4, 7]\).
On applique l'algorithme de tri rapide (quicksort) au tableau \([3, 7, 1, 5]\) en choisissant le dernier élément comme pivot. Effectuer la première partition et donner l'indice final du pivot.
Pivot = dernier élément = 5. On place à gauche les éléments \(\leq 5\).
Le pivot 5 est à l'indice 2. À gauche : \([3, 1]\) (tous \(\leq 5\)) ; à droite : \([7]\). On trie ensuite récursivement chaque partie.
Compléter le tableau comparatif des complexités (pire cas) et indiquer si le tri est stable.
| Algorithme | Pire cas | Stable ? |
|---|---|---|
| Tri à bulles | ? | ? |
| Tri par sélection | ? | ? |
| Tri rapide | ? | ? |
| Tri fusion | ? | ? |
| Algorithme | Pire cas | Stable ? |
|---|---|---|
| Tri à bulles | \(O(n^2)\) | Oui |
| Tri par sélection | \(O(n^2)\) | Non |
| Tri rapide | \(O(n^2)\) | Non |
| Tri fusion | \(O(n\log n)\) | Oui |
Le tri rapide est \(O(n\log n)\) en moyenne mais \(O(n^2)\) au pire (mauvais choix de pivot). Le tri fusion garantit \(O(n\log n)\) dans tous les cas.
On effectue sur une pile (LIFO) initialement vide la séquence d'opérations : push(10), push(20), push(30), pop(), push(40), pop(). Donner la valeur retournée par chaque pop() et l'état final de la pile.
Dans une pile, c'est le dernier élément empilé qui est retiré en premier (LIFO).
État final de la pile : [10, 20] (sommet : 20).
On effectue sur une file (FIFO) initialement vide : enqueue("A1"), enqueue("A2"), enqueue("A3"), dequeue(), enqueue("A4"), dequeue(). Donner la valeur retournée par chaque dequeue() et l'état final de la file.
Dans une file, c'est le premier élément enfilé qui est retiré en premier (FIFO).
État final de la file : [A3, A4] (tête : A3).
On considère la fonction récursive de la factorielle :
def factorielle(n):
if n == 0:
return 1
return n * factorielle(n - 1)factorielle(4) et donner le résultat.n * factorielle(n-1) sur un problème plus petit.Résultat : \(4! = 24\).
La suite de Fibonacci est définie par \(F(0)=0\), \(F(1)=1\) et \(F(n) = F(n-1) + F(n-2)\).
Pour les tours de Hanoï, le nombre de déplacements nécessaires pour \(n\) disques est \(2^n - 1\).
Donner la complexité Big-O de chaque expression en ne gardant que le terme dominant :
On ne garde que le terme à croissance la plus rapide et on ignore les constantes.
Classer les complexités suivantes par ordre de croissance (de la plus lente à la plus rapide à croître) : \(O(n^2)\), \(O(1)\), \(O(n\log n)\), \(O(\log n)\), \(O(2^n)\), \(O(n)\).
Ordre croissant des complexités :
\(O(1) \ll O(\log n) \ll O(n) \ll O(n\log n) \ll O(n^2) \ll O(2^n)\).
\(O(1)\) (constante) croît le plus lentement, \(O(2^n)\) (exponentielle) le plus vite.
Justifier que la recherche dichotomique sur un tableau trié de taille \(n\) effectue au plus \(\lceil\log_2 n\rceil\) comparaisons.
À chaque comparaison, la taille du sous-tableau à explorer est divisée par 2. Après \(k\) étapes, cette taille vaut \(\dfrac{n}{2^k}\).
La recherche s'arrête lorsque \(\dfrac{n}{2^k} \leq 1\), c'est-à-dire \(2^k \geq n\), soit \(k \geq \log_2 n\).
Le nombre d'étapes est donc au plus \(\lceil\log_2 n\rceil\), d'où une complexité \(O(\log n)\).
Un algorithme parcourt un tableau de taille \(n\) avec deux boucles imbriquées (chaque boucle de 0 à \(n-1\)).
On distingue la complexité temporelle et la complexité spatiale. Pour le tri fusion et un tri en place (comme le tri par sélection), indiquer la complexité spatiale (mémoire supplémentaire) et expliquer la différence.
La complexité temporelle mesure le nombre d'opérations ; la complexité spatiale mesure la mémoire supplémentaire utilisée.
Le tri en place est préférable lorsque la mémoire est limitée, même si le tri fusion offre une meilleure garantie temporelle.