Examen_A18 COMPLET Flashcards

1
Q

V/F

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

A

Faux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

V/F

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

A

Faux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

V/F

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

A

Vrai

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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.

A

Faux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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.

A

Vrai

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

V/F

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

A

Faux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

V/F

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

A

Faux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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.

A

Faux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

V/F

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

A

Faux

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

V/F

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

A

Vrai

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
26
27
28
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]
Non
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]
Oui
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]
Oui
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]
Oui
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]
Non
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]
Non
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]
Réponse : [9, 7, 8, 4]
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]
Réponse : [9, 8, 8, 5, 6]
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]
Réponse : [9, 7, 8, 6, 5, 2]
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]
Réponse : [9, 7, 7, 6, 2, 5]
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]
Réponse : [9, 6, 8, 4, 2, 3, 6]
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]
Réponse : [11, 10, 8, 9, 7, 5, 6, 8]
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.
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.
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.
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.
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.
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.
47
# V/F Le tri par tas est en Ω(n) et en O(n Log(n)).
Vrai
48
# V/F Le tri fusion ne tri pas sur place
Vrai
49
# V/F Le tri par tas n’est pas stable.
Vrai
50
# V/F Le tri fusion est en Θ( n log(n)) en meilleur cas.
Vrai
51
# V/F Le tri par insertion est en O(n) en meilleur cas.
Vrai
52
Le tri de base est en O(n) en pire cas
Vrai