Ch17 – Calcul et algorithmique – QCM

Question 1

En pseudo-code, l'instruction x ← x + 1 signifie :

une équation sans solution on lit la valeur de \(x\), on lui ajoute 1, et on range le résultat dans \(x\) on compare \(x\) et \(x+1\) on crée une nouvelle variable \(x+1\)

Question 2

Quelle structure utiliser quand le nombre d'itérations est connu d'avance ?

SI … ALORS … SINON TANT QUE … FAIRE POUR … DE … À … FAIRE RETOURNER

Question 3

Après exécution de l'algorithme « somme des \(n\) premiers entiers » avec \(n=5\), la variable somme vaut :

\(15\) \(5\) \(25\) \(10\)

Question 4

Quel risque présente une boucle TANT QUE mal écrite ?

elle ne s'exécute jamais elle renvoie toujours 0 elle inverse le tableau une boucle infinie si la condition ne devient jamais fausse

Question 5

Une fonction récursive doit obligatoirement posséder :

au moins deux paramètres un cas de base (condition d'arrêt) et un cas récursif une boucle POUR un tableau en entrée

Question 6

La suite de Fibonacci est définie par \(F_0=0,\;F_1=1,\;F_n=F_{n-1}+F_{n-2}\). Que vaut \(F_6\) ?

\(5\) \(13\) \(8\) \(21\)

Question 7

La méthode de dichotomie pour résoudre \(f(x)=0\) sur \([a,b]\) exige l'hypothèse :

\(f\) continue sur \([a,b]\) et \(f(a)\cdot f(b) \lt 0\) \(f\) dérivable et \(f'(a) = 0\) \(f(a) = f(b)\) \(f(a)\cdot f(b) \gt 0\)

Question 8

La formule d'itération de Newton-Raphson pour approcher une racine de \(f\) est :

\(x_{n+1} = x_n + f(x_n)\,f'(x_n)\) \(x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}\) \(x_{n+1} = \dfrac{a+b}{2}\) \(x_{n+1} = x_n - \dfrac{f'(x_n)}{f(x_n)}\)

Question 9

Quelle est la complexité du tri à bulles et du tri par sélection (cas moyen) ?

\(O(1)\) \(O(\log n)\) \(O(n\log n)\) \(O(n^2)\)

Question 10

Parmi ces complexités, laquelle correspond à un accès direct à \(T[k]\) par son indice ?

\(O(1)\) (constante) \(O(n)\) (linéaire) \(O(n^2)\) (quadratique) \(O(2^n)\) (exponentielle)

Question 11

En classant les complexités de la plus faible à la plus forte, l'ordre correct est :

\(O(n^2) \ll O(n) \ll O(\log n)\) \(O(n\log n) \ll O(\log n) \ll O(n)\) \(O(\log n) \ll O(n) \ll O(n\log n) \ll O(n^2)\) \(O(2^n) \ll O(n^2) \ll O(n)\)

Question 12

En Python, à quelle structure de pseudo-code correspond for i in range(1, n+1) ?

TANT QUE i \(\lt\) n FAIRE POUR i DE 1 À n FAIRE SI i = n ALORS POUR i DE 0 À n FAIRE