Examen_H18 COMPLET Flashcards

1
Q

L’adressage ouvert nécessite l’utilisation d’un champ « état » pour décrire l’état de l’entrée d’une
table. Décrivez quels sont les états possibles.

A

L’état ACTIVE : Indique que cette entrée contient une clé valide (2 points)
L’état DELETED : Indique que cette entrée a déjà contenu une clé valide, mais elle a été
supprimée (2 points)
L’état EMPTY : Indique que cette entrée est vide et n’a jamais contenu une clé. (2 points)

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

REGARDER IMAGE DE LA QUESTION 2

En continuité avec la question précédente, lorsque TrouverPosition(x) est arrêté sur une entrée de la
table, quelle est la valeur booléenne retournée par Trouver(x) et comment le champ état est-il modifié
en fonction de l’état initial de cette entrée et de la clé x? Même question pour Supprimer(x) et pour
Insérer(x). (9 points)

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q
A
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

Cette question concerne les tas max (i.e., les monceaux)

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

Cette question concerne les tas max (i.e., les monceaux).

(b) Si on enlève la racine du tas max constitué du tableau
[10, 8, 5, 7, 4, 1], dessinez la représentation arborescente du tas résultant.

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

Cette question concerne les tas max (i.e., les monceaux).

(c) Si on enlève la racine du tas max constitué du tableau
[15, 8, 14, 3, 6], dessinez la représentation arborescente du tas résultant.

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

Cette question concerne les tas max (i.e., les monceaux).

(d) Si on ajoute l’élément 8 au tas max [13, 10, 7, 8, 6], dessinez la représentation arborescente du tas résultant.

A
17
Q

Cette question concerne les tas max (i.e., les monceaux).

(e) Si on ajoute l’élément 11 au tas max [10, 9, 7, 8], dessinez la représentation arborescente du tas résultant.

A
18
Q

4 cas possibles selon le critère AVL

Pour chaque arbre suivant, identifiez le cas du débalancement : le nœud critique, le nœud sous-critique, et l’arbre AVL résultant après avoir corrigé le
débalancement.

CAS 1

A
19
Q

4 cas possibles selon le critère AVL

Pour chaque arbre suivant, identifiez le cas du débalancement : le nœud critique, le nœud sous-critique, et l’arbre AVL résultant après avoir corrigé le
débalancement.

CAS 2

A
20
Q

4 cas possibles selon le critère AVL

Pour chaque arbre suivant, identifiez le cas du débalancement : le nœud critique, le nœud sous-critique, et l’arbre AVL résultant après avoir corrigé le
débalancement.

CAS 3

A
21
Q

4 cas possibles selon le critère AVL

Pour chaque arbre suivant, identifiez le cas du débalancement : le nœud critique, le nœud sous-critique, et l’arbre AVL résultant après avoir corrigé le
débalancement.

CAS 4

A
22
Q

Arbre AVL

Supposons que vous désirez supprimer l’élément 11 de l’arbre AVL suivant. Illustrez les différentes
étapes de reconstruction de l’arbre menant à la suppression de cet élément.

A
23
Q

Vrai ou Faux, triage

Le temps d’exécution du tri par insertion est en Ω(n²).

A

FAUX

24
Q

Vrai ou Faux, triage

Le temps d’exécution du tri de base en O(n)

A

VRAI

25
Q

Vrai ou Faux, triage

Le temps d’exécution du tri par tas est en Θ(n log n)

A

FAUX

26
Q

Vrai ou Faux, triage

Le temps d’exécution du tri fusion est en Θ(n log n)

A

VRAI

27
Q

Vrai ou Faux, triage

Le tri par insertion est stable.

A

VRAI

28
Q

Vrai ou Faux, triage

Le tri fusion se fait sur place.

A

FAUX

29
Q

Vrai ou Faux, triage

Le tri de base se fait sur place.

A

FAUX

30
Q

Vrai ou Faux, triage

Le tri fusion est stable.

A

VRAI

31
Q

Vrai ou Faux, triage

Le tri par tas est stable.

A

FAUX

32
Q

Vrai ou Faux, triage

Le tri par insertion ne se fait pas sur place.

A

FAUX