Examen_A19 COMPLET Flashcards
Considérez une table de dispersion de 10 indexes (cases, alvéoles, entrées,…) et une fonction de hachage h telle que pour tout entier non signé x, nous avons h(x) = x mod 10. Considérez également que nous utilisons l’adressage ouvert. Dans les exemples ci-dessous, une case de la table dans l’état EMPTY est indiquée par un blanc et une case dans l’état ACTIVE ou DELETED contenant une clé x est indiquée par la clé x présente. Pour chaque table, la première rangée indique la valeur de l’indexe. Le contenu de la table se trouve à la deuxième rangée.
Considérez une table de dispersion de 10 indexes (cases, alvéoles, entrées,…) et une fonction de hachage h telle que pour tout entier non signé x, nous avons h(x) = x mod 10. Considérez également que nous utilisons l’adressage ouvert. Dans les exemples ci-dessous, une case de la table dans l’état EMPTY est indiquée par un blanc et une case dans l’état ACTIVE ou DELETED contenant une clé x est indiquée par la clé x présente. Pour chaque table, la première rangée indique la valeur de l’indexe. Le contenu de la table se trouve à la deuxième rangée.
Considérez une table de dispersion de 10 indexes (cases, alvéoles, entrées,…) et une fonction de hachage h telle que pour tout entier non signé x, nous avons h(x) = x mod 10. Considérez également que nous utilisons l’adressage ouvert. Dans les exemples ci-dessous, une case de la table dans l’état EMPTY est indiquée par un blanc et une case dans l’état ACTIVE ou DELETED contenant une clé x est indiquée par la clé x présente. Pour chaque table, la première rangée indique la valeur de l’indexe. Le contenu de la table se trouve à la deuxième rangée.
Considérez une table de dispersion de 10 indexes (cases, alvéoles, entrées,…) et une fonction de hachage h telle que pour tout entier non signé x, nous avons h(x) = x mod 10. Considérez également que nous utilisons l’adressage ouvert. Dans les exemples ci-dessous, une case de la table dans l’état EMPTY est indiquée par un blanc et une case dans l’état ACTIVE ou DELETED contenant une clé x est indiquée par la clé x présente. Pour chaque table, la première rangée indique la valeur de l’indexe. Le contenu de la table se trouve à la deuxième rangée.
Considérez une table de dispersion de 10 indexes (cases, alvéoles, entrées,…) et une fonction de hachage h telle que pour tout entier non signé x, nous avons h(x) = x mod 10. Considérez également que nous utilisons l’adressage ouvert. Dans les exemples ci-dessous, une case de la table dans l’état EMPTY est indiquée par un blanc et une case dans l’état ACTIVE ou DELETED contenant une clé x est indiquée par la clé x présente. Pour chaque table, la première rangée indique la valeur de l’indexe. Le contenu de la table se trouve à la deuxième rangée.
Considérez une table de dispersion de 10 indexes (cases, alvéoles, entrées,…) et une fonction de hachage h telle que pour tout entier non signé x, nous avons h(x) = x mod 10. Considérez également que nous utilisons l’adressage ouvert. Dans les exemples ci-dessous, une case de la table dans l’état EMPTY est indiquée par un blanc et une case dans l’état ACTIVE ou DELETED contenant une clé x est indiquée par la clé x présente. Pour chaque table, la première rangée indique la valeur de l’indexe. Le contenu de la table se trouve à la deuxième rangée.
Cette question porte sur l’adressage ouvert
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.
Cette question porte sur l’adressage ouvert
Cette question porte sur l’adressage ouvert
A)
B)
C)
tas « heapBottumUp »
(a) [2, 4, 6, 8, 10, 12]
Réponse : [12, 10, 2, 8, 4, 6]
tas « heapBottumUp »
(b) [8, 5, 12, 20, 3, 7, 11]
Réponse : [20, 8, 12, 5, 3, 7, 11]
tas « heapBottumUp »
(c) [1, 6, 14, 12, 15, 8, 18]
Réponse : [18, 15, 14, 12, 6, 8, 1]
tas « heapBottumUp »
(d) [2, 7, 8, 11, 9, 9, 10]
Réponse : [11, 9, 10, 7, 2, 9, 8]
Pour chacun des tas suivants, indiquez le tas résultant (sous la forme
d’un tableau) suite à la suppression de la racine selon l’algorithme vu en classe. L’élément supprimé ne doit plus être dans le tableau.
(a) [9, 7, 6, 7, 3, 6, 2]
Réponse : [7, 7, 6, 2, 3, 6]
Pour chacun des tas suivants, indiquez le tas résultant (sous la forme
d’un tableau) suite à la suppression de la racine selon l’algorithme vu en classe. L’élément supprimé ne doit plus être dans le tableau.
(b) [11, 5, 7, 5, 4, 6, 3]
Réponse : [7, 5, 6, 5, 4, 3]
Pour chacun des tas suivants, indiquez le tas résultant (sous la forme
d’un tableau) suite à la suppression de la racine selon l’algorithme vu en classe. L’élément supprimé ne doit plus être dans le tableau.
(c) [14, 9, 10, 7, 8, 9, 6]
Réponse : [10, 9, 9, 7, 8, 6]
Pour chacun des tas suivants, indiquez le tas résultant (sous la forme
d’un tableau) suite à la suppression de la racine selon l’algorithme vu en classe. L’élément supprimé ne doit plus être dans le tableau.
(d) [12, 10, 9, 7, 8, 5, 7]
Réponse : [10, 8, 9, 7, 7, 5]
Pour chacun des tas suivants, indiquez le tas résultant (sous la forme
d’un tableau) après l’insertion de l’élément mentionné selon l’algorithme vu en classe.
(a) On ajoute 3 à [9, 7, 9, 4, 5, 6]
Réponse : [9, 7, 9, 4, 5, 6, 3]
Pour chacun des tas suivants, indiquez le tas résultant (sous la forme
d’un tableau) après l’insertion de l’élément mentionné selon l’algorithme vu en classe.
(b) On ajoute 11 à [9, 7, 9, 4, 5, 6]
Réponse : [11, 7, 9, 4, 5, 6, 9]
Pour chacun des tas suivants, indiquez le tas résultant (sous la forme
d’un tableau) après l’insertion de l’élément mentionné selon l’algorithme vu en classe.
(c) On ajoute 9 à [11, 8, 10, 7, 6, 7, 9]
Réponse : [11, 9, 10, 8, 6, 7, 9, 7]
Pour chacun des tas suivants, indiquez le tas résultant (sous la forme
d’un tableau) après l’insertion de l’élément mentionné selon l’algorithme vu en classe.
(d) On ajoute 8 à [14, 7, 7, 6, 5, 6, 4, 4, 3]
Réponse : [14, 8, 7, 6, 7, 6, 4, 4, 3, 5]
Pour chaque arbre suivant, identifiez le cas du débalancement (parmi les 4 cas possibles selon le critère AVL) qui survient après l’opération d’insertion indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement. (4 points par cas : 1 point pour le type de débalancement, 1 point pour le nœud critique et 2 points pour l’arbre AVL final).
Pour chaque arbre suivant, identifiez le cas du débalancement (parmi les 4 cas possibles selon le critère AVL) qui survient après l’opération d’insertion indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement. (4 points par cas : 1 point pour le type de débalancement, 1 point pour le nœud critique et 2 points pour l’arbre AVL final).
Pour chaque arbre suivant, identifiez le cas du débalancement (parmi les 4 cas possibles selon le critère AVL) qui survient après l’opération d’insertion indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement. (4 points par cas : 1 point pour le type de débalancement, 1 point pour le nœud critique et 2 points pour l’arbre AVL final).
Pour chaque cas ci-dessous, indiquez l’arbre résultant après avoir effectué l’opération de suppression indiqué. Utilisez l’opération de suppression telle que vue en classe. S’il y a débalancement suite à la suppression du noeud, effectuez les rotations requises selon le cas du débalancement pour que l’arbre résultant soit un arbre AVL.
Pour chaque cas ci-dessous, indiquez l’arbre résultant après avoir effectué l’opération de suppression indiqué. Utilisez l’opération de suppression telle que vue en classe. S’il y a débalancement suite à la suppression du noeud, effectuez les rotations requises selon le cas du débalancement pour que l’arbre résultant soit un arbre AVL.
Pour chaque cas ci-dessous, indiquez l’arbre résultant après avoir effectué l’opération de suppression indiqué. Utilisez l’opération de suppression telle que vue en classe. S’il y a débalancement suite à la suppression du noeud, effectuez les rotations requises selon le cas du débalancement pour que l’arbre résultant soit un arbre AVL.
Pour chaque cas ci-dessous, indiquez l’arbre résultant après avoir effectué l’opération de suppression indiqué. Utilisez l’opération de suppression telle que vue en classe. S’il y a débalancement suite à la suppression du noeud, effectuez les rotations requises selon le cas du débalancement pour que l’arbre résultant soit un arbre AVL.
