Final Flashcards
Quel est le type d’adressage qui utilise EMPTY, DELETED et ACTIVE?
Adressage ouvert
Description état EMPTY?
Indique que cette entrée est vide et n’a jamais contenu une clé.
Description état ACTIVE
Indique que cette entrée contient une clé valide.
Description état EMPTY
Indique que cette entrée est vide et n’a jamais contenu une clé.
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?
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.
Comment cette séquence de sondages est-elle effectuée pour le sondage quadratique?
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.
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?
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)
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?
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.
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).
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)
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.
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.
Enlever racine : [8, 8, 7, 6, 6]
[8, 6, 7, 6]
Enlever racine : [9, 8, 9, 8, 7, 6]
[9, 8, 6, 8, 7]
Enlever racine : [8, 7, 6, 6, 5, 5, 4]
[7, 6, 6, 4, 5, 5]
Enlever racine : [8, 7, 6, 5, 4, 3, 2]
[7, 5, 6, 2, 4, 3]
On ajoute 7 à [8, 7, 6, 5, 4]
Réponse : [8, 7, 7, 5, 4, 6]
On ajoute 9 à [8, 7, 6, 5, 4]
Réponse : [9, 7, 8, 5, 4, 6
On ajoute 9 à [9, 8, 7, 7, 6, 5, 6]
Réponse : [9, 9, 7, 8, 6, 5, 6, 7]
On ajoute 6 à [8, 7, 6, 5, 5, 5, 5]
Réponse : [8, 7, 6, 6, 5, 5, 5, 5]
V-F : Le tri par insertion est en Q(n2) dans tous les cas.
Faux
V-F : Le tri par insertion n’est pas stable
Faux
V-F : Le tri par tas ne trie pas sur place
Faux
V-F : Le tri fusion est en Q(n log(n)) en meilleur cas
Vrai
V-F : Le tri fusion est stable.
Vrai
V-F : Le tri de base est en O(n) dans tous les cas.
Vrai
V-F : Le tri par tas est en O(n) en meilleur cas.
Vrai
V-F : Le tri de base ne trie pas sur place.
Vrai
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.
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
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?
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.
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?
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.
