Algorithmique

 

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

1. On considère la fonction suivante :

def f(T,i):
indice = i
m = T[i]
for k in range(i+1, len(T)):
if T[k] < m:
indice = k
m = T[k]
return indice


Quelle est la valeur de f([ 7, 3, 1, 8, 19, 9, 3, 5 ], 0) ?
A.
B.
C.
D.
2. On définit la fonction f comme suit :

def f(L):
a = L[0]
for x in L:
if x < a:
a = x
return a


Quelle est la valeur renvoyée par l'appel f([7, 10.3, -4, 12 ,7 ,2, 0.7, -5, 14, 1.4]) ?

 
A.
B.
C.
D.
3. 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.
4. 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.
5. A quelle catégorie, appartient l'algorithme des k plus proches voisins (k-NN) ?
A.
B.
C.
D.
6. Une recherche par dichotomie, par rapport à une recherche linéaire :
A.
B.
C.
D.
7. On exécute le code suivant :

tab = [1, 4, 3, 8, 2]
S = 0
for i in range(len(tab)):
S = S + tab[i]


Que vaut la variable S à la fin de l'exécution ?
A.
B.
C.
D.
8. La fonction suivante doit calculer le produit de tous les éléments de la liste passée en paramètre. Avec quelles expressions doit-on la compléter pour que cette fonction soit correcte ?

def produit (L):
p = ...
for elt in L:
.......
return p
A.
B.
C.
D.
9. 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.
10. La fonction suivante doit calculer la moyenne d’un tableau de nombres, passé en paramètre. Avec quelles expressions faut-il remplacer les points de suspension pour que la fonction soit correcte ?

def moyenne(tableau):
total = ...
for valeur in tableau:
total = total + valeur
return total / ...


 
A.
B.
C.
D.
11. 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.
12. 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.
13. la complexité d'un algorithme ?
A.
B.
C.
D.
14. 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.
15. Un algorithme de recherche dichotomique dans une liste triée de taille nécessite, dans le pire des cas, exactement comparaisons.

Combien cet algorithme va-t-il utiliser, dans le pire des cas, de comparaisons sur une liste de taille ?
A.
B.
C.
D.
16. Avec un algorithme de recherche par dichotomie, combien d’étapes sont nécessaires pour déterminer que 35 est présent dans le tableau [1, 7, 12, 16, 18, 20, 24, 28, 35, 43, 69] ?
A.
B.
C.
D.
17. Quel est l’ordre de grandeur du coût du tri par insertion (dans le pire des cas) ?
A.
B.
C.
D.
18. 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.
19. On conçoit un algorithme permettant de déterminer la valeur maximale parmi une liste quelconque de valeurs comparables.

Pour une liste de 100 valeurs, le nombre minimal de comparaisons que doit effectuer cet algorithme est :
A.
B.
C.
D.
20. 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.