Algorithmique

 

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

1. Quelle est la valeur du couple (s, i) à la fin de l'exécution du script suivant ?

s = 0
i = 1
while i < 5:
s = s + i
i = i + 1
A.
B.
C.
D.
2. 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.
3. Soit le temps nécessaire pour trier, à l'aide de l'algorithme du tri par insertion, une liste de 1000 nombres entiers. Quel est l'ordre de grandeur du temps nécessaire, avec le même algorithme, pour trier une liste de 10 000 entiers, c'est-à-dire une liste dix fois plus grande ?
A.
B.
C.
D.
4. Pour pouvoir utiliser un algorithme de recherche par dichotomie dans une liste, quelle précondition doit être vraie ?
A.
B.
C.
D.
5. 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.
6. La fonction mystere suivante prend en argument un tableau d'entiers.

def mystere(t):
for i in range(len(t) - 1):
if t[i] + 1 != t[i+1]:
return False
return True


À quelle condition la valeur renvoyée par la fonction est-elle True ?
A.
B.
C.
D.
7. Quel est l’ordre de grandeur du coût du tri par insertion (dans le pire des cas) ?
A.
B.
C.
D.
8. 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.
9. 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.
10. 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.
11. La fonction ci-dessous permet d’effectuer une recherche par dichotomie de l’index m de l’élément x dans un tableau L de valeurs distinctes et triées

def dicho(x,L):
g = 0
d = len(L)-1
while g <= d:
m = (g+d)//2
if L[m] == x:
return m
elif L[m] < x:
g = m+1
else:
d = m-1       
return None


Combien de fois la cinquième ligne du code de la fonction (m = (g+d)//2) sera-t-elle exécutée dans l'appel dicho(32, [4, 5, 7, 25, 32, 50, 51, 60] ?
A.
B.
C.
D.
12. Une recherche par dichotomie, par rapport à une recherche linéaire :
A.
B.
C.
D.
13. la complexité d'un algorithme ?
A.
B.
C.
D.
14.

On exécute le script suivant :

for i in range(n):
for j in range(i):
print('NSI')


Combien de fois le mot NSI est-il affiché ?
A.
B.
C.
D.
15. À quelle catégorie appartient l’algorithme classique de rendu de monnaie ?
A.
B.
C.
D.
16. On a écrit une fonction, qui prend en paramètre une liste non vide et qui renvoie son plus grand élément. Combien de tests faudra-t-il pour garantir que la fonction donne un résultat correct pour toute liste ?
A.
B.
C.
D.
17. 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.
18. A quelle catégorie, appartient l'algorithme des k plus proches voisins (k-NN) ?
A.
B.
C.
D.
19. On considère la fonction suivante :

def f(x,L):
i = 0
j = len(L)-1
while i<j:
k = (i+j)//2
if x <= L[k]:
j = k
else:
i = k + 1
return i


Cette fonction implémente :
A.
B.
C.
D.
20. 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.