Examen de contrτle d'algorithmique et structures de donnιes. Juin 2005.
Universitι
de Tunis
Institut Supιrieur de Gestion
Dιpartement Informatique
EXAMEN
DE CONTROLE
D'ALGORITHMIQUE ET STRUCTURES DE DONNEES
Niveau : 2eme Annιe Informatique Appliquιe ΰ la Gestion
Durιe : 2 heures
Annιe Universitaire : 2004/2005
Enseignants : N. Ben Amor, L. Ben Said, K. Jebli, A. Smida, A. Ben Othmane
Remarques importantes : L'examen comporte 9 pages et 4 exercices.
Les mιthodes demandιes doivent κtre ιcrites en Java. Les exceptions doivent κtre traitιes.
Les interfaces des structures de donnιes dont vous pourrez avoir besoins sont en annexe ΰ la fin de ce document (pages 8 et 9).
Il sera tenu compte de la prιsentation.
Rιpondre uniquement sur le formulaire.
Documents : Non autorisιs
Exercice 1 : (7 points)
On dispose d'une File d'entiers non triιe FI. On voudrait trier les ιlιments de cette File dans l'ordre croissant en utilisant un arbre binaire de recherche.
a/ Donner la dιfinition d'un arbre binaire de recherche.
b/ Les interfaces des types File (File_Attente) et arbre binaire de recherche (Arb_Bin_Recherche) sont en annexe.
On voudrait rajouter ΰ l'interface Arb_Bin_Recherche une mιthode permettant de copier les ιlιments de l'arbre dans une file d'attente de faηon ΰ obtenir une file dont les ιlιments sont triιs par ordre croissant. Implιmenter cette mιthode appelιe ArbreBinVersFile (voir annexe).
public File_Attente AbreBinVersFile()
On voudrait utiliser cette mιthode et crιer une classe utilisatrice nommιe FileETArbreRecherche qui permet :
· d'implιmenter la mιthode FileVersArbreBin.
· Puis de crιer une File de 10 entiers non triιs F1
· d'afficher F1 non triιe
· puis d'effectuer l'appel suivant : F1 = FileVersArbreBin(F1)..Abreliin VersFile()
Remplissez les ιlιments manquants dans la classe FileETArbreRecherche suivante : r public class FileETArbreRecherche {
public static Arb_Bin_Recherche FileVersArbreBin(File_Attente F) {
Arb_Bin_Recherche A = new ArbreRechercheCh(...................................................................................... );
{while (!F.Vide()){
} return A
}
public static void main( String [] x) {
File Attente Fl = new FileChainιe( ..);
for (int i=1; i<=10; i++)
{ System.out.println("Introduire l'entier n : "+i);
int ent=Readln.unint();
try {............................................................................................................................................}
catch (FileSatureeException e) System.out.println(e); }
}
Fl.Afficher();
FI = FileVersArbreBin(F1 ).AbreBinVersFile() ;
Fl.Afficher(); } }
c/ Est-ce que l'implιmentation d'une maniθre ou d'une autre peut influencer les mιthodes dιveloppιes ci- dessus ? Justifiez votre rιponse.
d/ Justifier l'emploi d'un arbre binaire de recherche.
Exercice 2 : (5 points)
On dispose d'une liste linιaire d'entiers. On cherche ΰ inverser cette liste. Pour cela, on pense ΰ utiliser une
autre structure de donnιes intermιdiaire qui facilitera cette inversion de faηon ΰ pouvoir retirer les ιlιments de la liste dans l'ordre et les placer dans la structure intermιdiaire. Il suffira ensuite de construire la nouvelle liste en rιcupιrant, tout en supprimant, les ιlιments de la structure intermιdiaire.
a/ Quel est le type de la structure intermιdiaire nιcessaire (choisir entre liste, file et pile).
b/ On vous demande :
· d'ιcrire la mιthode permettant l'inversion rιpondant aux hypothθses ιnoncιes prιcιdemment
· puis d'ιcrire un programme permettant de saisir une liste de 10 entiers, de l'afficher, de l'inverser, et enfin d'afficher la liste rιsultat.
Remarque : Les mιthodes ΰ utiliser sont dιcrites dans les interfaces en annexe.
public clans Listelnversιe
{ public static void inverser(Liste L) {
public static void main(String[] x) {
}}
Exercice 3 : (4 points)
Nous voulons dιfinir une structure de donnιes correspondant ΰ la notion d'ensemble. Un ensemble est une collection d'objets de mκme type et tous distincts.
L'interface du type ensemble est dιcrite en annexe.
On se propose d'implιmenter le type Ensemble ΰ l'aide d'une liste.
On vous demande d'implιmenter les opιrations suivantes : appartient et ajouter appartenant ΰ l'interface Ensemble en utilisant les listes que l'on suppose dιjΰ implιmentιes et dont l'interface se trouve en annexe. Sachant que :
· la mιthode appartient teste l'existence d'un ιlιment (Object) et retourne vrai s'il existe et faux sinon.
· La mιthode ajouter permet d'ajouter un ιlιment (Object) ΰ la suite des ιlιments dιjΰ existants.
· On suppose que les exceptions sont dιjΰ implιmentιes et peuvent κtre utilisιes.
public boolean appartient(Obiect o) throws EnsembleVideException
{
public void aioute(Object o throws EnsembleSaturιException,TypelncompatibleException
{
Exercice 4 : (4 points)
On voudrait redιfinir le type chaξne de caractθres en Java (String) en proposant une implιmentation sous forme d'une liste chaξnιe de caractθres nommιe Lchaξne.
On vous demande d'ιcrire :
a/ une mιthode qui prend en entrιe une chaξne de caractθres sous la forme d'une valeur de type String et retourne en sortie la valeur correspondante de type Lchaξne.
b/ une deuxiθme mιthode rιcursive de copie d'une chaξne de caractθres de type Lchaξne dans une autre (sans partage des ιlιments des listes).
La classe Utilisatrice est la suivante :
public class ListeCaracteres
{ public static Liste convertir (String S)
{ ..
}
public static void copier(Liste Li, Liste L2, int i)
}
public static void main(String[] x)
{try { Liste Lchaξne = new ListeChainee(Class.forName("java.lang.Character"));
Liste L2 = new ListeChainee(ClassforName(java.lang.Character")); System.outprintln("Tntroduire une chaξne de caractθres");
String S=Readln.unString();
Lchaξne = convertir( S);
Lchaξne.Afficher();
copier(Lchaξne, L2.
L2.Afficherω;
catch(ClassNotFoundException e) {System.out.println("Classe non trouvιe");
} }