Théorie de la programmation - TDA et structures de données 2008 Génie Informatique Université de Technologie de Belfort Montbéliard

Renaud

Description

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Théorie de la programmation - TDA et structures de données 2008. Retrouvez le corrigé Théorie de la programmation - TDA et structures de données 2008 sur Bankexam.fr.

Sujets

• 2008

Informations

• Publié par: bankexam
• Publié le: 17 mars 2009
• Nombre de lectures: 24
• Langue: Français

Extrait

UTBM

le 24 juin 2008

Final – LO42

solution

(durée 1h30)

Les documents ne sont pas autorisés (La copie ou les idées du voisin non plus ). Le barème est indicatif.

Le soin donné à la rédaction sera évalué. Toute réponse devra être claire et justifiée (toute ambiguïté sera

mal interprétée). L’élégance de la solution sera jugée.

Sauf indication contraire, dans le cas d’algorithmes les réponses doivent être rédigées en pseudo code.

1) En pleine largeur, mais pas trop, étalons nous

.

(5p)

Le parcours ou descente en largeur dans un graphe consiste à avancer par « niveau », c’est à dire visite de tous les

sommets distants de i arcs avant de visiter ceux distants de i+1 arcs.

Nous pouvons décrire le parcours de la façon suivante :

S

←

{ x } ;

/* S correspond à l’ensemble des sommets rencontrés à visiter */

Y

← φ

;

/* Y est l’ensemble des sommets visités */

Tantque S

≠ φ

Faire

/* tant qu’il y a des sommets à visiter */

Marquer tous les sommets de S

Y

←

Y

∪

S ;

S

← Γ

(S) \ Y ;

Ftq

Dans le graphe ci-dessus donner le parcours en largeur depuis le sommet 5.

Soit un graphe

G

d'ordre

n

, écrivez un algorithme qui réalise une descente en largeur, à partir du sommet

s

, dans le

graphe

G

implanté par file de successeurs (FS/APS).

•

On pourra, utiliser une file d'attente gérée comme suit :

-

un sommet s entre dans la file au moment où il est marqué

-

un sommet s sort de la file au moment où tous ses successeurs sont marqués.

•

Pour marquer les sommets, on utilisera un tableau de booléen MARQUE initialisé à faux.

2) De l’arbre, petite, l’image donnée doit être

(8p)

Pour représenter un arbre d’Huffman nous utilisons la méthode définie par Lukasiewizc. Dans cette représentation

une feuille est représentée par un 1. En présence d'un nœud, la représentation de l'arbre est 0 suivi de la

représentation du fils gauche et de celle du fils droit.

L(A)

= 1 si A est une feuille

= 0 L(fg(A)) L(fd(A)).

Ainsi l'arbre (a, ( (b, r), (c, d) ))) est représenté :

010011011|1|"a"|"b"|"r"|"c"|"d"

Le 1 avant les caractères est un marqueur de fin de codage

de l'arbre

a) Expliquez pourquoi cette représentation est suffisante pour restituer l'arbre.

b) Écrivez la fonction

estFeuille(AB A)

qui restitue un booléen vrai si l'arbre transmis est une feuille, faux sinon.

lo42 - final P2008 - page1/3

7

6

3

2

1

5

9

8

4

10

a

b

r

c

d

UTBM

le 24 juin 2008

c) Écrivez la fonction

coderArbre(AB A)

qui retourne une file de caractères contenant la représentation de l'arbre.

La procédure recevra en paramètre un arbre binaire de Huffman et donnera la suite de caractères comme dans

l’exemple ci-dessus. (on ne travaille pas sur les bits comme cela doit être fait.). Vous définirez et utiliserez

deux fonctions récursives

coderStructure(AB A, File f)

et

listeFeuilles(AB A, File f)

qui permettent

respectivement d'obtenir dans la file

f

la suite de caractères représentant la structure de l'arbre

A

et d'ajouter

dans la file

f

les caractères contenus par les feuilles de

A

.

d) Écrivez une fonction

decoderArbre(Chaine Ch)

qui reçoit une chaîne de caractères et retourne un arbre binaire

de Huffman.

On supposera que l’arbre à traiter est bien un arbre de Huffman, et que la chaîne de caractères est une

représentation correcte d’un arbre de Huffman.

On utilisera les opérations sur File et Arbre, suivantes :

File

File fileVide

File creerFile()

File defiler(f)

File enfiler(f, v)

Elt premier(f)

Arbre

AB arbreVide

AB creerArbre()

Elt valeur(AB)

AB setValeur(AB, v)

AB filsGauche(AB)

AB filsDroit(AB)

AB setFilsGauche(AB, AB)

AB setFilsDroit(AB, AB)

enfiler et defiler retournent la référence à la File f

3) Tranchons, mais de la famille, le respect, ayons !

(7p)

Étant donné un arbre binaire de recherche contenant des éléments gérés par clef, on cherche à supprimer de l’arbre

tous les éléments de clefs strictement inférieures à une valeur donnée.

a) Donnez l'arbre résultant de l'élagage des valeurs inférieures à 21.

b) Écrivez la fonction

elaguerInferieur(ABR A, int k)

telle que

elaguerInferieur(A, k)

supprime de l’arbre

A

, tous

les éléments de clef strictement inférieure à

k

. La fonction retourne l'arbre résultant.

Vous devez limiter au maximum les comparaisons dans votre fonction ou les fonctions éventuellement appelées.

(

indication : 0 ou 1 comparaison maximum par valeur

)

c) La représentation de l'arbre intègre un lien père, modifiez votre fonction pour intégrer la gestion de ce lien.

d) Écrivez la fonction

rotDroite(ABR A)

qui retourne l'arbre résultat de la rotation à droite de l'arbre

A

intégrant la

liaison père.

lo42 - final P2008 - page2/3

25

11

35

13

29

27

37

28

20

17

24

22

33

30