Objectif du plan d’études gymnasial
GYM INF 1 — Discipline obligatoire : informatique.
Aperçu des questions
1Une liste de 250 noms n'est pas triée. Une recherche séquentielle compare le nom cherché à chaque élément. Combien de comparaisons faut-il pour affirmer qu'un nom absent n'y figure pas ?
Réponse chiffrée à écrire.
2Pourquoi une recherche dichotomique ne peut-elle pas s'appliquer à une liste de noms rangés au hasard ?
Parce qu'elle doit connaître d'avance la position du nom cherché.Parce que comparer au nom du milieu n'apprend alors rien sur le reste.Parce qu'elle ne sait comparer que des nombres, jamais du texte.Parce qu'elle exige une liste dont la taille est une puissance de deux.
3Remets dans l'ordre les étapes d'une recherche dichotomique dans une liste triée.
À remettre dans le bon ordre :
Calculer l'indice du milieu entre les deux bornesComparer la valeur cherchée à l'élément du milieuDéplacer une borne pour ne garder qu'une moitiéPoser deux bornes : début et fin de la listeRecommencer tant que les bornes ne se croisent pas
4Une liste triée compte 100 valeurs. Chaque comparaison d'une recherche dichotomique élimine la moitié des candidats encore possibles. Combien de comparaisons suffisent au pire pour conclure ?
Réponse chiffrée à écrire.
5Un tri en n² compare environ n × n valeurs. Sur 100 000 fiches, un ordinateur qui effectue 100 millions de comparaisons par seconde termine ce tri en moins d'une seconde.
VraiFaux
6Une liste contient n valeurs. Range chaque opération selon le nombre d'étapes qu'elle demande dans le pire cas.
Catégories :
Environ log nEnviron nEnviron n²
Éléments à classer :
Additionner toutes les valeurs de la listeChercher par dichotomie dans une liste triéeComparer chaque valeur à toutes les autresCouper la liste en deux jusqu'à un seul élémentTrier la liste avec un tri à bullesTrouver la plus grande valeur de la liste
7n = 12 compteur = 0 for i in range(n): for j in range(n): compteur = compteur + 1 Combien vaut compteur à la fin ?
Réponse chiffrée à écrire.
8Une liste de 1000 valeurs passe à 2000 valeurs. Associe chaque coût au nombre de comparaisons qui en résulte, arrondi.
À associer par paires :
n comparaisonslog n comparaisonsn² comparaisonsn × log n comparaisons
11 environ200022 000 environ4 000 000
9Deux moitiés triées de 4 valeurs sont fusionnées : on compare leurs premiers éléments restants et on garde le plus petit. Quand une moitié est vide, le reste passe sans comparaison. Combien de…
4 comparaisons5 comparaisons7 comparaisons8 comparaisons
10Le tri à bulles parcourt la liste et échange deux voisins mal ordonnés. On applique une passe complète à la liste [5, 1, 4, 2]. Quelles affirmations sont exactes ?
La liste est devenue [1, 4, 2, 5].La plus grande valeur occupe la dernière place.La liste est maintenant entièrement triée.Trois comparaisons de voisins ont été faites.Aucun échange n'a été nécessaire.La plus petite valeur a été poussée vers la fin.
11while debut <= fin: m = (debut + fin) // 2 if t[m] < cible: ??? La liste t est triée. Quelle instruction remplace correctement les points d'interrogation ?
debut = m + 1fin = m - 1debut = m - 1fin = len(t) - 1
12Un logiciel de gestion garde ses 500 000 fiches triées par nom, et non dans l'ordre où elles sont arrivées. Quel avantage principal cela lui donne-t-il ?
Il occupe beaucoup moins de place sur le disque de la machine.Il ajoute une nouvelle fiche sans jamais déplacer les autres.Il protège les fiches contre les fautes de saisie du personnel.Il retrouve une fiche par dichotomie au lieu de tout parcourir.
Les bonnes réponses se découvrent en jouant le Kwiiz.
