Examen_H18 COMPLET Flashcards
L’adressage ouvert nécessite l’utilisation d’un champ « état » pour décrire l’état de l’entrée d’une
table. Décrivez quels sont les états possibles.
L’état ACTIVE : Indique que cette entrée contient une clé valide (2 points)
L’état DELETED : Indique que cette entrée a déjà contenu une clé valide, mais elle a été
supprimée (2 points)
L’état EMPTY : Indique que cette entrée est vide et n’a jamais contenu une clé. (2 points)
REGARDER IMAGE DE LA QUESTION 2
En continuité avec la question précédente, lorsque TrouverPosition(x) est arrêté sur une entrée de la
table, quelle est la valeur booléenne retournée par Trouver(x) et comment le champ état est-il modifié
en fonction de l’état initial de cette entrée et de la clé x? Même question pour Supprimer(x) et pour
Insérer(x). (9 points)
Cette question concerne les tas max (i.e., les monceaux)
Cette question concerne les tas max (i.e., les monceaux).
(b) Si on enlève la racine du tas max constitué du tableau
[10, 8, 5, 7, 4, 1], dessinez la représentation arborescente du tas résultant.
Cette question concerne les tas max (i.e., les monceaux).
(c) Si on enlève la racine du tas max constitué du tableau
[15, 8, 14, 3, 6], dessinez la représentation arborescente du tas résultant.