No Title

DEUG $2^{\grave{e}me}$ Année - Tronc A - MIAS 2 et MASS 2
Examen d'informatique - Session de Juin
Durée : 2 heures - Sans documents.
Exercice 1 : Arbres Binaires

Répondre uniquement dans les cadres prévus à cet effet

$\fbox{\begin{minipage}{173mm}\large Nom :\hspace*{9cm}No dossier :\\ [1mm] Pr\'enom(s) :\hspace*{8cm}Signature :\\ [1mm] Date de naissance : \end{minipage}}$

Le but de ces questions est d'implanter les primitives d'un type de données abstrait d'arbres binaires représenté comme suit :

$\begin{figure} \centerline{\epsfig{scale=0.8, figure=figures/arbre.eps}} \end{figure}$

$\fbox{\begin{minipage}{173mm} {\texttt{function arbre\_vide : arbre;}\large ~ \\ [3cm]} \end{minipage}}$

1.b Ecrire la fonction cons_arbre qui, à partir d'un entier e et de deux arbres g et d, renvoie un arbre binaire dont le champ info est e et ayant pour fils gauche g et pour fils droit d.

$\fbox{\begin{minipage}{173mm} {\texttt{function cons\_arbre(e : integer; g, d : arbre) : arbre;}\large ~ \\ [3cm]} \end{minipage}}$

1.c Ecrire la fonction est_vide qui renvoie true si l'arbre passé en paramètre est vide, false sinon.

$\fbox{\begin{minipage}{173mm} {\texttt{function est\_vide(a : arbre) : boolean;}\large ~ \\ [3cm] } \end{minipage}}$

1.d Ecrire la fonction valeur qui renvoie la valeur contenue dans le champ info de la racine de l'arbre non vide passé en paramètre. Pour l'arbre donné en exemple, la fonction valeur renverrait 1.

$\fbox{\begin{minipage}{173mm} {\texttt{function valeur(a : arbre) : integer;}\large ~ \\ [2cm] } \end{minipage}}$

1.e Ecrire la fonction fils_gauche qui renvoie le fils gauche d'un arbre non vide passé en paramètre.

$\fbox{\begin{minipage}{173mm} {\texttt{function fils\_gauche(a : arbre) : arbre;}\large ~ \\ [2.25cm] } \end{minipage}}$

Ecrire la fonction fils_droit qui renvoie le fils droit d'un arbre non vide passé en paramètre.

$\fbox{\begin{minipage}{173mm} {\texttt{function fils\_droit(a : arbre) : arbre;}\large ~ \\ [2.25cm] } \end{minipage}}$

1.f En utilisant exclusivement les fonctions arbre_vide et cons_arbre, déterminer l'expression construisant l'arbre ci-dessous.

$\begin{figure} \centerline{\epsfig{scale=0.9, figure=figures/sousarbre.eps}} \end{figure}$

$\fbox{\begin{minipage}{173mm} {\texttt{var a : arbre;\\ a :=}\large ~ \\ [2cm] } \end{minipage}}$

1.g Ecrire la fonction nb_noeuds qui retourne le nombre de n $\oe$ uds de l'arbre passé en paramètre (un arbre vide est constitué de 0 n $\oe$ ud ; dans l'exemple donné en première page, la fonction nb_noeuds renvoie 10).

$\fbox{\begin{minipage}{173mm} {\texttt{function nb\_noeuds(a : arbre) : integer;}\large ~ \\ [3cm] } \end{minipage}}$

1.h Ecrire la fonction arbre_similaire qui renvoie true si les deux arbres passés en paramètre sont similaires (tous les deux vides ou bien avec le même champ info pour les racines et des sous arbres similaires) et false sinon.

$\fbox{\begin{minipage}{173mm} {\texttt{function arbre\_similaire(a, b : arbre) : boolean;}\large ~ \\ [3cm] } \end{minipage}}$

À propos de ce document...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)