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.
Cette question concerne les tas max (i.e., les monceaux).
(d) Si on ajoute l’élément 8 au tas max [13, 10, 7, 8, 6], dessinez la représentation arborescente du tas résultant.
Cette question concerne les tas max (i.e., les monceaux).
(e) Si on ajoute l’élément 11 au tas max [10, 9, 7, 8], dessinez la représentation arborescente du tas résultant.
4 cas possibles selon le critère AVL
Pour chaque arbre suivant, identifiez le cas du débalancement : le nœud critique, le nœud sous-critique, et l’arbre AVL résultant après avoir corrigé le
débalancement.
CAS 1
4 cas possibles selon le critère AVL
Pour chaque arbre suivant, identifiez le cas du débalancement : le nœud critique, le nœud sous-critique, et l’arbre AVL résultant après avoir corrigé le
débalancement.
CAS 2
4 cas possibles selon le critère AVL
Pour chaque arbre suivant, identifiez le cas du débalancement : le nœud critique, le nœud sous-critique, et l’arbre AVL résultant après avoir corrigé le
débalancement.
CAS 3
4 cas possibles selon le critère AVL
Pour chaque arbre suivant, identifiez le cas du débalancement : le nœud critique, le nœud sous-critique, et l’arbre AVL résultant après avoir corrigé le
débalancement.
CAS 4
Arbre AVL
Supposons que vous désirez supprimer l’élément 11 de l’arbre AVL suivant. Illustrez les différentes
étapes de reconstruction de l’arbre menant à la suppression de cet élément.
Vrai ou Faux, triage
Le temps d’exécution du tri par insertion est en Ω(n²).
FAUX
Vrai ou Faux, triage
Le temps d’exécution du tri de base en O(n)
VRAI
Vrai ou Faux, triage
Le temps d’exécution du tri par tas est en Θ(n log n)
FAUX
Vrai ou Faux, triage
Le temps d’exécution du tri fusion est en Θ(n log n)
VRAI
Vrai ou Faux, triage
Le tri par insertion est stable.
VRAI
Vrai ou Faux, triage
Le tri fusion se fait sur place.
FAUX
Vrai ou Faux, triage
Le tri de base se fait sur place.
FAUX
Vrai ou Faux, triage
Le tri fusion est stable.
VRAI
Vrai ou Faux, triage
Le tri par tas est stable.
FAUX
Vrai ou Faux, triage
Le tri par insertion ne se fait pas sur place.
FAUX
