Contrôle continu LI 032
Devoir non surveillé
(facultatif)
À rendre le 17 janvier 2002
Proposer une mise en oeuvre des arbres binaires de recherche (ABR)
qui réalise les fonctions suivantes :
- Stocker tous les mots d'un texte dans un ABR, au fur et à mesure
de leur rencontre dans le fichier.
- Mesurer :
- la profondeur de l'arbre obtenu
- la profondeur théorique (log2(n), où n est le
nombre de noeuds)
- le « taux de remplissage »
- Renouveler ces statistiques avec des textes allant de quelques
lignes à plus de 50 000 mots différents.
- Proposer une stratégie de remplissage qui tente, lorsque la
profondeur est trop grande, d'obtenir un meilleur remplissage en
supprimant avant des les réinsérer les mots se trouvant dans une
position remarquable.
On demande un listing du programme, et une trace du déroulement du
programme avec les différentes valeurs mesurées dans tous les cas.
|
|
Thu Jan 10, 2002
|
|