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 2 Master BioInformatique Année Session de décembre PARCOURS Master UE Algorithmes et structures de données Épreuve Examen Date Vendredi décembre Heure heures Durée heures Documents autorisés Épreuve de M Alain Gri ?ault SUJET CORRIGE Avertissement

Master BioInformatique Année Session de décembre PARCOURS Master UE Algorithmes et structures de données Épreuve Examen Date Vendredi décembre Heure heures Durée heures Documents autorisés Épreuve de M Alain Gri ?ault SUJET CORRIGE Avertissement La plupart des questions sont indépendantes Le barème total est de points car le sujet est assez long E indique une question plus di cile E L'espace laissé pour les réponses est su sant sauf si vous utilisez ces feuilles comme brouillon ce qui est fortement déconseillé Rappels C Dé nition Un arbre binaire est une structure dynamique A récursive qui soit ne contient aucun n? ud soit contient trois ensembles disjoints de n? uds un n? ud racine un arbre binaire dénommé sous arbre gauche C un arbre binaire dénommé sous arbre droit Dé nition Un arbre binaire A de hauteur h est presque parfait lorsque Toute les feuilles sont à distances h ou h ?? de la racine La feuille la plus à gauche est à distance h de la racine Si une feuille est à distance h ?? de la racine alors toutes les feuilles à sa droite sont à distance h ?? de la racine N En cours vous avez vu la correspondance entre les arbres binaires presque parfait de taille et les tableaux indicés de à N- munis des fonctions fg i i qui simule le pointeur fg fd i i qui simule le pointeur fd pere i i - pour i et pere qui simule le pointeur pere Dans la suite vous supposerez disposer des opérateurs C suivants sur les tableaux Etendre T qui ajoute une case à la n du tableau T et qui met à jour la valeur de T longueur en conséquence de complexité O Reduire T qui retire la dernière case du tableau T et qui met à jour la valeur de T longueur en conséquence de complexité O Vous supposerez également que chaque case d'un tableau contient un champ data pour stocker les données un champ cle pour ordonner les C données Dé nition Un tas T de taille N est un tableau de longueur N tel que ??i ?? N ?? T pere i cle ? T i cle La structure de tas est munie des primitives suivantes vues en cours EntasserRecursif T i M qui construit un tas de taille M dans un tableau de longueur T longueur ? M i à partir d'une structure qui est un tas sauf peut- être pour la case d'indice CAlgorithmes et structures de données Session Année ExtraireMax T qui supprime d'un tas l'élément ayant la plus grande clé InsererEchange T X qui ajoute au tas T une nouvelle case contenant X data X cle et positionnée en fonction de X cle dont voici les pseudo codes EntasserRecursif T i M M la taille du tas est un nombre inferieur ou egal a la longueur du tableau M - Minimum M T longueur pour eviter des debordements indiceMax - i si fg i M T fg i