U.S.T.O. M.B. / Faculté des Mathématiques et Informatique / Dept. Informatique 2ème A.

Licence
Semestre S3 EXAMEN ALGORITHMIQUES ET STRUCTURES DE DONNEES ASD3
Durée : 1h30 26 Janvier 2020

Exo1 : (2.5pts) Analyser la complexité de l’algorithme suivant. En déduire la valeur de la variable 𝒚

à la fin de cet algorithme en fonction de 𝑛.
𝒚 = 5;
for (i=1 ; i<=n ; i++)
for (j=i ; j<=n ; j++)
for (k=1 ; k<=n ; k++)
𝒚 += 3;

Exo2 : (5pts) On considère l’algorithme de tri suivant (étrange et inefficace, appelé stooge sort) pour
un tableau T entre les indices i et j.
Tri(T,i,j) {
Si (T[i] > T[j]) alors { a  T[i]; T[i]  T[j]; T[j]  a; }
Si (j > i+1) alors
{ k  (j - i + 1)/3;
Tri(T, i, j-k); // On trie les deux premiers tiers
Tri(T, i+k, j); // On trie les deux derniers tiers
Tri(T, i, j-k); // On trie encore les deux premiers tiers
}
} // deux tiers = ‫الثلثين‬
1. Dérouler l’algorithme sur le tableau T = [ 7 , 9 , 3 ] (L’appel se fait avec Tri(T,0,2)) en indiquant les
états intermédiaires de T.
2. Écrire l’équation de récurrence de sa complexité.
3. Evaluer sa complexité.

Exo3 : (5pts) Soit la liste d’entiers 𝒔 = 11, 15, 5, 2, 3, 9, 17, 21, 22, 13, 19, 4, 12.
1. Construire l’arbre binaire de recherche associé à la liste (en prenant les éléments dans l’ordre où ils sont
donnés). Que devient l’arbre après la suppression de 15 ?
2. En considérant que l’arbre est représenté de manière chaînée (Questions 2 et 3), donner la routine
C/C++ qui affiche la liste 𝑠 triée.
3. Ecrire la fonction C/C++ qui prend en entrée la racine de l’arbre et supprime le plus grand élément.

Exo4 : (7.5pts) Soit le graphe 𝐺 orienté valué (poids>0) représenté comme suit :
SuccPds (Succ = Successeur , Pds = Poids ou valeur de l’arc)
1  1 2  2 17  3 8  4 2 null
2 null
3  2 9  3 14  6 7 null
4  4 2  6 15 null
5 null
6  1 5  2 1 null

1. Donner le graphe inverse 𝐺 en utilisant la même représentation.

2. Considérons le graphe 𝐺 et le problème du plus court chemin du sommet 1 vers les autres sommets :
a. Appliquer l’algorithme de Dijkstra.
b. Après exécution de l’algorithme de Dijkstra, que signifie un sommet non fixé (non marqué) ?
c. Citer le principal inconvénient de l’algorithme de Dijkstra. Donner sa complexité, et dire s’il est
possible de réduire cette complexité. Justifier.
3. En considérant un graphe orienté représenté sous forme de listes chainées d’adjacence, écrire une
fonction C/C++ qui permet de tester si un sommet donné en paramètre est isolé.
Bon courage…
U.S.T.O. M.B. / Faculté des Mathématiques et Informatique / Dept. Informatique 2ème A. Licence
Semestre S3 EXAMEN ALGORITHMIQUES ET STRUCTURES DE DONNEES ASD3
Durée : 1h30 26 Janvier 2020

BAREME

Exo1 : (2.5pts) Analyser la complexité de l’algorithme suivant. En déduire la valeur de la variable 𝒚

à la fin de cet algorithme en fonction de 𝑛.
𝒚 = 5;
for (i=1 ; i<=n ; i++) ........................ O(n) 0.25pt
for (j=i ; j<=n ; j++) .................... n+(n-1)+…+1=n(n+1)/2 0.5pt
for (k=1 ; k<=n ; k++) ................. n²(n+1)/2 0.5pt
𝒚 += 3;

La complexité est donc O(n3) 0.5pt

La valeur de y à la fin est donc y = 5 + 3n²(n+1)/2 0.75pt

Exo2 : (5pts) On considère l’algorithme de tri suivant (étrange et inefficace, appelé stooge sort) pour
un tableau T entre les indices i et j.
Tri(T,i,j) {
Si T[i] > T[j] alors { a  T[i]; T[i]  T[j]; T[j]  a; }
Si j > i+1 alors
{ k  (j - i + 1)/3;
Tri(T, i, j-k); // On trie les deux premiers tiers
Tri(T, i+k, j); // On trie les deux derniers tiers
Tri(T, i, j-k); // On trie encore les deux premiers tiers
}
}
1. Dérouler l’algorithme sur le tableau T = [ 7 , 9 , 3 ] (L’appel se fait avec Tri(T,0,2)) en indiquant les
états intermédiaires de T. 1.5pts (0.75 + 0.75)

[7,9,3][3,9,7][3,7,9]

2. Écrire l’équation de récurrence de sa complexité. 1.5pts (0.5 1ère ligne, 1pt 2ème ligne)

𝑂(1) 𝑠𝑖 𝑛 ≤ 2 (𝑒𝑛𝑙𝑒𝑣𝑒𝑟 0.25 𝑠𝑖 𝑒𝑟𝑟𝑒𝑢𝑟 𝑠𝑢𝑟 𝑛 ≤ 2)

𝑐𝑜𝑛𝑠𝑖𝑑é𝑟𝑒𝑟 𝑐𝑜𝑚𝑚𝑒 𝑗𝑢𝑠𝑡𝑒 𝑠𝑖 𝑛 = 2
𝑇(𝑛) =
2𝑛
3𝑇 + 𝑂(1) 𝑠𝑖𝑛𝑜𝑛
3

3. Evaluer sa complexité. 2pts (1pt développement, 1pt résultat final ; accepter le résultat final même si la base du
logarithme et les constantes ont été laissées)
2𝑛 4𝑛 8𝑛 2 𝑛 2 𝑛 3 −1
𝑇(𝑛) = 3𝑇 + 1 = 9𝑇 + 4 = 27𝑇 + 13 = ⋯ = 3 𝑇 + 3 =3 𝑇 +
3 3 27 3 3 2

𝑇(2) = 𝑂(1)  = 2  𝑝 = 𝑙𝑜𝑔 (𝑛/2) accepter aussi 𝑝 = 𝑙𝑜𝑔

On obtient une complexité de l’ordre de : (la base du logarithme peut être omise)
( ) ( / )
𝑂 3 𝑜𝑢 𝑂 3
U.S.T.O. M.B. / Faculté des Mathématiques et Informatique / Dept. Informatique 2ème A. Licence
Semestre S3 EXAMEN ALGORITHMIQUES ET STRUCTURES DE DONNEES ASD3
Durée : 1h30 26 Janvier 2020

Exo3 : (5pts) Soit la liste d’entiers 𝑠 = 11, 15, 5, 2, 3, 9, 17, 21, 22, 13, 19, 4, 12.
1. Construire l’arbre binaire de recherche associé à la liste (en prenant les éléments dans l’ordre où ils sont
donnés). Que devient l’arbre après la suppression de 15 ? 1pt (0.5+0.5)

11

5 15

2 9 13 17

3 12 21

4 19 22

Après suppression de 15 (une solution parmi les 2 solutions possibles) :

11 11

5 13 5 17
5

2 9 12 17 2 9 13 21

3 21 3 12 19 22

4 19 22 4

2. En considérant que l’arbre est représenté de manière chaînée (Questions 2 et 3), donner la routine
C/C++ qui affiche la liste 𝑠 triée. 1pt
void parcoursInfixe(Noeud *racine)
{ if (racine!=NULL) {
parcoursInfixe(racine->filsGauche);
cout<<racine->element<<endl;
parcoursInfixe(racine->filsDroit); }
}
U.S.T.O. M.B. / Faculté des Mathématiques et Informatique / Dept. Informatique 2ème A. Licence
Semestre S3 EXAMEN ALGORITHMIQUES ET STRUCTURES DE DONNEES ASD3
Durée : 1h30 26 Janvier 2020

3. Ecrire la fonction C/C++ qui prend en entrée la racine de l’arbre et supprime le plus grand élément. 3pts

void suppMax(Noeud *&racine)

{
if (racine!=NULL) {
// Chercher l'élément maximal
Noeud *p=racine, *prec=NULL;
while (p->filsDroit!=NULL) { prec=p; p=p->filsDroit;}
if (prec==NULL) // ou p==racine, cas où l'élément maximal est la racine
racine=p->filsGauche; //ou racine=racine->filsGauche;
else
prec->filsDroit=NULL;
delete p;
}
}
Recherche du maximum : 1pt
Suppression logique cas particulier : 0.5pt
Suppression logique cas général : 0.5pt
Suppression physique : 0.5pt
Respect de la syntaxe : 0.5pt

Exo4 : (7.5pts) Soit le graphe orienté valué (poids>0) représenté comme suit :
1  1 2  2 17  3 8  4 2 null
2 null
3  2 9  3 14  6 7 null
4  4 2  6 15 null
5 null
6  1 5  2 1 null

1. Donner le graphe inverse en utilisant la même représentation. 0.75pt

1  1 2  6 5 null
2  1 17  3 9  6 1 null
3  1 8  3 14 null
4  1 2  4 2 null
5 null
6  3 7  4 15 null

2. Considérons le problème du plus court chemin du sommet 1 vers les autres sommets : (3.75=2.5+0.25+1)
a. Appliquer l’algorithme de Dijkstra. 2.5pts
1 2 3 4 5 6 Fix
0 ∞ ∞ ∞ ∞ ∞ 1 0.25
17 8 2 ∞ ∞ 4 0.25
17 8 ∞ 17 3 0.25
17 ∞ 15 6 0.25
16 ∞ 2 0.25
Arrêt car la valeur minimale est ∞ 0.25

Tableau P (Paths)
1 2 3 4 5 6
0 0/1/6 0/1 0/1 0 0/4/3 0.5
U.S.T.O. M.B. / Faculté des Mathématiques et Informatique / Dept. Informatique 2ème A. Licence
Semestre S3 EXAMEN ALGORITHMIQUES ET STRUCTURES DE DONNEES ASD3
Durée : 1h30 26 Janvier 2020

Résultat final
Tableau V (Valeur de plus court chemin)
1 2 3 4 5 6
0 16 8 2 ∞ 15

Tableau P (Paths)
1 2 3 4 5 6
0 6 1 1 0 3

Les plus courts chemins sont : 0.5pt

11:0
1  3  6  2 : 16
13:8
14:2
1  5 : pas de chemin (facultatif, objet de la question suivante)
1  3  6 : 15

Acceptez le déroulement « façon THG » ; les itérations sont écrites l’une après l’autre, le tableau V est appelé
éventuellement 𝜋. Validez l’itération en vérifiant le Vmin (𝜋 ), le sommet marqué qui est stocké dans un ensemble
appelé M et aussi les mise à jours des valeurs 𝜋 des successeurs non marqué du sommet fixé.

b. Après exécution de l’algorithme de Dijkstra, que signifie un sommet non fixé (non marqué) ? 0.25pt
Il n’existe pas de chemin entre le sommet de départ et le sommet non fixé.

c. Citer le principal inconvénient de l’algorithme de Dijkstra. Donner sa complexité, et dire s’il est
possible de réduire cette complexité. Justifier. 1pt (0.25+0.25+0.5)

- Inconvénient : Ne fonctionne pas en cas de poids négatifs.

- Complexité : O(N²) N étant le nombre de sommets.
- Oui en organisant le tableau V sous forme d’un min-tas et en utilisant les listes d’adjacence comme
structure de données pour le graphe. La complexité devient O(NlogN).
(Le plus important c’est de citer le terme TAS 0.25 et la nouvelle complexité O(NlogN) 0.25)

3. En considérant le graphe représenté sous forme de listes chainées d’adjacence, écrire une fonction
C/C++ qui permet de tester si un sommet donné en paramètre est isolé. 3pts

// Au cas où l’étudiant utilise la représentation chainée vue dans le dernier exercice de la fiche TD, acceptez et
appliquez le même barème.

Rappel Déclaration (Facultatif):

const int maxNoeuds=999;

struct Bloc { int sommet; int poids; Bloc *suiv ;};

struct Graphe { Bloc *Tete[maxNoeuds]; int N,M; };

U.S.T.O. M.B. / Faculté des Mathématiques et Informatique / Dept. Informatique 2ème A. Licence
Semestre S3 EXAMEN ALGORITHMIQUES ET STRUCTURES DE DONNEES ASD3
Durée : 1h30 26 Janvier 2020

bool estIsole(Graphe G, int s)

{ if (G.Tete[s]!=NULL) return false; 0.75 //s possède des successeurs

for (int i=1;i<=G.N;i++) 0.5

{ Bloc *p=G.Tete[i]; 0.25
while (p!=NULL) { 0.25
if (p->succ==s) return false; 0.75 //s possède des prédecesseurs
p=p->suiv; 0.25
}
}
return true; 0.25 // s est isolé
}