Français
Menu

Structures de données et algorithmes

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.

  1. A−9
  2. B6
  3. C9
Afficher la réponse et l'explication

Réponse : C. 9

On empile 3 et 4, puis + les retire et empile 3 + 4 = 7. On empile 2, puis * empile 7 × 2 = 14. On empile 5, puis − soustrait la valeur la plus récente, 5, de la valeur la plus ancienne, 14, ce qui donne 14 − 5 = 9. En notation postfixée, l'ordre des opérations est fixé par la suite elle-même et aucune parenthèse n'est nécessaire ; cette expression correspond à (3 + 4) × 2 − 5 en notation usuelle. −9 vient d'une inversion des opérandes de la soustraction, et 6 d'une lecture sans parenthèses, 3 + 4 × 2 − 5.

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

Autres questions sur Structures de données et algorithmes

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