Examen_A19 COMPLET

Question 1

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.

Answer 1

Question 2

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.

Answer 2

Question 3

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.

Answer 3

Question 4

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.

Answer 4

Question 5

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.

Answer 5

Question 6

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.

Answer 6

Question 7

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.

Answer 7

Question 8

Cette question porte sur l’adressage ouvert

Answer 8

Question 9

Cette question porte sur l’adressage ouvert

Answer 9

Question 10

A)

Answer 10

Question 11

B)

Answer 11

Question 12

C)

Answer 12

Question 13

tas « heapBottumUp »

(a) [2, 4, 6, 8, 10, 12]

Answer 13

Réponse : [12, 10, 2, 8, 4, 6]

Question 14

tas « heapBottumUp »

(b) [8, 5, 12, 20, 3, 7, 11]

Answer 14

Réponse : [20, 8, 12, 5, 3, 7, 11]

Question 15

tas « heapBottumUp »

(c) [1, 6, 14, 12, 15, 8, 18]

Answer 15

Réponse : [18, 15, 14, 12, 6, 8, 1]

Question 16

tas « heapBottumUp »

(d) [2, 7, 8, 11, 9, 9, 10]

Answer 16

Réponse : [11, 9, 10, 7, 2, 9, 8]

Question 17

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]

Answer 17

Réponse : [7, 7, 6, 2, 3, 6]

Question 18

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]

Answer 18

Réponse : [7, 5, 6, 5, 4, 3]

Question 19

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]

Answer 19

Réponse : [10, 9, 9, 7, 8, 6]

Question 20

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]

Answer 20

Réponse : [10, 8, 9, 7, 7, 5]

Question 21

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]

Answer 21

Réponse : [9, 7, 9, 4, 5, 6, 3]

Question 22

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]

Answer 22

Réponse : [11, 7, 9, 4, 5, 6, 9]

Question 23

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]

Answer 23

Réponse : [11, 9, 10, 8, 6, 7, 9, 7]

Question 24

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]

Answer 24

Réponse : [14, 8, 7, 6, 7, 6, 4, 4, 3, 5]

Question 25

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).

Answer 25

Question 26

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).

Answer 26

Question 27

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).

Answer 27

Question 28

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.

Answer 28

Question 29

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.

Answer 29

Question 30

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.

Answer 30

Question 31

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.

Answer 31