Algorithmique

 

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

1. la complexité d'un algorithme ?

A.
B.
C.
D.

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

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

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

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

6.

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.

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

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

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

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

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

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

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

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

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

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

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

19. A quelle catégorie, appartient l'algorithme des k plus proches voisins (k-NN) ?

A.
B.
C.
D.

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