Français
Menu

Structures de données et algorithmes

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 ?

  1. AA, B, C
  2. BC, D, E
  3. CC, B, A
Afficher la réponse et l'explication

Réponse : A. A, B, C

Une file d'attente est une structure FIFO (premier entré, premier sorti) : les éléments sont retirés dans l'ordre où ils ont été ajoutés. Après l'ajout de A, B et C, le premier retrait prend A. Même si D et E sont ensuite ajoutés à l'arrière, B et C, placés devant, sortent d'abord : l'ordre de retrait est donc A, B, C, et D et E restent dans la file. C, D, E serait l'ordre obtenu avec une pile (LIFO), qui retire à chaque fois l'élément ajouté le plus récemment. Les files servent pour les travaux d'impression, pour les files de messages qui transmettent des données entre tâches et pour le parcours en largeur.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. 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.
  2. Quelle description d'une collision dans une table de hachage est correcte ?
  3. 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 ?
  4. 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.
  5. 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 ?