Examen_A18 COMPLET

Question 1

V/F

Pour le chainage externe, le taux d’occupation doit être maintenu à au plus ½.

Answer 1

Faux

Question 2

V/F

Le chainage externe nécessite l’utilisation d’un champ « état » pour spécifier l’état dans lequel se
trouve une clé.

Answer 2

Faux

Question 3

V/F

Pour le sondage quadratique, le taux d’occupation doit être maintenu à au plus ½.

Answer 3

Vrai

Question 4

V/F

L’insertion peut boucler indéfiniment si nous utilisons le chainage externe et une table dont le nombre d’entrées n’est pas un nombre premier.

Answer 4

Faux

Question 5

V/F

L’insertion peut boucler indéfiniment si nous utilisons le sondage quadratique et une table dont le nombre d’entrées n’est pas un nombre premier.

Answer 5

Vrai

Question 6

V/F

Le hachage universel est réalisable seulement lorsque la distribution des clés est statique.

Answer 6

Faux

Question 7

V/F

Le hachage universel nécessite l’utilisation d’un champ « état » pour spécifier l’état dans lequel se trouve une clé.

Answer 7

Faux

Question 8

V/F

Nous sommes en situation de hachage parfait lorsque le temps d’exécution pour les recherches dans une table contenant n clés est en O(log(n)) en pire cas.

Answer 8

Faux

Question 9

V/F

Le hachage universel consiste à utiliser une fonction de hachage universelle pour le hachage de clés.

Answer 9

Faux

Question 10

V/F

L’adressage ouvert nécessite l’utilisation d’un champ « état » pour spécifier l’état dans lequel se trouve une clé.

Answer 10

Vrai

Question 11

Answer 11

Question 12

Answer 12

Question 13

Answer 13

Question 14

Answer 14

Question 15

Answer 15

Question 16

Answer 16

Question 17

Answer 17

Question 18

Answer 18

Question 19

En utilisant votre réponse de l’image ci-dessous, que pouvez-vous dire de la longueur attendue de la liste à l’entrée h(x) lorsque x n’est pas parmi les n clés?

Answer 19

Question 20

En utilisant votre réponse de l’image ci-dessous, que pouvez-vous dire de la longueur attendue de la liste à l’entrée h(x) lorsque x est parmi les n clés?

Answer 20

Question 21

Answer 21

Question 22

Answer 22

Question 23

Answer 23

Question 24

Answer 24

Question 25

Answer 25

Question 26

Answer 26

Question 27

Answer 27

Question 28

Answer 28

Question 29

Dites si oui ou non il s’agit d’un tas (satisfaisant la propriété du tas_max)

[1, 2, 3, 4, 5, 6, 7]

Answer 29

Non

Question 30

Dites si oui ou non il s’agit d’un tas (satisfaisant la propriété du tas_max)

[7, 6, 5, 4, 3, 2, 1]

Answer 30

Oui

Question 31

Dites si oui ou non il s’agit d’un tas (satisfaisant la propriété du tas_max)

[6, 6, 6, 6, 6, 6, 6]

Answer 31

Oui

Question 32

Dites si oui ou non il s’agit d’un tas (satisfaisant la propriété du tas_max)

[9, 5, 7, 5, 3, 6, 2]

Answer 32

Oui

Question 33

Dites si oui ou non il s’agit d’un tas (satisfaisant la propriété du tas_max)

[8, 5, 6, 5, 6, 6, 3]

Answer 33

Non

Question 34

Dites si oui ou non il s’agit d’un tas (satisfaisant la propriété du tas_max)

[8, 6, 7, 5, 7, 7, 6]

Answer 34

Non

Question 35

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.

[9, 9, 8, 7, 4]

Answer 35

Réponse : [9, 7, 8, 4]

Question 36

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.

[11, 9, 8, 8, 6, 5]

Answer 36

Réponse : [9, 8, 8, 5, 6]

Question 37

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.

[10, 7, 9, 6, 5, 2, 8]

Answer 37

Réponse : [9, 7, 8, 6, 5, 2]

Question 38

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.

On ajoute 7 à [9, 7, 5, 6, 2]

Answer 38

Réponse : [9, 7, 7, 6, 2, 5]

Question 39

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.

On ajoute 9 à [8, 6, 6, 4, 2, 3]

Answer 39

Réponse : [9, 6, 8, 4, 2, 3, 6]

Question 40

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.

On ajoute 10 à [11, 9, 8, 8, 7, 5, 6]

Answer 40

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

Question 41

Pour l’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 indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement.

Answer 41

Question 42

Pour l’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 indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement.

Answer 42

Question 43

Pour l’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 indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement.

Answer 43

Question 44

Pour l’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 indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement.

Answer 44

Question 45

Pour l’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 indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement.

Answer 45

Question 46

Pour l’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 indiqué. Identifiez le nœud critique et l’arbre AVL résultant après avoir corrigé le débalancement.

Answer 46

Question 47

V/F

Le tri par tas est en Ω(n) et en O(n Log(n)).

Answer 47

Vrai

Question 48

V/F

Le tri fusion ne tri pas sur place

Answer 48

Vrai

Question 49

V/F

Le tri par tas n’est pas stable.

Answer 49

Vrai

Question 50

V/F

Le tri fusion est en Θ( n log(n)) en meilleur cas.

Answer 50

Vrai

Question 51

V/F

Le tri par insertion est en O(n) en meilleur cas.

Answer 51

Vrai

Question 52

Le tri de base est en O(n) en pire cas

Answer 52

Vrai