كﻟﯾﺔ اﻟﻌﻠوم – ﺗﯾﺟﺎﻧﻲ ھدام
Faculté des Sciences – Tidjani HADDAM
Tel : 043 21 63 71 Fax : 043 21 63 70
Site web: fs.univ-tlemcen.dz
Concours d’accès en 3ème cycle DOCTORAT LMD en informatique
Options : « Ingénierie des Systèmes d’Information et de Connaissance
et Aide à la Décision » et « Informatique Distribuée et Réseaux »
Epreuve Algorithmique - Durée : 1 heure 30 min
Exercice 1 : (6 points)
1.1 Dans ce qui suit, on notera n le nombre de nœuds d'un arbre binaire et h sa hauteur.
a. Quelle est la hauteur maximale d'un arbre à n nœuds ?
b. Quel est le nombre maximal de feuilles d'un arbre de hauteur h ?
c. Quel est le nombre maximal de nœuds d'un arbre de hauteur h ?
d. Quelle est la hauteur minimale d'un arbre de n nœuds ?
1.2 Considérons une liste doublement chainée l1, et une liste doublement chainée circulaire l2
sachant que les deux listes sont triées dans un ordre croissant. Calculer intuitivement la
complexité (pire cas) des opérations suivantes :
a. Trouver le plus grand élément dans chacune des deux listes ?
b. Inverser chacune des deux listes ?
Supposons que l’on a une fonction Nœud* position(Nœud *racine , int pos ) permettant de
retourner un pointeur vers l’élément de la liste se trouvant à la position pos , et que la taille de la
liste l2 est N. On veut appliquer une recherche pour vérifier si un élément appartient à l2 en
utilisant la fonction précédente.
c. Quelle serait la complexité (pire cas) de cette recherche ?
Exercice 2 : (7 points)
Proposition 1 :
Qu’affiche le programme suivant?
#include <stdio.h>
void Mystere(int N)
{
int M = N;
int Somme = 0;
while(M > 0){
int C = M % 10;
int F = 1;
for (int i = 2; i <= C ; ++i){ F *= i; }
Somme += F;
M /= 10;
}
if (Somme == N) printf("Propriété vérifiée pour %d\n", N);
else printf("Propriété non vérifiée pour %d\n", N) ;
}
int main(){
Mystere(145); Mystere(11); Mystere(40585);
}
En déduire ce que fait la fonction Mystere.
Solution :
Propriété vérifiée pour 145.
Proriété non vérifiée pour 11.
Propriété vérifiée pour 40585.
La fonction Mystere permet de tester si un nombre est factorion : c-a-d il est égal à la somme
des factorielles de ses chiffres (ex. 145 = 1! + 4! + 5!).
Proposition 2 :
Qu’affiche le programme suivant?
#include <stdio.h>
int main()
{
void Modif(int X, int *Y, int *Z); /* Prototype */
int T[] = {12, 12, 13, 12, 13, 12, 13};
int *P = T;
printf("1. %d\n", *P - 4);
printf("2. %d\n", *(P + 2) + 3);
printf("3. %d\n", *(P + (*P)/2 - (T[4]-T[3])));
printf("4. %d\n", (T+2)[2]);
printf("5. %d\n", (T+2)[3]);
printf("6. %d\n", *(P + (*P)/4 - ((T+2)[2]-(T+2)[3])));
Modif(T[0], &T[1], &T[2]);
Modif(T[0], &(*(P+3)), T+4);
Modif(T[0], &T[5], T+6);
printf("T = %d %d %d %d %d %d %d\n", T[0], T[1], T[2], T[3], T[4], T[5], T[6]);
return 0;
}
void Modif(int X, int *Y, int *Z)
{
*Y = *Y + *Z + X;*Z = *Y - *Z – X; *Y = *Y - *Z - X;
}
Solutions :
1. 8
2. 16
3. 12
4. 13
5. 12
6. 13
T = 12 13 12 13 12 13 12
Proposition 3 :
Qu’affiche le programme suivant?
#include <stdio.h>
void Mystere(char mot[], int taille, char * tmp, int * indice)
{
int i=0, c1=0, c2=0, c3=0;
while(i < taille - 1 && (mot[i] == 'a' || mot[i] == 'b')){
if(mot[i] == 'a'){ c1++; } else {c2++;}
i++;
}
*tmp = mot[i]; * indice = i;
while(i < taille && mot[i] == 'c'){ i++; c3++; }
if ((c1 + c2 + c3 == taille) && (c1 == c2)) printf("Accepté\n"); else printf("Refusé\n");
}
int main(void)
{
char tmp;
int indice;
char mot1[10] = {'a','a','a','b','b', 'b', 'c','c','a','a'}; char mot2[7] = {'a','a','b','b', 'b', 'c','c'}; char mot3[4] =
{'c','c','c','c'};
Mystere(mot1, 8, &tmp, &indice);
Mystere(mot2, 10, &tmp, &indice);
Mystere(mot3, 10, &tmp, &indice);
Mystere(mot1, 10, &tmp, &indice);
mot1[indice+2] = tmp;
Mystere(mot1, 10, &tmp, &indice);
mot1[indice+3] = tmp;
Mystere(mot1, 10, &tmp, &indice);
return 0;
}
En déduire ce que fait la fonction Mystere.
Solutions :
Accepté
Refusé
Refusé
Refusé
Refusé
Accepté
La fonction Mystere permet d'accepter uniquement les mots qui ont la forme :
aN bN c* (N >= 0) ⇒ N a suivis par N b, suivis par 0 ou plusieurs c.
Exercice 3 : (7 points)
3.1 Calculer la complexité au pire des cas de chacune des fonctions suivantes :
int valeur (Liste L, int pos){ boolean existe (Liste L, int e){
int i = 1 ; boolean found = false ;
Liste tmp = L.tete ; int d = 1, f = L.taille() ;
while(tmp != null && i < pos){ while(d <= f && !found){
tmp = tmp.next; int milieu = (d +f)/2;
i++; int val_milieu = valeur(L, milieu);
} if(val_milieu == e)found = true ;
return tmp.val ; else if(val_milieu < e) d = milieu + 1;
} else f = milieu – 1;
}
return found ;
}
3.2 Un TAS (Heap en Anglais) est un arbre binaire quasi-parfait tel que la valeur de chaque
sommet est inférieure à la valeur de (son ou) ses fils ; représenté par la structure de données
suivante :
Type TAS = {
Tab : tableau [1..MAX] de sommets.
Nb : entier (nombre de sommets existants).
}
Éplucher un tas consiste à supprimer le plus petit élément de cette structure, il sera remplacé par
la dernière feuille de l’arbre (ex. 30 de la figure sera remplacé par 63).
a. Écrire un algorithme pour réaliser cette opération sachant que le résultat doit garder la
propriété du tas .
Le tri par tas consiste à appeler l'opération éplucher plusieurs fois tel qu'à chaque fois l'élément
supprimé est ajouté à la fin d'un certain tableau. Ce tableau trié est retourné à la fin.
b. Quelle est la complexité de ce tri ?
