Département d'Informatique Filières: SMI4 & SMA4
Faculté des Sciences, Université Ibn Zohr Durée: 2h
Agadir 18/05/2018
DS - Structures de données
Session normale
Exercice 1: (6 pts)
1. Donner une fonction récursive som permettant de calculer:
1 2 3 4
0− + − + + ...
4 9 16 25
Exemples:
som(0)=0, som(1)=0-(1/4), som(2)=0-(1/4)+(2/9),
som(3)=0-(1/4)+(2/9)-(3/16)
2. Donner sa complexité en tenant compte les opérations d'addition, soustraction et divi-
sion (le nombre total des opérations). La réponse doit être justi ée. Une réponse
non justi ée ne sera pas prise en compte.
Exercice 2: (14 pts)
On suppose que nous nous disposons d'une liste chaînée d'entiers qui peut être vide ou
non vide (cas général). La structure des noeuds de la liste chaînée est dé nie comme suit:
typedef struct liste{
int data;
struct liste * suivant;
} liste;
Contraintes à respecter: Dans les réponses aux questions ci-dessous, vous n'êtes
pas autorisés à parcourir les noeuds de la liste plus qu'une seule fois ni à faire
appel à d'autres fonctions. La fonction (réponse) qui ne respecte pas les contraintes
ci-dessus ne sera pas prise en compte.
1. Donner une fonction permettant de supprimer (détruire) la tête et la queue d'une liste
chaînée (Il y aura libération de l'espace mémoire occupé par les noeuds tête et queue).
2. Donner une fonction permettant de supprimer le Nième noeud d'une liste chaînée. La
suppression est possible uniquement si la liste comporte au moins N noeuds (Il y aura
libération de l'espace mémoire occupé par le Nième noeud).
3. Donner une fonction permettant d'insérer un élément après le nième noeud d'une liste
chaînée. Si le nombre de noeuds de la liste est inférieure à N, l'insertion s'eectue en
queue de la liste (à la n de la liste).
4. Donner une fonction récursive permettant l'a chage des éléments d'une liste chaînée.
Bon courage
Prof. Mohamed El Ansari Page 1/1
