Examen_A18 Question_brève

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

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 11

Question 12

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 12

Question 13

Answer 13

Question 14

Answer 14

Question 15

Answer 15

Question 16

Answer 16

Question 17

Answer 17

Question 18

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 18

Non

Question 19

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 19

Oui

Question 20

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 20

Oui

Question 21

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 21

Oui

Question 22

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 22

Non

Question 23

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 23

Non

Question 24

V/F

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

Answer 24

Vrai

Question 25

V/F

Le tri fusion ne tri pas sur place

Answer 25

Vrai

Question 26

V/F

Le tri par tas n’est pas stable.

Answer 26

Vrai

Question 27

V/F

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

Answer 27

Vrai

Question 28

V/F

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

Answer 28

Vrai

Question 29

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

Answer 29

Vrai