Sujet 2012

Examen PG 2011-2012 / Structures de données avancées
Durée : 1 heure 10 mns.
Barème : 8 + 6 + 6.
Répartition en temps : 20mns + 20 mns + 30 mns 1. Arbres AVL Donner deux exemples montrant deux cas différents de déséquilibre d'un
arbre AVL lors de l'insertion d'une donnée. Pour chaque exemple, donner
l'arbre corrigé. Donner deux exemples montrant deux cas différents de déséquilibre d'un
arbre AVL lors de la suppression d'une donnée. Pour chaque exemple, donner
l'arbre corrigé. Pourquoi, il n'y a pas d'équilibrage en cascade lors de l'insertion et il
peut y avoir équilibrage en cascade lors de la suppression ? Coder une rotation droite du n?ud d'adresse P.
2. Hachage digital (HD) Considérons un fichier HD avec capacité des cases b=5. Considérer 20
données numériques de longueurs variables L ( 1 ? L ? 6) et construire le
fichier. Coder la recherche d'une donnée.
3. B-arbres distribués Concevoir un schéma de distribution d'un B-arbre selon le modèle des SDDS
en proposant une structure de données pour l'image du client. On supposera
qu'un n?ud du B-arbre est stocké dans un serveur et donc l'ordre de l'arbre
peut être très grand (10 000 par exemple). Donner les pseudo-algorithmes de
recherche d'un élément, ajustement de l'image du client, etc.