Algorithmique

 

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

1. 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.
2. Soit L une liste de  nombres réels ( entier naturel non nul). On considère l'algorithme suivant, en langage Python, calculant la moyenne des éléments de L.

M = 0
for k in range(n):
         M = M + L[k]
M = M/n


Si le nombre  de données double alors le temps d'exécution de ce script  :
A.
B.
C.
D.
3. 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.
4. 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.
5. 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.
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. 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.
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 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.
10. Quelle est la valeur de X/m à la fin de l'exécution du code suivant :

L = [1,2,3,4,1,2,3,4,0,2]

X = 0
m = 0
for k in L:
    X = X + k
    m = m + 1
A.
B.
C.
D.
11. 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.
12. la complexité d'un algorithme ?
A.
B.
C.
D.
13. À quelle catégorie appartient l’algorithme classique de rendu de monnaie ?
A.
B.
C.
D.
14. 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.
15. 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.
16. 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.
17. Quel est l’ordre de grandeur du coût du tri par insertion (dans le pire des cas) ?
A.
B.
C.
D.
18. 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.
19.

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.
20. 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.