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. Pour pouvoir utiliser un algorithme de recherche par dichotomie dans une liste, quelle précondition doit être vraie ?
A.
B.
C.
D.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
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. Quel est l’ordre de grandeur du coût du tri par insertion (dans le pire des cas) ?
A.
B.
C.
D.
10. Une recherche par dichotomie, par rapport à une recherche linéaire :
A.
B.
C.
D.
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.
16. Quelle est la valeur de c à la fin de l'exécution du code suivant :

L = [1,2,3,4,1,2,3,4,0,2]
c = 0
for k in L:
    if k == L[1]:
        c = c+1
A.
B.
C.
D.
17. 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.
18. 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.
19. 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.
20. 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.