Algorithmique

 

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

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

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

3. Une recherche par dichotomie, par rapport à une recherche linéaire :

A.
B.
C.
D.

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

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

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

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

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

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

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

11. la complexité d'un algorithme ?

A.
B.
C.
D.

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

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

14. Que renvoie la fonction suivante quand on l'appelle avec un nombre entier et une liste d'entiers ?

def mystere(n,L):
	for x in L:
		if n == x:
			return True
	return False
A.
B.
C.
D.

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

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

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

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

20. l'algorithme glouton:

A.
B.
C.
D.