Examen_A18 Question_brève Flashcards
V/F
Pour le chainage externe, le taux d’occupation doit être maintenu à au plus ½.
Faux
V/F
Le chainage externe nécessite l’utilisation d’un champ « état » pour spécifier l’état dans lequel se
trouve une clé.
Faux
V/F
Pour le sondage quadratique, le taux d’occupation doit être maintenu à au plus ½.
Vrai
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.
Faux
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.
Vrai
V/F
Le hachage universel est réalisable seulement lorsque la distribution des clés est statique.
Faux
V/F
Le hachage universel nécessite l’utilisation d’un champ « état » pour spécifier l’état dans lequel se trouve une clé.
Faux
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.
Faux
V/F
Le hachage universel consiste à utiliser une fonction de hachage universelle pour le hachage de clés.
Faux
V/F
L’adressage ouvert nécessite l’utilisation d’un champ « état » pour spécifier l’état dans lequel se trouve une clé.
Vrai
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?
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?
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]
Non
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]
Oui
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]
Oui
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]
Oui
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]
Non
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]
Non
V/F
Le tri par tas est en Ω(n) et en O(n Log(n)).
Vrai
V/F
Le tri fusion ne tri pas sur place
Vrai
V/F
Le tri par tas n’est pas stable.
Vrai
V/F
Le tri fusion est en Θ( n log(n)) en meilleur cas.
Vrai
V/F
Le tri par insertion est en O(n) en meilleur cas.
Vrai
Le tri de base est en O(n) en pire cas
Vrai
