Solutions aux exercices du chapitre 8 - LabUnix

Solutions aux exercices du chapitre 8
1) Dessinez le résultat de chacune des opérations suivantes sur l'arbre-B+
de la figure suivante (prises individuellement et non pas en séquence) : [pic] a) insérer 23 [pic] b) insérer 65 [pic] c) insérer 52 [pic] d) insérer 42 [pic] e) supprimer 44 [pic] f) supprimer 40 [pic] g) supprimer 70 [pic] h) supprimer 60 [pic] i) supprimer 60 et 70 Fusion des blocs 4 et 5. Redistribution au niveau 2 pour les blocs 2 et 6. [pic] 2) Quelle est la hauteur maximale d'un arbre-B+ contenant 1000000
d'enregistrements en supposant que le facteur de blocage maximal au
niveau des feuilles est 20 et que l'ordre de l'arbre est 100. H ( 2 + log (OrdreI /2( (N /(2*(FBMf/2()) H ( 2 + log (100/2( (1000000 /(2*(20/2()) = 2 + log (50( (50000) = 4.77 3) * Faites le pseudo-code d'un itérateur pour sélection par intervalle
dans un arbre-B+. 4) Dessinez le résultat de chacune des opérations suivantes (prises
individuellement et non pas en séquence) sur l'organisation par hachage
statique avec résolution des collisions par chaînage de la figure
suivante : [pic] a) Insérer 66 [pic] b) Insérer 16 [pic] c) Insérer 53 [pic] 5) Peut-on mettre en même temps une organisation par hachage sur le
noArticle et une organisation par arbre-B+ primaire sur la description
pour le type d'enregistrement plantCatalogue ? Expliquez. Ceci est impossible parce que ce sont deux organisations primaires
différentes à moins de dupliquer les enregistrements dans les deux
organisations primaires. 6) Quels sont les avantages et inconvénients du hachage statique par
rapport à l'arbre-B+ primaire. 7) Dessinez le résultat de chacune des opérations suivantes sur
l'organisation par hachage linéaire de la figure suivante (prises
individuellement et non pas en séquence) en supposant que la fonction de
hachage est h(clé) = clé MOD 32 : [pic] a) Insérer 22 [pic] b) Insérer 51 [pic] 8) Dessinez le résultat de chacune des opérations suivantes sur
l'organisation par hachage linéaire de la figure suivante (prises
individuellement et non pas en séquence) en supposant que la fonction de
hachage est h(clé) = clé MOD 32 : [pic] a) Insérer 60 [pic] b) Insérer 73 [pic] 9) Dessinez le résultat de chacune des opérations suivantes sur
l'organisation par hachage extensible de la figure suivante (prises
individuellement et non pas en séquence) en supposant que la fonction de
hachage est h(clé) = clé MOD 32 : [pic] a) Insérer 23 [pic] b) Insérer 16 [pic]