C17 : QCM

Question

On exécute le script suivant :

a = 4
b = 4
c = 4
while a < 5:
    a = a - 1
    b = b + 1
    c = c * b

Que peut-on dire ?

Question

Un algorithme de recherche dichotomique dans une liste triée de taille n nécessite, dans le pire des cas, exactement k comparaisons.

Combien cet algorithme va-t-il utiliser, dans le pire des cas, de comparaisons sur une liste de taille 2n ?

Question

p = 1
while p < n:
	p = 2*p

Quel argument permet d'affirmer que son exécution termine à coup sûr ?

Question

On définit une fonction de calcul de la moyenne d'une liste de nombres :

def moyenne(L):
	s = 0
	n = len(L)
	for x in L:
		s = s + x
	return s/n

Combien cette fonction utilise-t-elle d'opérations (additions et divisions) pour calculer la moyenne d'une liste de 7 nombres ?

Question

On considère le code suivant de recherche d'une valeur dans une liste :

def search(x, liste):
    # x est la valeur à chercher
    # liste est une liste de valeurs
    for i in range(len(liste)):
        if x == liste[i]:
            return i
    return None

Quel est le coût de cet algorithme ?

Question

On exécute le script suivant :

liste = [17, 12, 5, 18, 2, 7, 9, 15, 14, 20]
somme = 0
i = 0
while i < len(liste):
    somme = somme + liste[i]
    i = i + 1
resultat = somme / len(liste)

Quelle affirmation est fausse parmi les suivantes ?

Question

Pour pouvoir utiliser un algorithme de recherche par dichotomie dans une liste, quelle précondition doit être vraie ?

Question

Soit L une liste de n nombres réels (n 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 n de données double alors le temps d'exécution de ce script :

Question

On considère un entier positif A.

Parmi les quatre codes suivants, il y en a un dont l'exécution ne termine pas. Lequel ?

i = A + 1
	while i < A:
		i = i + 1

i = A - 1
	while i < A:
		i = i - 1

i = A + 1
	while i < A:
		i = i - 1

i = A - 1
	while i < A:
		i = i + 1