Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrige Master BioInformatique Anne ?e Semestre de de ?cembre PARCOURS Master UE J BS Algorithmique et Programmation E ?preuve Examen Date Lundi d ?ecembre Heure heures Dur ?ee heures Documents autoris ?es E ?preuve de M Alain Gri ?ault SUJET CORRIGE Aver

Master BioInformatique Anne ?e Semestre de de ?cembre PARCOURS Master UE J BS Algorithmique et Programmation E ?preuve Examen Date Lundi d ?ecembre Heure heures Dur ?ee heures Documents autoris ?es E ?preuve de M Alain Gri ?ault SUJET CORRIGE Avertissement ?? La plupart des questions sont ind ?ependantes ?? Vous pouvez au choix utiliser un langage algorithmique ou bien le langage python pour r ?epondre aux questions ?? L ? espace laiss ?e pour les r ?eponses est suf ?sant sauf si vous utilisez ces feuilles comme brouillon ce qui est fortement d ?econseill ?e Question Points Score ABR algorithmes et complexit ?es Total Exercice ABR algorithmes et complexit ?es points Rappels Les Arbres Binaires de Recherche ABR sont des arbres binaires qui satisfont la propri ?et ?e suivante ??N un n ?ud de l ? arbre ??G un n ?ud du sous arbre gauche de N ??D un n ?ud du sous arbre droit de N G inf o ? N inf o ? D inf o ouinf o est une valeur entiere servant a comparer les n ?uds Voici pour m ?emoire une version python de deux algorithmes vus en cours sur les ABR def minimumABR A i f A None return None else Aux A while Aux f g None Aux Aux f g return Aux def successeurABR A P P d o i t e t r e un noeud non n i l de A i f P fd None return minimumABR P f d else Aux P AuxPere P pere while AuxPere None and AuxPere f d Aux Aux AuxPere AuxPere Aux p e r e return AuxPere a points En vous inspirant de la fonction minimumABR A vue en cours ?ecrire une fonction it ?erative maximumABR A qui retourne un pointeur sur le n ?ud de l ? arbre A poss ?edant la plus grande valeur enti ere s ? il existe la valeur nil sinon Solution def maximumABR A i f A None return None else Aux A while Aux f d None Aux Aux f d return Aux b points Donner et justi ?er les complexit ?es pire des cas et meilleur des cas de votre fonction maximumABR A en fonction du nombre de n ?uds n ou de la hauteur h de l ? arbre A CUE J BS Algorithmique et Programmation Examen Ann ?ee Solution ?? Meilleur des cas lorsque A n ? a pas de ?ls droit ?? Pire des cas O lorsque A n ? a qu ? une descendance par ses ?ls droits La hauteur h de l ? arbre est alors ?egale a n c points En vous inspirant de la fonction successeurABR A P vue en cours ?ecrire une fonction predecesseur A P qui retourne un pointeur sur le n ?ud poss ?edant la valeur qui pr ?ecede la valeur contenue dans P Solution def predecesseurABR A P P d o i t e t r e un noeud non n i l