Examen info structures données avec c -Structures des donne

Télécharger PDF

Examen d'Informatique INFO3

Cet examen, d'une durée d'1h30, a été élaboré par le Département Informatique de la Faculté des Sciences et Techniques de Mohammedia, Université Hassan II de Casablanca. L'utilisation de documents et de tout appareil électronique est strictement interdite. La présentation des réponses sera prise en compte rigoureusement.

Exercice 1 : Gestion de listes chaînées d'étudiants

Soient L1 et L2 deux listes chaînées d'étudiants inscrits dans une école, totalement ordonnées par NOM. La structure d'un inscrit est définie comme suit :

typedef struct inscrit {
char Nom[15];
char Prenom[10];
char Tel[15];
char sexe;
float Moy;
struct inscrit *suivant;
} liste_ETD;

Cette définition de structure inscrit utilise un pointeur suivant pour lier les éléments entre eux, formant ainsi une liste chaînée. Le mot-clé typedef permet d'utiliser liste_ETD comme un alias pour struct inscrit, simplifiant la déclaration de variables de ce type.

1. Allocation mémoire pour un élément

Écrire une fonction qui permet d'allouer de l'espace mémoire pour un nouvel élément de la liste liste_ETD. Cette fonction renverrait un pointeur vers la nouvelle structure allouée, initialisée et prête à être insérée dans la liste, généralement en utilisant malloc en langage C.

2. Insertion triée dans une liste

Écrire une fonction qui insère un nouvel inscrit dans la liste L3 en respectant le tri par NOM. La fonction doit parcourir la liste pour trouver la position correcte où insérer le nouvel élément, afin de maintenir l'ordre alphabétique des noms des étudiants.

3. Fusion de deux listes chaînées triées

Écrire une fonction qui fusionne les listes L1 et L2 (de type liste_ETD), qui sont déjà totalement ordonnées par Nom, en une seule liste L3. L'objectif est de réaliser cette fusion de manière optimisée pour que L3 soit également triée par Nom, sans nécessiter un nouveau tri complet après l'opération.

4. Suppression d'éléments selon un critère

Écrire une fonction qui supprime de la liste L3 tous les inscrits dont la moyenne est inférieure à 10. La fonction doit correctement gérer la libération de la mémoire des éléments supprimés et la mise à jour des pointeurs de la liste pour maintenir son intégrité.

5. Affichage d'une liste chaînée

Écrire une fonction qui affiche tous les détails (Nom, Prénom, Téléphone, Sexe, Moyenne) de chaque inscrit présent dans une liste chaînée donnée. Cette fonction implique un parcours simple de la liste, du début à la fin.

6. Programme principal avec menu interactif

Réaliser le programme principal (main) qui présente un menu de choix à l'utilisateur. Ce menu doit permettre d'appeler les différentes fonctions définies précédemment pour manipuler les listes d'étudiants (par exemple, ajouter, supprimer, fusionner, ou afficher).

Exercice 2 : Manipulation d'une pile (structure LIFO)

Une pile est une structure de données de type LIFO (Last In, First Out) : le dernier élément entré est le premier à sortir.

On supposera que l'on dispose des fonctions de base suivantes pour manipuler une pile :

donnée(elt) : renvoie la donnée associée à l'élément elt.
estVide(P) : renvoie vrai si la pile P est vide, faux sinon.
sommet(P) : renvoie l'élément au sommet de la pile P sans le retirer.
dépiler(P) : supprime l'élément au sommet de la pile P.
empiler(P, elt) : ajoute l'élément elt au sommet de la pile P.

La structure de la pile est définie comme suit :

#define Max 10
typedef struct Tpile {
char elt[Max];
int NbElts;
} Tpile;

Dans cette structure, Max représente la taille maximale fixe de la pile, elt est un tableau de caractères pour stocker les éléments, et NbElts est le nombre d'éléments actuellement présents dans la pile.

1. Fonction `afficherPile(P)`

Écrire une fonction qui affiche tous les éléments de la pile P. Pour ce faire, il est souvent nécessaire de dépiler temporairement les éléments dans une structure auxiliaire ou de parcourir la pile sans la modifier si l'implémentation le permet, puis de restaurer son état initial.

2. Fonction `depilerKelt(P, k)`

Écrire une fonction qui dépile k éléments de la pile P. Si la pile contient moins de k éléments, la fonction doit dépiler tous les éléments restants de la pile jusqu'à ce qu'elle soit vide.

3. Fonction `depilerJusquA(P, elt)`

Écrire une fonction qui dépile la pile P jusqu'à ce que l'élément elt soit atteint au sommet. L'élément elt lui-même ne doit pas être dépilé. Si l'élément elt n'est pas trouvé dans la pile après avoir parcouru tous les éléments, alors la fonction doit dépiler toute la pile.

4. Fonction `empilerKelt(P, k)`

Écrire une fonction qui tente d'empiler k nouveaux éléments dans la pile P. Cette opération ne doit être effectuée que si la pile dispose d'au moins k cases disponibles (c'est-à-dire, si Max - NbElts >= k). Dans le cas contraire (pas assez d'espace), aucun élément ne doit être empilé.

Foire Aux Questions (FAQ)

Qu'est-ce qu'une liste chaînée ?

Une liste chaînée est une structure de données linéaire où les éléments, appelés nœuds, ne sont pas stockés de manière contiguë en mémoire. Chaque nœud contient une donnée et un pointeur (ou une référence) vers le nœud suivant de la séquence. Cela offre une grande flexibilité pour l'insertion et la suppression d'éléments, car elle ne nécessite pas de décalage des autres éléments.

Quelle est la différence entre une pile et une file ?

La principale différence réside dans l'ordre d'accès aux éléments. Une pile (Stack) suit le principe LIFO (Last In, First Out), où le dernier élément ajouté est le premier à être retiré. Une file (Queue), quant à elle, suit le principe FIFO (First In, First Out), où le premier élément ajouté est le premier à être retiré, similaire à une file d'attente réelle.

Pourquoi l'allocation dynamique de mémoire est-elle cruciale pour les listes chaînées ?

L'allocation dynamique de mémoire est essentielle pour les listes chaînées car elle permet à la liste de grandir ou de rétrécir en fonction des besoins du programme au moment de l'exécution. Contrairement aux tableaux, la taille d'une liste chaînée n'a pas besoin d'être définie à l'avance, ce qui optimise l'utilisation de la mémoire en allouant de l'espace uniquement lorsque c'est nécessaire pour un nouvel élément.