Structures de données et algorithmes

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 ?

A1, 2, 3
B2, 3, 4
C2, 4, 3

Afficher la réponse et l'explication

Réponse : C. 2, 4, 3

Une pile est une structure LIFO (dernier entré, premier sorti) : l'élément ajouté en dernier est retiré en premier. Après push 1 et push 2, pop retire la valeur du sommet, 2, et il reste 1. Après push 3 et push 4, la pile contient 4, 3, 1 en partant du sommet, et les deux pop suivants retirent 4 puis 3. Les valeurs sortent donc dans l'ordre 2, 4, 3, et 1 reste dans la pile. 1, 2, 3 serait l'ordre obtenu avec une file d'attente (FIFO, premier entré, premier sorti), qui retire d'abord l'élément le plus ancien.

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

Autres questions sur 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 ?
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.
Quelle description d'une collision dans une table de hachage est correcte ?
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 ?
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.