CCSE 2000 informatique classe prepa mp

Description

Concours Centrale - Supélec 2000 Épreuve : I N FOR MATIQU E Filière MP - Soit n, = (n E n, est l'ensemble des fils de n, . On Note :Toutes les réponses doivent être justifiées. - {n,})lp(n) = nl . i i Note :Vous indiquerez, au début de votre copie, si vous choisissez de rëdiger vos appelle degré de n le cardinal de !F , et degré maximal de l'arbre le plus grand programmes en PASCAL ou en CAML. des degrés des nœuds. -soit ~~,={ns~l 3xEIN,p"(n)=n, . Partie I - Algorithmique 1 Dans cette partie, on s'intéressè aux arbres bicolores qui sont une classe Si pn, est la restriction de p à Nn1, alors (Nn,, nl,pnl) est un arbre, dit sous- particulière des arbres binaires de recherche. arbre de A de racine nl . - La profondeur d'un nœud n est l'entier x E IN tel que p"(n) = no. La hauteur 1.A - Rappels et Notations d'un arbre est la profondeur maximale de ses nœuds. I.A.l) Définitions - Un arbre ordonné est un arbre auquel on adjoint à chaque nœud un ordre to- Un arbre est un triplet A = (N, no, p) où : tal sur ses fils. - % est un ensemble fini dont les éléments sont appelés nœuds. - Un arbre n-aire est un arbre ordonné dont chaque nœud a exactement n fils - no est un élément particulier de appelé racine. (certains des fils pouvant être des arbres vides). - p est une fonction, nommée père, de N - (no} dans !7( ayant la propriété - Un arbre binaire est un arbre 2-aire. On nomme classiquement fils droit et suivante : fils gauche les deux fils de chaque nœud. 'dn ...

Informations

• Publié par: aiolos
• Nombre de lectures: 151
• Langue: Français

Extrait