Français
Menu

Structures de données et algorithmes

Apprenez les structures de données et les algorithmes avec des QCM : complexité temporelle et notation grand O, tableaux et listes chaînées, piles et files d'attente, tables de hachage, recherche dichotomique, fonctionnement et stabilité des différents tris, arbres binaires de recherche et tas, parcours de graphes et plus courts chemins, récursion, programmation dynamique et algorithmes gloutons, y compris leurs liens avec les caches et les GPU.

S'entraîner sur 10 questionsQuestions aléatoires de ce thème · environ 5 minutes S'entraîner sur ce thèmeToutes les questions de ce thème dans un ordre aléatoire Questions à revoirNe refaire que les questions manquées lors de la dernière tentative

Structures de données et algorithmes : points clés

Des programmes qui résolvent le même problème peuvent avoir des vitesses qui diffèrent de plusieurs ordres de grandeur quand les données augmentent, selon les structures de données et les algorithmes qu'ils utilisent. Estimer la croissance du travail par la complexité temporelle et choisir des structures adaptées à l'usage des données sont les points de départ des programmes rapides.

Ce thème couvre les structures de données de base comme les tableaux et les listes chaînées, les piles et les files d'attente, les tables de hachage, les arbres binaires de recherche et les tas, ainsi que la représentation des graphes, avec la recherche dichotomique, les tris (à bulles, par sélection, par insertion, fusion, rapide et par tas), le parcours en largeur, le parcours en profondeur et l'algorithme de Dijkstra, ainsi que la récursion, la programmation dynamique et les algorithmes gloutons, principalement au moyen de questions de calcul qui suivent chaque étape. Il aide aussi à préparer la partie algorithmique des examens de certification informatique. Il aborde en outre le lien avec les performances du matériel, comme les dispositions de données adaptées au cache et le tri parallèle sur GPU.

Toutes les questions sur Structures de données et algorithmes (40)
  1. Pour un tableau de n éléments, quelle est la complexité temporelle d'un traitement qui compare une seule fois chaque paire d'éléments distincts (une double boucle qui compare l'élément i à tous les éléments situés après lui, en faisant avancer i d'un cran à chaque fois) ?
  2. Un programme de complexité temporelle O(n²) met 0,5 seconde pour 1000 données. Combien de temps mettra-t-il environ pour 4000 données ?
  3. Une recherche linéaire compare un à un, depuis le début, les éléments d'un tableau de 100 valeurs distinctes pour trouver une valeur cible. Si la cible se trouve toujours dans le tableau et a la même probabilité d'être à n'importe quelle position, quel est le nombre moyen de comparaisons ?
  4. Par rapport à un tableau, quelle description d'une liste chaînée (liste dont chaque élément contient un pointeur vers l'élément suivant) est correcte ?
  5. Sur une pile vide, on effectue dans cet ordre les opérations push 1, push 2, pop, push 3, push 4, pop, pop. Dans quel ordre les valeurs sont-elles retirées par pop ?
  6. On ajoute dans cet ordre les éléments A, B et C à une file d'attente vide. Ensuite, on retire un élément, on ajoute D et on retire un élément, puis on ajoute E et on retire un élément. Dans quel ordre les éléments sont-ils retirés ?
  7. On évalue l'expression « 3 4 + 2 * 5 − » écrite en notation polonaise inverse (notation postfixée) en empilant chaque nombre sur une pile et, pour chaque opérateur, en retirant deux valeurs, en calculant le résultat et en l'empilant à nouveau. Quel est le résultat ? L'opérande gauche d'un opérateur est la valeur empilée la première.
  8. Quelle description d'une collision dans une table de hachage est correcte ?
  9. On range dans cet ordre les clés 10, 17, 24 et 3 dans une table de hachage de taille 7 (positions 0 à 6) avec la fonction de hachage h(k) = k mod 7. Les collisions sont résolues par sondage linéaire, qui avance d'une position à la fois (en revenant de 6 à 0) pour trouver un emplacement libre. À quelle position la clé 3 est-elle rangée ?
  10. Quelle comparaison du chaînage (relier par une liste chaînée les éléments d'une même position) et de l'adressage ouvert (chercher une autre position libre dans la table), comme méthodes de résolution des collisions d'une table de hachage, est correcte ? Le facteur de charge est le nombre d'éléments stockés divisé par la taille de la table.
  11. Quelle condition est nécessaire pour utiliser la recherche dichotomique, qui compare la cible à l'élément du milieu et réduit de moitié l'intervalle de recherche à chaque fois ?
  12. On effectue une recherche dichotomique parmi 1000 valeurs distinctes triées par ordre croissant. Si une comparaison indique si les valeurs sont égales, plus petites ou plus grandes, quel est le nombre maximal de comparaisons, en comptant les recherches réussies comme infructueuses ?
  13. Une recherche dichotomique cherche 38 dans le tableau croissant a[0] à a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. L'intervalle de recherche commence avec lo = 0 et hi = 9, et la position du milieu vaut (lo + hi) ÷ 2 arrondi à l'entier inférieur. Quelle liste donne, dans l'ordre, les éléments comparés à 38 ?
  14. On trie par ordre croissant le tableau 5, 3, 8, 1, 4 avec le tri à bulles. Quel est le tableau après une passe, au cours de laquelle les éléments voisins sont comparés du début jusqu'à la fin et échangés chaque fois que celui de gauche est le plus grand ?
  15. On trie par ordre croissant le tableau 29, 10, 14, 37, 13 avec le tri par sélection, qui cherche le minimum de la partie non triée et l'échange avec le premier élément de cette partie. Quel est le tableau après deux répétitions de cette étape ?
  16. On trie par ordre croissant un tableau de 10 éléments avec le tri par insertion. Chaque élément à partir du deuxième est extrait et comparé aux éléments situés à sa gauche, en commençant par son voisin de gauche, jusqu'à trouver un élément inférieur ou égal ou jusqu'à atteindre le début. Combien de comparaisons sont effectuées quand le tableau est déjà dans l'ordre croissant, et quand il est dans l'ordre décroissant ?
  17. Quel algorithme de tri a une complexité temporelle en O(n log n) même dans le pire cas et trie presque sans mémoire supplémentaire, comme un tableau de travail ?
  18. Les enregistrements (nom, note) (A, 80), (B, 70), (C, 80), (D, 70) sont dans cet ordre. Si on les trie par note croissante avec un tri stable, dans quel ordre les noms apparaissent-ils ?
  19. Quel est le cas typique dans lequel la complexité temporelle du tri rapide devient O(n²) ?
  20. Dans le tri fusion, on fusionne les deux séquences triées 1, 4, 7, 9 et 2, 3, 8, 10 en une seule en comparant de façon répétée leurs éléments de tête et en sortant le plus petit. Quand une séquence est vide, le reste de l'autre est sorti sans comparaison. Combien de comparaisons sont effectuées ?
  21. Un tas binaire est stocké dans un tableau a[0], a[1], a[2], … avec la racine en a[0], en remplissant chaque niveau de gauche à droite à partir du haut. Quels sont les enfants et le parent de a[4] ?
  22. Un tas max, dans lequel la valeur de chaque parent est supérieure ou égale à celles de ses enfants, est stocké dans un tableau avec la racine en a[0]. On ajoute 45 au tas 50, 30, 40, 10, 20, 35 en le plaçant à la fin, puis en l'échangeant avec son parent tant qu'il est plus grand que celui-ci. Quel est le tableau obtenu ?
  23. Quand on parcourt un arbre binaire de recherche dans l'ordre infixe (sous-arbre gauche, puis le nœud, puis sous-arbre droit), dans quel ordre se présentent les valeurs des nœuds visités ? On suppose toutes les valeurs distinctes.
  24. On insère dans cet ordre les valeurs 50, 30, 70, 20, 40, 60, 80 dans un arbre binaire de recherche vide. Dans quel ordre les nœuds sont-ils visités quand on parcourt l'arbre dans l'ordre postfixe (sous-arbre gauche, sous-arbre droit, puis le nœud) ?
  25. On insère dans cet ordre les valeurs 1, 2, 3, …, 1000 dans un arbre binaire de recherche vide (sans aucun rééquilibrage). Lors de la recherche de 1000 dans cet arbre, combien de nœuds sont comparés, à partir de la racine, avant de le trouver ?
  26. Quelle est la raison principale pour laquelle les arbres B (y compris les arbres B+), plutôt que les arbres binaires de recherche, sont largement utilisés pour les index des bases de données et des systèmes de fichiers ?
  27. Quelle est une façon appropriée de stocker en mémoire un graphe creux, c'est-à-dire un graphe ayant peu d'arêtes par rapport à son nombre de sommets, comme un réseau routier d'environ 1 million de sommets et 3 millions d'arêtes ?
  28. Dans un graphe dont les arêtes n'ont pas de poids, on veut trouver le plus petit nombre d'arêtes entre un sommet de départ et chacun des autres sommets. Quelle association entre méthode de recherche et structure de données convient ?
  29. Dans un graphe non orienté, les voisins de chaque sommet sont A : B, C / B : A, D, E / C : A, F / D : B / E : B, F / F : C, E. Un parcours en profondeur par récursion part du sommet A. Les voisins sont examinés dans l'ordre indiqué, et dès qu'un sommet non visité est trouvé, le parcours s'y déplace. Dans quel ordre les sommets sont-ils visités ?
  30. Dans un graphe non orienté, les poids des arêtes (distances) sont S−A : 4, S−B : 1, A−B : 2, A−C : 1, B−C : 5, C−T : 3 et A−T : 6. Quelle réponse donne le plus court chemin de S à T trouvé par l'algorithme de Dijkstra et sa longueur ?
  31. Quelle condition sur le graphe est nécessaire pour que l'algorithme de Dijkstra trouve des plus courts chemins corrects ?
  32. Les tâches A à E ont les contraintes d'ordre « A avant C », « B avant C », « C avant D », « B avant E » et « E avant D ». Quel ordre satisfait toutes les contraintes (résultat d'un tri topologique) ?
  33. Une fonction f(x, y) est définie par « si y vaut 0, renvoyer x ; sinon, renvoyer f(y, x mod y) ». Quand on appelle f(84, 36), quelle est la valeur renvoyée, et combien de fois f est-elle appelée, premier appel compris ?
  34. Une fonction fib(n) qui calcule les nombres de Fibonacci est définie par récursion : « si n vaut 1 ou moins, renvoyer n ; sinon, renvoyer fib(n−1) + fib(n−2) ». Quand on appelle fib(5), combien de fois fib est-elle appelée, premier appel compris ?
  35. On paie 8 yens avec des pièces de 1 yen, 4 yens et 6 yens. Quelle affirmation relie correctement le nombre de pièces choisi par un algorithme glouton, qui utilise d'abord autant que possible la plus grosse pièce, et le nombre minimal de pièces ?
  36. On remplit un sac à dos de capacité 8 avec des objets choisis parmi quatre objets de (poids, valeur) (2, 3), (3, 4), (4, 5) et (5, 6). Il n'existe qu'un exemplaire de chaque objet, et les objets ne peuvent pas être fractionnés. Quelle est la valeur totale maximale pour un poids total de 8 ou moins ?
  37. Quelle est une caractéristique de l'algorithme de Boyer-Moore, qui recherche un motif dans une chaîne de caractères ?
  38. Un tableau dynamique, quand on ajoute un élément alors qu'il est plein, alloue une nouvelle zone de capacité double et y copie tous les éléments. Si l'on ajoute un à un 1000 éléments à un tableau vide de capacité 1, combien de copies d'éléments sont effectuées au total ?
  39. Pour une table de hachage contenant de nombreux éléments et maintenue à un facteur de charge d'environ 0,5, quelle est la raison la plus appropriée pour laquelle l'adressage ouvert avec sondage linéaire tend à être plus rapide que le chaînage (relier les éléments par des listes chaînées) ?
  40. Des méthodes de tri dont la suite d'étapes de comparaison-échange est fixée d'avance (réseaux de tri), comme le tri bitonique, sont parfois utilisées pour trier sur du matériel parallèle comme les GPU. Pourquoi ?

Autres thèmes de Systèmes informatiques