Six questions courtes sur la recherche séquentielle.
1.Quel est le coût d’un accès indexé a[i] ?
2.Dans le pire cas (valeur absente, ou en dernière position), combien de comparaisons recherche(a, v) effectue-t-elle sur un tableau à n éléments ?
3.Pourquoi second_maximum initialise-t-il ses deux variables m1 et m2 à partir des deux premiers éléments du tableau, plutôt que d’un seul ?
4.Parmi les opérations suivantes sur un dictionnaire Python, lesquelles sont considérées à coût constant, dans le modèle « boîte noire » du cours ?
5.Quel est le coût total de comptage(a) sur un tableau à n éléments ?
6.Dans la démonstration de correction de maximum, que représente mk ?
Soit a = [8, 15, 3, 15, 42]. On appelle recherche(a, 15).
Dérouler l’exécution de l’algorithme du cours, en indiquant les comparaisons effectuées, puis donner la valeur renvoyée.
a[0] = 8 à 15 : différenta[1] = 15 à 15 : égal, on renvoie l’indice 1La fonction renvoie 1 (l’indice de la première occurrence de 15, même si 15 apparaît aussi à l’indice 3).
Soit a = [10, 4, 10, 7]. On appelle second_maximum(a).
Donner les valeurs initiales de m1 et m2.
a[0] = 10 \ge a[1] = 4, donc m1 = 10 et m2 = 4.
Comparer a[0] et a[1] pour déterminer lequel des deux initialise m1.
Dérouler les itérations restantes (i=2 puis i=3), en indiquant à chaque étape les valeurs de m1 et m2.
m2 = 10.En déduire la valeur renvoyée, et vérifier sa cohérence avec la définition du second maximum.
La fonction renvoie m2 = 10. Le maximum de a (qui vaut 10) apparaît deux fois (aux indices 0 et 2) : d’après la définition du cours, le second maximum lui est donc bien égal — ce qui correspond au résultat obtenu.
Encore 2 blocs dans ce document. Créer un compte ne demande qu'une adresse e-mail.