Algorithmique (NSI 1)

NSI, Première NSI, QCM NSI / Par

Algorithmique

 

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

1. La fonction mystere suivante prend en argument un tableau d'entiers.

[pastacode lang="python" manual="def%20mystere(t)%3A%0A%09for%20i%20in%20range(len(t)%20-%201)%3A%0A%09%09if%20t%5Bi%5D%20%2B%201%20!%3D%20t%5Bi%2B1%5D%3A%0A%09%09%09return%20False%0A%09return%20True%0A" message="" highlight="" provider="manual"/]

À quelle condition la valeur renvoyée par la fonction est-elle True ?
A.
B.
C.
D.
2. 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.
3. Que renvoie la fonction suivante quand on l'appelle avec un nombre entier et une liste d'entiers ?

[pastacode lang="python" manual="def%20mystere(n%2CL)%3A%0A%09for%20x%20in%20L%3A%0A%09%09if%20n%20%3D%3D%20x%3A%0A%09%09%09return%20True%0A%09return%20False%0A%0A" message="" highlight="" provider="manual"/]
A.
B.
C.
D.
4. 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.

[pastacode lang="python" manual="M%20%3D%200%0Afor%20k%20in%20range(n)%3A%0A%20%20%20%20%20%20%20%20%20M%20%3D%20M%20%2B%20L%5Bk%5D%0AM%20%3D%20M%2Fn%0A" message="" highlight="" provider="manual"/]

Si le nombre  de données double alors le temps d'exécution de ce script  :
A.
B.
C.
D.
5. 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.
6. Une recherche par dichotomie, par rapport à une recherche linéaire :
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. 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 ?

[pastacode lang="python" manual="def%20produit%20(L)%3A%0A%09p%20%3D%20...%0A%09for%20elt%20in%20L%3A%0A%09%09.......%0A%09return%20p%0A" message="" highlight="" provider="manual"/]
A.
B.
C.
D.
9. On considère la fonction Python suivante, qui prend en argument une liste L et renvoie le maximum des éléments de la liste :

[pastacode lang="python" manual="def%20rechercheMaximum(L)%3A%0A%20%20%20%20max%20%3D%20L%5B0%5D%0A%20%20%20%20for%20i%20in%20range(len(L))%3A%0A%09%09if%20L%5Bi%5D%20%3E%20max%3A%0A%09%09%09max%20%3D%20L%5Bi%5D%0A%20%20%20%20return%20max%0A" message="" highlight="" provider="manual"/]

On note  la taille de la liste.

Quelle est la complexité en nombre d’opérations de l’algorithme ?
A.
B.
C.
D.
10. 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.
11. 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 ?

[pastacode lang="python" manual="def%20moyenne(tableau)%3A%0A%20%20%20%20total%20%3D%20...%0A%20%20%20%20for%20valeur%20in%20tableau%3A%0A%20%20%20%20%20%20%20%20total%20%3D%20total%20%2B%20valeur%0A%20%20%20%20return%20total%20%2F%20...%0A" message="" highlight="" provider="manual"/]

 
A.
B.
C.
D.
12. On considère la fonction suivante :

[pastacode lang="python" manual="def%20comptage(phrase%2Clettre)%3A%0A%09i%20%3D%200%0A%09for%20j%20in%20phrase%3A%0A%09%09if%20j%20%3D%3D%20lettre%3A%0A%09%09%09i%20%3D%20i%2B1%0A%09return%20i%0A" message="" highlight="" provider="manual"/]

Que renvoie l'appel comptage("Vive l’informatique","e") ?
A.
B.
C.
D.
13. A quelle catégorie, appartient l'algorithme des k plus proches voisins (k-NN) ?
A.
B.
C.
D.
14. 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.
15. 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 ?
A.
B.
C.
D.
16. On définit la fonction f comme suit :

[pastacode lang="python" manual="def%20f(L)%3A%0A%09a%20%3D%20L%5B0%5D%0A%09for%20x%20in%20L%3A%0A%09%09if%20x%20%3C%20a%3A%0A%09%09%09a%20%3D%20x%0A%09return%20a%0A" message="" highlight="" provider="manual"/]

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.
17. Quel est l’ordre de grandeur du coût du tri par insertion (dans le pire des cas) ?
A.
B.
C.
D.
18. On considère le code incomplet suivant qui recherche le maximum dans une liste.

[pastacode lang="python" manual="liste%20%3D%20%5B5%2C12%2C15%2C3%2C15%2C17%2C29%2C1%5D%0AiMax%20%3D%200%0Afor%20i%20in%20range(1%2Clen(liste))%3A%0A%09............%20%20%20%20%0A%09iMax%20%3D%20i%0A%0Aprint%20(liste%5BiMax%5D)%0A" message="" highlight="" provider="manual"/]

Par quoi faut-il remplacer la ligne pointillée ?
A.
B.
C.
D.
19. 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.
20. On considère la fonction suivante :

[pastacode lang="python" manual="def%20trouverLettre(phrase%2Clettre)%3A%0A%09indexResultat%20%3D%200%0A%09for%20i%20in%20range(len(phrase))%3A%0A%09if%20phrase%5Bi%5D%3D%3D%20lettre%3A%0A%09%09indexResultat%3Di%0A%09return%20indexResultat%0A" message="" highlight="" provider="manual"/]

Que renvoie l'appel trouverLettre("Vive l’informatique","e") ?
A.
B.
C.
D.

 

Retour en haut
Retour haut de page