UTBM theorie de la programmation tda et structures de donnees 2005 gi

Description

UTBM le 16 janvier 2006 Final – LO42 Les documents sont autorisés (La copie ou les idées du voisin non). Le barème est indicatif. Le soin donné à la rédaction sera évalué. Toute réponse devra être claire et justifiée (toute ambiguïté sera mal interprétée). L’élégance de la solution sera jugée. Sauf indication contraire, dans le cas d’algorithmes, les réponses doivent être rédigées en pseudo code. L’exercice 3 est à faire sur une feuille séparée 1) La multiplication des pins (5) (en Java) Voici une classe java : public class ArbreBinaire { public ArbreBinaire droit() { return d; } Object r; // la racine de l'arbre public ArbreBinaire setDroit(ArbreBinaire a) { ArbreBinaire g, d; // les sous-arbres return (d = a); } protected ArbreBinaire(Object r, ArbreBinaire g, ArbreBinaire d) { // construction de l'arbre : a = f.cons(r,d) this.r = r; public ArbreBinaire cons(Object r, ArbreBinaire d) { this.g = g; return new ArbreBinaire (r,this, d); this.d = d; } } protected ArbreBinaire(Object r) { this(r,creer,creer); } /** Le seul moyen d'initialiser un nouvel arbre binaire : protected ArbreBinaire() { this(null,creer,creer); } * ArbreBinaire a = ArbreBinaire.creer; */ public Object racine() { return r; } static public final ArbreBinaire creer = new ArbreBinaire (); public Object setRacine(Object r) { return (this.r = r) ; } public boolean estVide() { public ArbreBinaire gauche() { return g; } ...

Informations

• Publié par: shura
• Nombre de lectures: 126
• Langue: Français

Extrait

UTBM

le 16 janvier 2006

Final –LO42 Les documents sont autorisÈs (La copie ou les idÈes du voisin non). Le barËme est indicatif. Le soin donnÈ ‡ la rÈdaction sera ÈvaluÈ. Toute rÈponse devra Ítre claire et justifiÈe (toute ambiguÔtÈ sera mal interprÈtÈe). L’ÈlÈgance de la solution sera jugÈe. Sauf indication contraire, dans le cas d’algorithmes, les rÈponses doivent Ítre rÈdigÈes en pseudo code. L’exercice 3 est ‡ faire sur une feuille sÈparÈe 1) Lamultiplication des pins (5) (en Java) Voici une classe java : public class ArbreBinaire {public ArbreBinaire droit() { return d; }  Objectr; //la racine de l'arbrepublic ArbreBinaire setDroit(ArbreBinaire a) {  ArbreBinaireg, d;// les sousarbresreturn (d = a);  }  protectedArbreBinaire(Object r, ArbreBinaire g, ArbreBinaire d) {// construction de l'arbre : a = f.cons(r,d)  this.r= r;public ArbreBinaire cons(Object r, ArbreBinaire d) {  this.g= g;return new ArbreBinaire (r,this, d);  this.d= d;}  }  protectedArbreBinaire(Object r) { this(r,creer,creer); }/** Leseulmoyen d'initialiser un nouvel arbre binaire :  protectedArbreBinaire() { this(null,creer,creer); }* ArbreBinairea = ArbreBinaire.creer;  */  publicObject racine() { return r; }static public final ArbreBinaire creer = new ArbreBinaire ();  publicObject setRacine(Object r) { return (this.r = r) ; }  publicboolean estVide() {  publicArbreBinaire gauche() { return g; }return this == creer;  }  publicArbreBinaire setGauche(ArbreBinaire a) {  return(g = a);  } a) Ajoutezune mÈthode permettant de cloner l’arbre binaire. b) Supposezque le type dern’est plusObjectmaisint. Ajoutez une mÈthode permettant de vÈrifier que l’arbre a la propriÈtÈ de maxtas. (On ne se prÈoccupe pas de savoir si l’arbre est quasi parfait) 2) Lapousse tirÈe par les cheveux (7) Nous travaillons sur une application de recherche prÈsentant comme particularitÈ que les derniers ÈlÈments introduits sont les ÈlÈments les plus demandÈs. Nous souhaitons donc insËrer dans un arbre de recherche un ÈlÈment non pas comme une feuille mais ‡ la racine afin que la recherche des derniers ÈlÈments introduits soit la plus rapide possible. Voici par exemple un arbre binaire dans lequel nous insÈrons la valeur 23. 23 15 30 12 30 15 35 25 35 12 25 20 40 29 40 20 29 a) Vousdevez Ècrire la sÈquence permettant de partager l’arbre existant en deux sous arbresgaucheetdroit

lo42  final A2005  page1/3