Final

Question 1

Quel est le type d’adressage qui utilise EMPTY, DELETED et ACTIVE?

Answer 1

Adressage ouvert

Question 2

Description état EMPTY?

Answer 2

Indique que cette entrée est vide et n’a jamais contenu une clé.

Question 3

Description état ACTIVE

Answer 3

Indique que cette entrée contient une clé valide.

Question 4

Description état EMPTY

Answer 4

Indique que cette entrée est vide et n’a jamais contenu une clé.

Question 5

Pour l’adressage ouvert, les opérations d’insertion, suppression et insertions utilise la fonction TrouverPosition(x) qui effectue une séquence de sondages de la table de dispersion et s’arrête sur la première entrée de cette séquence satisfaisant une propriété. De quelle propriété s’agit-il?

Answer 5

TrouverPosition(x) s’arrête sur la première case dans l’état EMPTY ou une case contenant la clé x qui est dans l’état DELETED ou ACTIVE.

Question 6

Comment cette séquence de sondages est-elle effectuée pour le sondage quadratique?

Answer 6

La séquence de cases sondées est h0(x), h1(x), h2(x), … avec hi(x) = (h(x) + i2) mod N pour une
fonction de hachage h et une table de dispersion avec N indexes.

Question 7

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?

Answer 7

Soit hi(x), la case où TrouverPosition(x) s’est arrêté.

Pour Trouver(x) : on retourne vrai si hi(x) est ACTIVE et contient x. Si non (dans ce cas hi(x) est dans l’état EMPTY ou DELETED), on retourne faux. Dans tous les cas le champ état n’est pas
modifié. (3 points)

Question 8

Lorsque TrouverPosition(x) est arrêté sur une entrée de
la table, quelle est la valeur booléenne retournée par Supprimer(x) et comment le champ état est-il modifié en fonction de l’état initial de cette entrée et de la clé x?

Answer 8

on retourne faux si hi(x) est dans l’état EMPTY ou DELETED et le champ état n’est pas modifié. Si non (dans ce cas hi(x) est dans l’état ACTIVE et contient x), on
retourne vrai et on change l’état à DELETED.

Question 9

En vous servant du fait que dans un tas que tous les niveaux sont pleins, sauf possiblement le dernier, démontrez qu’un tas de n nœuds possède une hauteur h ≤ log2(n).

Answer 9

Considérez un tas de n nœuds possédant L nœuds au dernier niveau (le niveau h).
Nous avons alors:
* n = 20 + 21 + … 2h-1 + L avec: 1 ≤ L ≤ 2h
* Alors: n = 2h – 1 + L
Alors:
* L ≥ 1 ⇒ n ≥ 2h ⇒ h ≤ log2(n)

Question 10

En vous servant du fait que dans un tas que tous les niveaux sont pleins, sauf possiblement le dernier, démontrez qu’un tas de n nœuds possède une hauteur h ≥ log2(n+1) - 1.

Answer 10

Considérez un tas de n nœuds possédant L nœuds au dernier niveau (le niveau h).
Nous avons alors:
* n = 20 + 21 + … 2h-1 + L avec: 1 ≤ L ≤ 2h
* Alors: n = 2h – 1 + L
Alors:
* L ≤ 2h ⇒ n ≤ 2h+1 – 1 ⇒ h ≥ log2(n+1) – 1.

Question 11

Enlever racine : [8, 8, 7, 6, 6]

Answer 11

[8, 6, 7, 6]

Question 12

Enlever racine : [9, 8, 9, 8, 7, 6]

Answer 12

[9, 8, 6, 8, 7]

Question 13

Enlever racine : [8, 7, 6, 6, 5, 5, 4]

Answer 13

[7, 6, 6, 4, 5, 5]

Question 14

Enlever racine : [8, 7, 6, 5, 4, 3, 2]

Answer 14

[7, 5, 6, 2, 4, 3]

Question 15

On ajoute 7 à [8, 7, 6, 5, 4]

Answer 15

Réponse : [8, 7, 7, 5, 4, 6]

Question 16

On ajoute 9 à [8, 7, 6, 5, 4]

Answer 16

Réponse : [9, 7, 8, 5, 4, 6

Question 17

On ajoute 9 à [9, 8, 7, 7, 6, 5, 6]

Answer 17

Réponse : [9, 9, 7, 8, 6, 5, 6, 7]

Question 18

On ajoute 6 à [8, 7, 6, 5, 5, 5, 5]

Answer 18

Réponse : [8, 7, 6, 6, 5, 5, 5, 5]

Question 19

V-F : Le tri par insertion est en Q(n2) dans tous les cas.

Answer 19

Faux

Question 20

V-F : Le tri par insertion n’est pas stable

Answer 20

Faux

Question 21

V-F : Le tri par tas ne trie pas sur place

Answer 21

Faux

Question 22

V-F : Le tri fusion est en Q(n log(n)) en meilleur cas

Answer 22

Vrai

Question 23

V-F : Le tri fusion est stable.

Answer 23

Vrai

Question 24

V-F : Le tri de base est en O(n) dans tous les cas.

Answer 24

Vrai

Question 25

V-F : Le tri par tas est en O(n) en meilleur cas.

Answer 25

Vrai

Question 26

V-F : Le tri de base ne trie pas sur place.

Answer 26

Vrai

Question 27

Si les indexes débutent à 1, à quelle position (ou indexe) doit se trouver le premier nœud du niveau h s’il est présent? Exprimez votre réponse en fonction de h.

Answer 27

Le premier nœud du niveau h doit être positionné immédiatement après les nœuds des niveaux précédents. Le nombre total de nœuds compris dans les niveaux de 0 à h-1 est donc donnée par :
=>(3^h-1)/2

selon la série géométrique de l’aide mémoire (avec r = 3 et n = h 1).
Puisque le premier noeud du niveau h doit se trouver immédiatement après tous
ces noeud, sa position (ou indexe) est donnée par :
=> ((3^h-1)/2)-1
=> (3^h+1)/2
=> j

Question 28

Si j dénote la position de ce nœud (le premier nœud au niveau h), à quelle position (ou indexe), en fonction de j, doit alors se trouver chacun des enfants de ce nœud s’ils sont présents?

Answer 28

L’enfant le plus a gauche de ce nœud est le premier nœud du niveau h+1. Il doit donc se trouver a la position donnée par le résultat précèdent en remplaçant h par h + 1. Cet enfant le plus à gauche doit donc se trouver en position.

=>3^(h+1)+1/2 = 3j - 1

Les deux autres enfants se trouvent alors en position 3j et 3j + 1.

Question 29

Si i dénote la position du nœud parent (le premier nœud du niveau h) lorsque les indexes débutent à 0, quelles sont alors les positions des nœuds enfants exprimées en fonction de i?

Answer 29

Lorsque les indexes débutent en 0, le nœud parent est alors en position i = j1.
L’enfant le plus `a gauche est alors en position

(3j - 1) - 1 = 3j - 2 = 3(i + 1) - 2 = 3i + 1.

Les deux autres enfants sont donc en positions 3i + 2 et 3i + 3.