Examen_A18 COMPLET 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
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]
Réponse : [9, 7, 8, 4]
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]
Réponse : [9, 8, 8, 5, 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.
[10, 7, 9, 6, 5, 2, 8]
Réponse : [9, 7, 8, 6, 5, 2]
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]
Réponse : [9, 7, 7, 6, 2, 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.
On ajoute 9 à [8, 6, 6, 4, 2, 3]
Réponse : [9, 6, 8, 4, 2, 3, 6]
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]
Réponse : [11, 10, 8, 9, 7, 5, 6, 8]
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.
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.
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.
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.
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.
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.
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
