Master BioInformatique Année : 2011/2012 Session de décembre 2011 PARCOURS : Ma

Master BioInformatique Année : 2011/2012 Session de décembre 2011 PARCOURS : Master 1 UE : Algorithmes et structures de données Épreuve : Examen Date : Vendredi 16 décembre 2011 Heure : 10 heures Durée : 2 heures Documents : autorisés Épreuve de M. Alain Griffault SUJET + CORRIGE Avertissement  La plupart des questions sont indépendantes, et le barème total est de 22 points.  L'espace laissé pour les réponses est su sant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement déconseillé). Exercice 1 (Files à l'aide de Piles (8 points)) Nous avons vu en cours une implémentation d'un pile par un tableau borné. CreerPileVide (N){ P.T : o b j e t [N] ; // T e s t un t a b l e a u de N " o b j e t s " P. sommet <−−1; // sommet e s t l ' i n d i c e du dernier o b j e t depose . retourner P; } PileVide (P){ retourner (P. sommet < 0 ) ; } P i l e P l e i n e (P){ retourner (P. sommet = P.T. longueur −1); } SommetPile (P){ s i ( non PileVide (P)) a l o r s retourner P.T[P. sommet ] ; sinon Ecrire " Impossible , l a p i l e e s t vide "; } Empiler (P,X){ s i ( non P i l e P l e i n e (P)) a l o r s { P. sommet <−P. sommet + 1; P.T[P. sommet ] <−X; } sinon Ecrire " Impossible , l a p i l e e s t p l e i n e "; } Depiler (P){ s i ( non PileVide (P)) a l o r s P. sommet <−P. sommet −1; sinon Ecrire " Impossible , l a p i l e e s t vide "; } 1 Algorithmes et structures de données Session 1, Année 2011/2012 Nous avons également vu en cours une implémentation d'une le par un tableau circulaire. Dans cet exercice, nous allons implémenter une le de taille N à l'aide de deux piles de taille N. L'idée est la suivante : Le sommet de la première pile correspond à l'avant de la le, tandis que le sommet de la seconde pile correspond à l'arrière de la le. Lorsque la première pile est vide, la seconde peut être retournée sur la première. Ce retournement est utilisé pour retirer l'élément en tête de le lorsque la pile correspondant à l'avant est vide. Ainsi la création d'une le s'écrit : CreerFile (N){ F. Tete <−CreerPile (N) ; // l e sommet de F. Tete e s t l a t e t e de l a f i l e F F. Queue <−CreerPile (N) ; // l e sommet de F. Queue e s t l a queue de l a f i l e F retourner F; } Les tests de le vide et de le pleine s'écrivent : FileVide (F){ // La f i l e e s t vide s i l e s deux p i l e s sont v i d e s . retourner PileVide (F. t e t e ) && PileVide (F. Queue ) ; } F i l e P l e i n e (F){ // l a f i l e e s t p l e i n e s i l a p i l e de queue e s t p l e i n e ( c ' e s t un choix ) retourner P i l e P l e i n e (F. Queue ) ; } La tete de le est obtenue par : TeteFile (F){ s i ( non FileVide (F)) a l o r s { s i ( non PileVide (F. Tete )) a l o r s retourner SommetPile (F. Tete ) ; sinon retourner F. Queue .T [ 0 ] ; } sinon Ecrire " Impossible , l a f i l e e s t vide "; } Question 1.1 (2 points) Complétez le code de la primitive Enfiler(F). Réponse : E n f i l e r (F,X){ // s i l a f i l e n ' e s t pas pleine , l e s o b j e t s sont deposes dans l a p i l e de queue . s i ( non F i l e P l e i n e (F)) a l o r s Empiler (F. Queue ,X) ; sinon Ecrire " Impossible , l a f i l e e s t vide "; } Question 1.2 (3 points) Complétez le code de la primitive Defiler(F). Réponse : D e f i l e r (F){ // I l e s t p o s s i b l e de d e f i l e r s i l a f i l e n ' e s t pas vide . // Si l a p i l e de t e t e e s t vide , // −i l f a u t " retourner " l a f i l e de queue dans l a f i l e de t e t e // ainsi , l a p i l e de t e t e n ' e s t pas vide et i l e s t p o s s i b l e de " d e f i l e r " s i ( non FileVide (F)) a l o r s { 2 Algorithmes et structures de données Session 1, Année 2011/2012 s i ( PileVide (F. Tete )) a l o r s { // I l f a u t " retourner " l a p i l e de queue dans l a p i l e de t e t e . tant que ( non PileVide (F. Queue )) f a i r e { Empiler (F. Tete , SommetPile (F. Queue ) ) ; Depiler (F. Queue ) ; } } Depiler (F. Tete ) ; } sinon Ecrire " Impossible , l a f i l e e s t vide "; } Question 1.3 (1 points) Donnez une suite d'appels contenant des Enfiler(F,X) et des Defiler(F) possible avec une implémentation d'une le de taille 3 à l'aide de deux piles de taille 3, et qui n'est pas possible avec l'implémentation vue en cours. Réponse : Avec les deux piles de taille 3, il est possible d'avoir plus de 3 objets simultanément dans la le. La séquence suivante est impossible avec une le de taille 3 implémentée avec un tableau circulaire. Enfiler(F,X);Enfiler(F,Y);Enfiler(F,Z);Defiler(F);Enfiler(F,T);Enfiler(F,U); Question 1.4 (2 points) Donnez une nouvelle version de la primitive FilePleine pour corriger le problème de la question précédente. Réponse : F i l e P l e i n e T a i l l e N (F){ // l a f i l e e s t p l e i n e s i l e nombre d ' o b j e t s dans l e s deux p i l e s e s t de N retourner ((F. Tete . sommet + 1) + (F. Queue . sommet + 1) = F. Tete . longueur ) ; } Exercice 2 (Tri par base (8 points)) Nous avons vu en cours de nombreux algorithmes pour trier des objets contenus dans un tableau. Dans cet exercice, nous allons implémenter un nouvel algorithme de tri. Cet algorithme a été inventé il y a bien longtemps pour trier les cartes perforées. Nous allons l'écrire pour trier des personnes suivant leur date de naissance. Pour cela nous allons supposer que les personnes sont stockées sous forme de tableaux. // Une personne e s t representee par sa date de naissance . // Personne [ 0 ] e s t l e jour de naissance . // Personne [ 1 ] e s t l e mois de naissance . // Personne [ 2 ] e s t l ' annee de naissance . Personne : Entier [ 3 ] ; Question 2.1 (2 points) Écrivez une fonction NeAvant(P1,P2) de comparaison de deux personnes P1 et P2 qui retourne Faux si P2 est né strictement après P1, et Vrai sinon. (Pensez aux prédicats !) Réponse : NeAvant (P1 , P2){ retourner ((P1 [ 2 ] < P2 [ 2 ] ) | | ((P1 [ 2 ] = P2 [ 2 ] ) && (P1 [ 1 ] < P2 [ 1 ] ) ) | | ((P1 [ 2 ] = P2 [ 2 ] ) && (P1 [ 1 ] = P2 [ 1 ] ) && (P1 [ 0 ] <= P2 [ 0 ] ) ) ) ; uploads/Ingenierie_Lourd/ corrige-pdf 1 .pdf

Tags
Ingénierie retourner sommet queue question réponse
Documents similaires
  • 36
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager