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. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. la complexité d'un algorithme ?
A.
B.
C.
D.
11. 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.
12. 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.
13. 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.
14. l'algorithme glouton:
A.
B.
C.
D.
15. Une recherche par dichotomie, par rapport à une recherche linéaire :
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. 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.
18. 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.
19. Quel est l’ordre de grandeur du coût du tri par insertion (dans le pire des cas) ?
A.
B.
C.
D.
20.

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.