Examen_A19 Table_disp et Tas 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.
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]
