Faculté des Sc.
iences Exactes Année Universitair e 202| -2022
Département d' informatique Filière :LMD SC 53
Durée: 0lh30mn
EMD Algorithmique et structure de données 3
Exercice 1:
Calculez la complexité des algorithmes suivants, sachant que toutes les Actions ont une
complexité constante.
a. j<-n; c. i+-1 ;
RéPéter Tant que i<n 1àire
Actions; i<_is4 ;
j<-1121 6crion ;
jusqu'à j<l ;
d. i<_n;
b. Pour i<-1 à n làire Répéter
a€-m; i<_i_5 ;
Pourj<-l ànfàire Action:
a<-alZ:, jusclu,à i<0 ;
Exercice 2 :
1. Citez les noms des six algorithmes de tri les plus répondus (étudiés dans le cours), et donnez leurs
complexités (au pil'e des cas). Classer ces algorithmes du plus mauvais au meilleur.
2. Etant donnée 1'arbre A dont Ia structure de donnée est la sr:ivante :
I 2 3 4 s 6 1 8 9 l0 ll 12 t3 14 15 t6
PF 2 1 5 0 0 0 0 10 0 0 t2 l6 0 0 0 0
a
FR 0 8 0 J 6 0 4 9 11 0 0 13 0 0 14 15
Valeur â b c d e f (I h I i k I m n o p
Racine:1
Nbr:16
a. Faire la r:eprésentation graphique de l'arbre A.
b. Selon le type de I'arbre A, citez les noms des stratégies de parcours que nous pouvons utiliser pour
parcourir les éléments de A.
3. Représentez les matrices d'incidencc suir,'antes par le graphe conespondant :
111 tJz U3 u4 U5 U6 u1 Lt2 tl3 u4 U5 U6 U7
at 1 1 0 0 0 0 a1 1 1 1 0 0 0 0
w -1 0 0 0 -1 0 u 0 0 1 0 1 0 1
A3 0 -1 1 -1 0 0 43 0 0 0 1 0 1 1
u 0 0 -1 0 0 1 u 1 0 0 1 0 0 0
âs 0 0 0 1 1 -1 a5 0 1 0 0 1 1 0
Exercice 3 et Examen de TD :
Sachant que la profondeur d'un sommet s dans un arbre binaire est la longueur du chemin
(nombre d'arc) entre ce sommet et la racine, elle se calcule récursivement à partir de la
profondeur du sommet parent de s. Ecrire alors la fonction qui calcule la profondeur d'un
sommet s dans un arbre binaire B.
5ê uL (l-,ea-Lo:_! 5b §.f i,
w
ry. (oÉ1*..Q (â)
,lf €xo,*,.q,--r4:U 5 [â\-,^Jtr\\^"q_
a,. tg((^) = A+ r(
= l+ .f(Là
:n*n'^o((tJ
{..*o((;l
(
=
a,L /o^,^^-r^- Ço.,...-
?t"= L =) lr-= !o7 " ,Y o g(a) -+
.) of(^) = UâJ -i = )(6aJ\ @
b . g((") =
H^iT"") ,.ç û.*) = ^ (.t*,) :rD(^) @
'4*
» a-.*.-(*i*14":
T+y d* a',&**- A;
o/I> "\, b'ùll^'@
/\ t/'l'1'
ü /\ à r-
/ \^
e-+?e-r4 ./\\
u. ,ü^ »Fo--t^*rtri* /t (*æ^'^ÀA S- e'*L*- A
'
u W%u,u\," ,f r^,1"-[fu-*
@"w
Kq{"^ek-ke; "b^ ylh^ &^ ,"^-.u(a,ice"" )(lur-J,u-üz
..
o- 4"d.;
9
{t .n5
qL, q-L
J^"1
4"5
q
5
Lç-
')
rLç "Oq
@
"^"o,Siu, J"*JG
We, ('"tç**h)
Ài 4 = viÂ- o-&.",1 «n^rt*r"" O
,À i \^t .- ,li crh <a-c.**- (,f , U) ,.-0uU fuE*-,r,r^r- O
Àî nÂ^, fufo^^,^*r^- 4 , l^"d &._rla,.,r_ (*a, (, ,b) , A)
-i
à;;
- Â-