Algorithmique

 

Ce questionnaire est composé de 20 questions aléatoires sur le thème de l'algorithmique.

1. la complexité d'un algorithme ?
A.
B.
C.
D.
2. Lors de l'exécution du code suivant, combien de fois l'opération a = 2*a sera-t-elle effectuée ?

a = 1
cpt = 1
while cpt < 8: 
a = 2*a
cpt = cpt+1
A.
B.
C.
D.
3. Quelle est la valeur de élément à la fin de l'exécution du code suivant :

L = [1,2,3,4,1,2,3,4,0,2]
element = L[0]
for k in L:
if k > element:
element = k
A.
B.
C.
D.
4. On considère le code incomplet suivant qui recherche le maximum dans une liste.

liste = [5,12,15,3,15,17,29,1]
iMax = 0
for i in range(1,len(liste)):
............    
iMax = i
print (liste[iMax])


Par quoi faut-il remplacer la ligne pointillée ?
A.
B.
C.
D.
5. l'algorithme glouton:
A.
B.
C.
D.
6. On considère la fonction suivante :

def comptage(phrase,lettre):
i = 0
for j in phrase:
if j == lettre:
i = i+1
return i


Que renvoie l'appel comptage("Vive l’informatique","e") ?
A.
B.
C.
D.
7. A quelle catégorie, appartient l'algorithme des k plus proches voisins (k-NN) ?
A.
B.
C.
D.
8. On considère le code suivant, où n désigne un entier au moins égal à 2.

p = 1
while p < n:
p = 2*p


Quel argument permet d'affirmer que son exécution termine à coup sûr ?
A.
B.
C.
D.
9. On considère la fonction Python suivante, qui prend en argument une liste L et renvoie le maximum des éléments de la liste :

def rechercheMaximum(L):
max = L[0]
for i in range(len(L)):
if L[i] > max:
max = L[i]
return max


On note la taille de la liste.

Quelle est la complexité en nombre d’opérations de l’algorithme ?
A.
B.
C.
D.
10. On considère la fonction suivante :

def trouverLettre(phrase,lettre):
indexResultat = 0
for i in range(len(phrase)):
if phrase[i]== lettre:
indexResultat=i
return indexResultat


Que renvoie l'appel trouverLettre("Vive l’informatique","e") ?
A.
B.
C.
D.
11. Pour trier par sélection une liste de 2500 entiers, le nombre de comparaisons nécessaires à l’algorithme est de l’ordre de :

A.
B.
C.
D.
12. Quel code parmi les quatre proposés ci-dessous s'exécute-t-il en un temps linéaire en (c'est-à-dire avec un temps d'exécution majoré par où et sont deux constantes) ?
A.
B.
C.
D.
13. Pour pouvoir utiliser un algorithme de recherche par dichotomie dans une liste, quelle précondition doit être vraie ?
A.
B.
C.
D.
14. Avec un algorithme de recherche par dichotomie, combien d'étapes sont nécessaires pour déterminer que 512 est présent dans le tableau suivant: t = [ 1, 8,15, 42, 99,160, 380, 512, 678, 952, 1304]

 
A.
B.
C.
D.
15. Une recherche par dichotomie, par rapport à une recherche linéaire :
A.
B.
C.
D.
16. Un algorithme de calcul de moyenne est implémenté de la façon suivante :

def moyenne(liste) :
t = 0
for e in liste :
t = t + e
# assertion vraie à cet endroit
return t/len(liste)


Parmi les propositions suivantes, laquelle reste vraie à la fin de chaque itération de la boucle ?
A.
B.
C.
D.
17. Un algorithme de tri d’une liste d’entiers est implémenté de la façon suivante :

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


Quelle est l'affirmation exacte ?
A.
B.
C.
D.
18. On exécute le script suivant :

liste=[48, 17, 25 , 9, 34, 12, -5, 89, 54, 12, 78, 8, 155, -85]
def recherche(liste):
valeur_1 = valeur_2 = liste[0]
for item in liste:
if item < valeur_1:
valeur_1 = item
elif item > valeur_2:
valeur_2 = item
else:
pass
return(valeur_1, valeur_2)


Que va renvoyer l'appel recherche(liste) ?
A.
B.
C.
D.
19. En utilisant une recherche dichotomique, combien faut-il de comparaisons pour trouver une valeur dans un tableau trié de 1000 nombres ?
A.
B.
C.
D.
20. L'algorithme suivant permet de calculer la somme des N premiers entiers, où N est un nombre entier donné :

i =0
somme =0
while i < N :
i = i +1
somme = somme + i


Un invariant de boucle de cet algorithme est le suivant :
A.
B.
C.
D.