U.S.T.O.M.B./Dept. Informatique/2ème Année Ing. Nom Prénom : …………………..…………….……………..

………………………
Durée : 01h30’ EXAMEN ALGORITHMIQUES ET COMPLEXITE Lundi 13 Janvier 2025

I) QCM (7pts) COCHER LA OU LES REPONSES JUSTES / CHECK THE CORRECT ANSWER(S)
1. La recherche d’un élément a une complexité pire cas 𝑂(𝑁) dans le cas
The search for an element has a worst-case complexity of 𝑶(𝑵) in the case

 Recherche séquentielle dans une liste quelconque / Sequential search in an unordered list
 Recherche dichotomique dans une liste triée / Binary search in a sorted list
 Arbre binaire de recherche dégénéré / Degenerate binary search tree
 Arbre binaire de recherche équilibré AVL / Balanced binary search tree AVL

2. La recherche de l’élément minimal a une complexité pire cas 𝑂(𝑙𝑜𝑔𝑁) dans le cas
Finding the minimum element has a worst-case complexity of 𝑶(𝒍𝒐𝒈𝑵) in the case

 Liste quelconque / Unordered list

 Liste triée / Sorted list
 Arbre binaire de recherche dégénéré / Degenerate binary search tree
 Arbre binaire de recherche équilibré AVL / Balanced binary search tree AVL
 Min-Tas / Min-heap
 Max-Tas / Max-heap

3. Le nombre de permutations est dans le pire des cas de l’ordre de 𝑂(𝑁²) dans le cas
The number of swaps is in the worst case of the order 𝑶(𝑵²) in the case

 Tri par sélection / Selection sort

 Tri par insertion / Insertion sort
 Tri à bulles / Bubble sort
 Tri par fusion / Merge sort
 Tri rapide / Quick sort

4. Etant donné les séquences suivantes de parcours d’un arbre binaire

Given the following traversal sequences of a binary tree
(infixe / inorder 9 13 5 11 14 41 21 53 25 6, postfixe / postorder 13 11 5 9 21 25 53 41 6 14)

 La séquence préfixe correspondante est / The correspondent preorder sequence is

14 9 13 5 11 6 41 21 53 25
 La séquence préfixe correspondante est / The correspondent preorder sequence is
14 9 5 13 11 6 41 53 21 25
 La séquence par niveaux correspondante est / The level-order traversal is
14 9 6 13 5 41 11 21 53 25
 L’arbre est indéfini (On ne peut pas le déduire) / The tree is undefined (It cannot be deduced)

1/3
U.S.T.O.M.B./Dept. Informatique/2ème Année Ing. Nom Prénom : …………………..…………….……………..………………………
Durée : 01h30’ EXAMEN ALGORITHMIQUES ET COMPLEXITE Lundi 13 Janvier 2025

5. Un arbre binaire de recherche de taille N / A binary search tree of size N

 Ne peut jamais être dégénéré / It can never be degenerated

 Le parcours préfixe donne une liste triée / The preorder traversal gives a sorted list
 Le parcours infixe donne une liste triée / The inorder traversal gives a sorted list
 La complexité pire cas de la recherche d’un élément est 𝑂(𝑙𝑜𝑔𝑁) / The worst-case time
complexity of searching for an element is 𝑶(𝒍𝒐𝒈𝑵)

6. Dans un tas de taille N / In a heap of size N

 L’opération d’insertion d’un élément a une complexité pire cas de l’ordre de 𝑂(𝑙𝑜𝑔𝑁)
The insertion operation for an element has a worst-case complexity of 𝑶(𝒍𝒐𝒈𝑵)

 L’opération de suppression d’un élément a une complexité pire cas de l’ordre de 𝑂(𝑁)
The deletion operation for an element has a worst-case complexity of 𝑶(𝑵)

 Les feuilles se trouvent au niveau de la première moitié du tableau

The leaves are located in the first half of the array

 Le tableau représentant un tas est toujours trié

The array representing a heap is always sorted

7. Dans un graphe orienté avec 𝑁 sommets et 𝑀 arcs ayant une densité de 0.9 (90%)
In a directed graph with 𝑵 vertices and 𝑴 edges having a density of 0.9 (90%)

 La représentation en matrice occupe moins d’espace que les listes d’adjacence

The matrix representation takes up less space than adjacency lists

 La représentation en listes d’adjacence occupe moins d’espace que la matrice

The adjacency lists representation takes up less space than matrix representation

 La recherche des successeurs d’un sommet donné se fait en 𝑂(𝑁²) dans le cas d’une
représentation en matrice
The search for the successors of a given vertex is done in 𝑶(𝑵²) in the case of a matrix
representation

 La recherche des successeurs d’un sommet donné se fait en 𝑂(𝑁 + 𝑀) dans le cas d’une
représentation en listes d’adjacence
The search for the successors of a given vertex is done in 𝑶(𝑵 + 𝑴) in the case of a
adjacency lists representation

2/3
U.S.T.O.M.B./Dept. Informatique 2ème Année Ingénieur d’état en informatique
Durée : 01h30’ EXAMEN ALGORITHMIQUES ET COMPLEXITE Lundi 13 Janvier 2025

II) EXERCICES : (13pts)

1. (3,5pts) Donner la structure de données résultante de l’insertion des sept clés 1,3,2,5,6,8,4 dans
cet ordre dans le cas d’un :
Give the resulting data structure from the insertion of the seven keys 1,3,2,5,6,8,4 in this order in the
case of a:
a. arbre binaire de recherche (BST) (indiquer le facteur d’équilibrage des nœuds du BST obtenu)
binary search tree (BST) (indicate the balance factor of the nodes in the resulting BST)
b. arbre binaire de recherche équilibré (AVL) (indiquer les opérations de rotation utilisées)
balanced binary search tree (AVL) (indicate the rotation operations used)
c. min-tas / min-heap
d. max-tas / max-heap

2. (1,5pts) Soit le graphe orienté représenté ci-après. Donner sa matrice d’adjacence puis le
déroulement de l’algorithme de parcours en profondeur (DFS) à partir du sommet 1.
Let the directed graph represented below. Provide its adjacency matrix and then detail the execution
of the Depth-First Search (DFS) algorithm starting from vertex 1.
1 2 3 4 5
Tete 1 2 2 6 6
1 2 3 4 5
Succ 3 3 2 1 4

3. (4pts) Soit une matrice carrée d’ordre N triée par ordre croissant (voir ci-dessous). Quelle est la
meilleure complexité temporelle possible de recherche d’un élément x dans une telle matrice (Evaluer
la complexité dans le pire des cas). Donner l’algorithme correspondant.
Let a square matrix of order N sorted in ascending order (as shown below). What is the best possible
time complexity for searching an element x in such a matrix (evaluate the worst-case complexity)?
Provide the corresponding algorithm.
M 1 2 3 4 5
1 2 4 5 7 10
2 14 16 18 25 27
3 29 39 45 52 59
4 60 66 74 81 87
5 88 90 92 93 98

4. (4pts) Le carré d’un graphe orienté G de n sommets et m arcs est le graphe G² construit comme
suit : pour chaque paire d’arcs dans G de la forme (u,v), (v,w), on ajoute l’arc (u,w) si ce dernier
n’existait pas déjà. Dans le cas de représentation en listes d’adjacence chainées, écrire le code C/C++
qui permet de construire G².
The square of a directed graph G with n vertices and m edges is the graph G² constructed as follows:
for each pair of edges in G of the form (u,v), (v,w), add the edge (u,w) if it does not already exist. In
the case of representation using linked adjacency lists, write the C/C++ code to construct G².

Utilisez la déclaration suivante / Use the following declaration:

const int MX = 50;

struct Bloc { int val; Bloc* suiv; };

struct Graphe { Bloc *Tete[MX]; int n,m; };

3/3
 Solution & Barème
I) QCM : (7pts) (1pt par réponse, Notation : Conformité stricte)
1. La recherche d’un élément a une complexité pire cas 𝑶(𝑵) dans le cas :
 Recherche séquentielle dans une liste quelconque
 Recherche dichotomique dans une liste triée
 Arbre binaire de recherche dégénéré
 Arbre binaire de recherche équilibré AVL
2. La recherche de l’élément minimal a une complexité pire cas 𝑶(𝒍𝒐𝒈𝑵) dans le cas :
 Liste quelconque
 Liste triée
 Arbre binaire de recherche dégénéré
 Arbre binaire de recherche équilibré AVL
 Min-Tas
 Max-Tas
3. Le nombre de permutations est dans le pire des cas de l’ordre de 𝑶(𝑵²) dans le cas :
 Tri par sélection
 Tri par insertion
 Tri à bulles
 Tri par fusion
 Tri rapide
4. Etant donné les séquences suivantes de parcours d’un arbre binaire :
(Séquence infixe 9 13 5 11 14 41 21 53 25 6, Séquence postfixe : 13 11 5 9 21 25 53 41 6 14)
 La séquence préfixe correspondante est : 14 9 13 5 11 6 41 21 53 25
 La séquence préfixe correspondante est : 14 9 5 13 11 6 41 53 21 25
 La séquence par niveaux correspondante est : 14 9 6 13 5 41 11 21 53 25
 L’arbre binaire est indéfini (On ne peut pas le déduire)
5. Un arbre binaire de recherche de taille N :
 Ne peut jamais être dégénéré
 Le parcours préfixe donne une liste triée
 Le parcours infixe donne une liste triée
 La complexité pire cas de la recherche d’un élément est 𝑂(𝑙𝑜𝑔𝑁)
6. Dans un tas de taille N :
 L’opération d’insertion d’un élément a une complexité pire cas de l’ordre de 𝑂(𝑙𝑜𝑔𝑁)
 L’opération de suppression d’un élément a une complexité pire cas de l’ordre de 𝑂(𝑁)
 Les feuilles se trouvent au niveau de la première moitié du tableau
 Le tableau représentant un tas est toujours trié
7. Dans un graphe orienté ayant N sommets et M arcs ayant une densité de 0.9 (90%) :
 La représentation en matrice occupe moins d’espace que les listes d’adjacence
 La représentation en listes d’adjacence occupe moins d’espace que la matrice
 La recherche des successeurs d’un sommet donné se fait en 𝑂(𝑁²) dans le cas d’une
représentation en matrice
 La recherche des successeurs d’un sommet donné se fait en 𝑂(𝑁 + 𝑀) dans le cas d’une
représentation en listes d’adjacence
1. (3,5pts) Donner la structure de données résultante de l’insertion des sept clés 1,3,2,5,6,8,4 dans
cet ordre dans le cas d’un :

1
a. BST (0,5pt : 0.25 BST + 0.25 facteur d’équilibrage)
3

2 5

4 6

b. AVL : (1.5pts : 1 AVL + 0.5 Rotations double DG + 2x simple G)

5

2 6

1 3 8

c. min-Heap : (0.5pt : min-Heap)

1 3 2 5 6 8 4

d. max-Heap : (1pt : max-Heap)

8 5 6 1 3 2 4

2. (1,5pts) Soit le graphe orienté représenté ci-après. Donner sa matrice d’adjacence puis le
déroulement de l’algorithme de parcours en profondeur (DFS) à partir du sommet 1.
Tete
1 2 3 4 5
1 2 2 6 6

Succ
1 2 3 4 5
3 3 2 1 4

Matrice d’adjacence : 0,75pt

1 2 3 4
1 0 0 1 0
2 0 0 0 0
3 1 1 1 1
4 0 0 0 0

Parcours en profondeur : 0,75pt

2 4
Pile 3 3 3 3 3 Pile Vide
1 1 1 1 1 1 1
Mark 1 3 2 4
3. (4pts) Soit une matrice carrée d’ordre N triée par ordre croissant (voir ci-dessous). Quelle est la
meilleure complexité temporelle possible de recherche d’un élément x dans une telle matrice (Evaluer
la complexité dans le pire des cas). Donner l’algorithme correspondant.
M 1 2 3 4 5
1 2 4 5 7 10
2 14 16 18 25 27
3 29 39 45 52 59
4 60 66 74 81 87
5 88 90 92 93 98
Three Ideas :
- Sequential search: O(N²) (0.25 Idea + 0.5 Complexity + 0.75 Algorithm) = 1.5pts
- Binary search in each row: O(NlogN) (0.75 Idea + 0.75 Complexity + 1 Algorithm) = 2.5pts
- One Row One Column: 2N = O(N) (1 Idea + 1 Complexity + 2 Algorithm) = 4pts

La recherche peut se faire au pire cas en 2N itérations (parcours d’une colonne et d’une ligne) soit
une complexité linéaire O(N). (2pts)

bool rech(int **M,int N,int x) (2pts, 1pt par boucle)

{ int i=1;
while (i<=N && M[i][1]<x) i++; // N Itérations au pire cas
if (M[i][1]==x) return true;

i--; int j=1;

while (j<=N && M[i][j]<x) j++; // N Itérations au pire cas
if (M[i][j]==x) return true;
return false;
}

4. (4pts) Le carré d’un graphe orienté G

Graphe buildG2(Graphe G) {
for (int u = 0 ; u < G.n ; u++) {
int k=0; //Nombre d’arcs ajoutés
Bloc *courant1 = [Link][u];
while (courant1 != NULL) {
int v = courant1->val;
courant2 = [Link][v];
while (courant2 != NULL) {
int w = courant2->val;
//chercher si (u,w) n’existe pas déjà
courant3 = [Link][u];
while (courant3 != NULL && courant3->val != w) courant3 = courant3->suiv;
//insertion de (u,w) en tête si (u,w) n’existe pas déjà
if (courant3 == NULL)
{nouv=new Bloc; nouv->val = w; nouv->suiv = [Link][u]; [Link][u] = nouv; k++;}
courant2 = courant2->suiv;
}
courant1 = courant1->suiv;
}
}
G.m += k; return G;
}
Barème :
Parcours : 2pts
Recherche de l’existence : 1pt
Insertion et modification du nombre d’arcs : 1pt