Exercice 1 : ABR : algorithmes et complexités (20 points) Rappels : Les Arbres Binaires de Recherche (ABR) sont des arbres binaires qui satisfont la propriété
| Previous PDF | Next PDF |
[PDF] TP 8 : Arbres binaires de recherche - Cedric-Cnam
Exercice 1 Définir une structure struct noeud_s permettant de coder un n÷ud d' un arbre binaire contenant une valeur entière Ajouter des typedef pour définir
[PDF] Exercice sur les arbres binaires de recherche
A-Rappelez les propriétés des arbres binaires de recherche B-Rappelez ce qu' est l'opération d'adjonction aux feuilles C-Construire l'arbre binaire de recherche
[PDF] SUJET + CORRIGE
Exercice 1 : ABR : algorithmes et complexités (20 points) Rappels : Les Arbres Binaires de Recherche (ABR) sont des arbres binaires qui satisfont la propriété
[PDF] Les arbres binaires de recherche
Exercice 3 Écrire une fonction Hauteur(x) prenant un arbre binaire et rendant sa hauteur, c'est à dire le nombre d'éléments
[PDF] TP 10 Arbres binaires de recherche - Normale Sup
Exercice 1 Définir une structure struct noeud_s permettant de coder un n÷ud d' un arbre binaire contenant une valeur entière Ajouter des typedef pour définir
[PDF] Travaux Dirigés Exercices corrigés sur les arbres
Solution de l'exercice 1 1 Exercices corrigés sur les arbres Soit le tableau suivant qui représente un arbre binaire T en triplets (info, gauche, droit) :
[PDF] TD : Arbres Binaires de Recherche (ABR) - ISIMA
Les exercices sont inspirés de [1] Dans toute la suite nous supposerons qu'un arbre binaire de recherche self est construit récursivement par l'utilisation de
[PDF] TD5 : Arbres Binaires
Tout noeud du sous-arbre gauche de N a une valeur inférieure à n Exercice 4 Écrire la fonction qui vérifie si un arbre donné est bien un arbre binaire de
[PDF] TD No3
Exercice 1 arbres binaires Exercice 2 arbres binaires de recherche Dessinez l'arbre binaire de recherche obtenu par ajout successif aux feuilles des
[PDF] TD7
Cette séance de Travaux dirigée est consacrée à l'étude du type de donnée arbre binaire Exercice 1 (Arbres binaires) 1 Implanter la spécification ABin en
[PDF] arbre binaire de recherche en c
[PDF] les arbres en c openclassroom
[PDF] arbre binaire de recherche algorithme
[PDF] arbre binaire de recherche algorithme suppression
[PDF] parcours en profondeur arbre
[PDF] arbre binaire complet
[PDF] dénombrement cours
[PDF] arbre de probabilité pile ou face
[PDF] arbre de probabilité seconde
[PDF] arbre probabilité conditionnelle
[PDF] arbre de décision exercices corrigés
[PDF] arbre de décision data mining
[PDF] cours arbre de décision
[PDF] classification par arbre de décision
Master BioInformatiqueAnn
ee :2012/2013Semestre de decembre 2012PARCOURS :Master 1
UE J1BS7202 :Algorithmique et Programmation
Epreuve :Examen
Date :Lundi 17 decembre 2012
Heure :10 heures
Duree :2 heures
Documents : autorises
Epreuve de M. AlainGriffaultSUJET + CORRIGE
Avertissement
La plupart des questions son t
independantes.V ousp ouvezau c hoixutiliser un langage
algorithmiqueou bien lelangage python pour repondre aux questions.L'espace laiss ep ourles r eponsesest suf-
sant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement deconseille).QuestionPointsScoreABR : algorithmes et complexites20
Total:20
Exercice 1 : ABR : algorithmes et complexites (20 points) Rappels :Les Arbres Binaires de Recherche (ABR) sont des arbres binaires qui satisfont la propriete suivante :8Nun nud de l'arbre,8Gun nud du sous arbre gauche deN,8Dun nud du sous arbre droit deN,G:infoN:infoD:info, ouinfoest une valeur entiere servant a comparer les nuds. Voici pour memoire une version python de deux algorithmes vus en cours sur les ABR. defminimumABR(A): ifA==None: returnNone else:Aux = A
whileAux. fg!=None:Aux = Aux. fg
returnAuxdefsuccesseurABR(A,P): # P doit etre un noeud non nil de A ifP. fd!=None: returnminimumABR(P. fd ) else:Aux = P
AuxPere = P. pere
whileAuxPere!=NoneandAuxPere . fd==Aux:Aux = AuxPere
AuxPere = Aux. pere
returnAuxPere (a) (2 p oints)En v ousinspiran tde la fonction minimumABR(A)vue en cours, ecrire une fonction iterative maximumABR(A)qui retourne un pointeur sur le nud de l'arbreApossedant la plus grande valeur entiere s'il existe, la valeurnilsinon.Solution:
defmaximumABR(A): ifA==None: returnNone else:Aux = A
whileAux. fd!=None:Aux = Aux. fd
returnAux(b)(2 p oints)Donner et justier les c omplexites(pire des cas et meilleur des cas) de v otrefonction
maximumABR(A)en fonction du nombre de nudsnou de la hauteurhde l'arbreA. UE J1BS7202 : Algorithmique et Programmation Examen, Annee 2012/2013Solution:
Meilleur des cas :
(1) lorsque An'a pas de ls droit. Pire des cas : ( O)(n) lorsqueAn'a qu'une descendance par ses ls droits. La hauteurhde l'arbreest alors egale an.(c)(3 p oints)En v ousin spirantde la fonction successeurABR(A,P)vue en cours, ecrire une fonction
predecesseur(A,P)qui retourne un pointeur sur le nud possedant la valeur qui precede la valeur contenue dansP.Solution:
defpredecesseurABR(A,P): # P doit etre un noeud non nil de A ifP. fg!=None: returnmaximumABR(P. fg ) else:Aux = P
AuxPere = P. pere
whileAuxPere!=NoneandAuxPere . fg==Aux:Aux = AuxPere
AuxPere = Aux. pere
returnAuxPere(d)(2 p oints)Donner et justier les c omplexites(pire des cas et meilleur des cas) de v otrefonction
predecesseurABR(A,P)en fonction du nombre de nudsnou de la hauteurhde l'arbreA.Solution:
Meilleur des cas :
(1) lorsque Pa un ls gauche qui n'a pas de ls droit. Pire des cas : ( O)(n) lorsquePest la racine, qu'il n'a pas de ls droit, qu'il a un ls gauche quin'a qu'une descendance par ses ls droits. La hauteurhde l'arbre est alors egale an.(e)(3 p oints)En utilisan tles fonctions minimumABR(A)etsuccesseurABR(A,P)vues en cours, ecrire une
fonction iterativeafficherCroissantABR(A)qui ache les valeurs de l'arbre binaire de rechercheA en ordre croissant.Solution:
defafficherCroissantABR (A): ifA!=None:Aux = minimumABR(A)
whileAux!=None: print(Aux. info )Aux = successeurABR(A,Aux)(f)(2 p oints)Donner et justier les complexit es(pire des c aset meilleur des cas) de v otrefonction
afficherCroissantABR(A)en fonction du nombre de nudsnou de la hauteurhde l'arbreA.Solution:
Meilleur des cas :
( n).Pire des cas : ( O)(n).
Soit : Theta(n)(g)(2 p oints)En utilisan tles fonctions maximumABR(A)etpredecesseurABR(A,P)vues en cours, ecrire
une fonction iterativeafficherDecroissantABR(A)qui ache les valeurs de l'arbre binaire de re- chercheAen ordre decroissant.Solution:
defafficherDecroissantABR (A): ifA!=None:Aux = maximumABR(A)
whileAux!=None:Page 2 sur 3 UE J1BS7202 : Algorithmique et Programmation Examen, Annee 2012/2013 print(Aux. info )Aux = predecesseurABR(A,Aux)(h)(2 p oints)
Ecrire une fonction recursiveafficherDecroissantRecursifABR(A)qui ache les valeurs de l'arbre binaire de rechercheAen ordre decroissant.Solution:
defafficherDecroissantRecursifABR (A): ifA!=None: afficherDecroissantRecursifABR (A. fd ): print(A. info )afficherDecroissantRecursifABR (A. fg ):(i)(2 p oints)Soit Aun ABR contenant au moins deux nudsP1etP2, et les deux sequences de calculs :