UNIVERSITE DE LA MANOUBA
ANNEE UNIVERSITAIRE
-----¤¤¤¤-----
2014-2015
ECOLE NATIONALE DES SCIENCES
DE L'INFORMATIQUE
Devoir Surveillé 1er Semestre
Matière : Algorithmique, Structures de Données et Programmation C
Date : 13-11-2014
Niveau : II1
Durée: 2H
ENSEIGNANTS : K. BEN RHOUMA, A. BEN HASSINE, W. AKKARI, F.BEN HAMIDA,
Documents : Non autorisés
O. FAKHFAKH, R. CHEBIL.
-
Il est fortement recommandé de lire la totalité des questions avant de répondre
-
Il sera tenu compte de la présentation et de la clarté de vos réponses
- Dans chacun des deux problèmes, l’utilisation d’un module (procédure ou fonction)
déjà développé dans une question antérieure est permise.
Publicité
Problème 1: Algorithmique (10 points)
On s’intéresse, dans ce problème, à la représentation et au traitement de l’ensemble des
gouvernorats de la Tunisie. Chaque gouvernorat est représenté par son nom, le nombre de ses
habitants et sa superficie (en Km2).
Partie I
1. Définir le type ENS-GOUV permettant de représenter l’ensemble des gouvernorats de la
Tunisie.
2. Ecrire une procédure Lecture permettant de lire toutes les données relatives à l’ensemble des
gouvernorats.
3. Ecrire une fonction Recherche qui, étant donné le nom d’un gouvernorat, retourne son rang
dans l’ensemble des gouvernorats s’il existe et 0 sinon.
4. Ecrire un module Densité qui, étant donnés le nombre d’habitants d’un gouvernorat ainsi que sa
superficie, retourne le nombre d’habitants par Km2.
5. Ecrire un module Densité-Min-Max permettant d’afficher le nom du gouvernorat ayant la
densité minimale ainsi que le nom du gouvernorat ayant la densité maximale.
Partie II
Dans cette partie, on souhaite donner plus de précisions sur chaque gouvernorat en ajoutant à la
représentation précédente, le nombre de délégations qu’il comporte ainsi que l’adresse du siège du
1/3
gouvernorat. L’adresse est considérée comme une structure de données composée par le nom de la
Publicité
rue, le numéro dans la rue et le code postal.
6. Définir le type ENS-GOUV-ETENDU permettant de représenter l’ensemble des gouvernorats
de la Tunisie.
7. Ecrire une fonction NbreDelegations qui calcule le nombre total de toutes les délégations de la
Tunisie.
8. Afin de pouvoir changer l’adresse du siège d’un gouvernorat, écrire un module ChangeAdr qui,
étant donnés le nom d’un gouvernorat ainsi que l’adresse de son nouveau siège permet
d’effectuer les mises à jour nécessaires.
9. On souhaite effectuer une ré-organisation des gouvernorats ; pour ceci, nous commencerons par
supprimer les gouvernorats dont le nombre de délégations représente moins que 5% du nombre
total de délégations du pays. Ecrire un module permettant de supprimer les gouvernorats
obéissant à ce critère.
Problème 2: Programmation C (10 points)
On s’intéresse, dans ce problème, au stockage et au traitement de l’ensemble des Noms et des
Prénoms des employés d’une société. Chaque employé est représenté par une seule chaîne de
caractères comportant son nom suivi de son prénom et obéissant aux règles suivantes :
- Le nom et le prénom sont séparés par un ou plusieurs espaces ;
- Le nom ne comporte pas d’espaces même s’il est composé ;
- Le prénom ne comporte pas d’espaces même s’il est composé ;
- Le nom peut être précédé par des espaces ;
- Le nom et le prénom sont écrits en minuscules ;
- Le prénom peut être suivi par des espaces.
Par exemple : la chaîne " bensalah mohamedali " représente l’employé ayant le nom :
Ben Salah et le prénom : Mohamed Ali.
Dans tout le problème, l’utilisation des fonctions définies dans les bibliothèques <stdio.h>,
Publicité
<string.h> et <stdlib.h> est permise.
Partie I
Dans un premier temps, on se limitera au traitement du Nom-Prénom d’un seul employé représenté
par une chaîne de caractères NP.
1. Ecrire une fonction SupprimeEspace qui, étant donnée une chaîne NP, enlève les espaces
supplémentaires tout en gardant un seul espace séparant le nom du prénom.
Exemple : " bensalah mohamedali " sera transformée en la chaîne : "bensalah mohamedali".
2/3
2. Ecrire une fonction PrenomNom qui, étant donnée une chaîne NP ne comportant pas d’espaces
supplémentaires, la modifie de façon à ce que le prénom apparaisse avant le nom.
Exemple : "bensalah mohamedali" sera transformée en la chaîne "mohamedali bensalah".
3. Ecrire une fonction FormaterNP qui, étant donnée une chaîne NP ne comportant pas d’espaces
supplémentaires, retourne une chaîne sous la forme suivante : "<nom>ˈ ˈ<première lettre du
prénom".
Exemple : "bensalah mohamedali" donne "bensalah m".
4. Ecrire une fonction Test qui, étant données deux chaînes NP1 et NP2 pouvant comporter des
espaces supplémentaires, retourne 1 si celles-ci représentent le même employé et 0 sinon.
Exemple : " bensalah mohamedali " et " bensalah mohamedali " représentent le
même employé.
Partie II
Publicité
Dans cette partie, on s’intéresse à la gestion de l’ensemble des noms-prénoms des employés
obéissant aux règles annoncées au début de l’énoncé.
5. Donner une structure adéquate permettant de représenter un ensemble d’un maximum de 50
employés et facilitant les traitements demandés ci-dessous.
6. Ecrire un programme permettant de :
a. Lire le nombre N des employés.
b. Lire le Nom-Prénom de chacun des N employés dans une chaîne NP d’un maximum de 40
caractères et la mémorise dans la structure choisie en lui réservant dynamiquement l’espace
qui lui est nécessaire.
c. Enlever les duplications de l’ensemble des Noms-Prénoms des N employés de manière que
chaque employé apparaisse une et une seule fois. Après avoir enlevé les duplications, la
chaîne représentant chaque employé ne doit pas contenir des espaces supplémentaires.
d. Transformer tous les Noms-Prénoms sous la forme suivante : <nom>ˈ ˈ<première lettre du
prénom>.
e. Trier l’ensemble des Noms-Prénoms des employés par ordre alphabétique.
f. Afficher la liste triée des employés (un employé par ligne).
Bon Travail
3/3