Exercices

Questions d'examens de Structures de données ainsi que leurs corrigés

Questions d'examens de Structures de données ainsi que leurs corrigés Contrôle continu du 7 mai 2001 (notes) ●

Arbre lexicographique

●

Arbre de tri

Examen écrit du 4 octobre 2000 (notes) ●

Arbres + chaînes

●

Les listes

●

Les B-arbres

Examen écrit du 3 juillet 2000 (notes) ●

Conversion arbre-chaîne

●

Arbres multiples

●

Listes

●

Graphes orientés

Contrôle continu du 22 juin 2000 (notes) ●

Fermeture transitive

●

Graphe orienté

●

parcours d'un B-arbre

Contrôle continu du 11 mai 2000 (notes) ●

Chaînes

●

Chaînes

●

Arbre de tri

http://cuisung.unige.ch/std/questions.html (1 of 5) [23-09-2001 15:57:36]

Questions d'examens de Structures de données ainsi que leurs corrigés

Examen écrit du 28 février 2000 ●

Structures statiques

●

Anneaux bidirectionnels

●

Arbres dépliables

●

B-arbres

Examen écrit du 11 octobre 1999 ●

Anneaux bidirectionnels

●

Arbres

●

Listes

●

Chemin le plus court dans un graphe

Examen écrit du 30 juin 1999 (notes) ●

Anneaux bidirectionnels

●

Arbres dépliables

●

Le chemin le plus court

●

Hash-Coding

Contrôle continu du 14 juin 1999 (notes) ●

Graphes orientés

●

B-Arbres

●

Adressage associatif par transformation de clés (Hash-code)

Contrôle continu du 29 avril 1999 (notes) ●

Chaînes bidirectionelles

●

Arbre lexicographique

Examen écrit de février 1999 ●

http://cuisung.unige.ch/std/questions.html (2 of 5) [23-09-2001 15:57:36]

Questions d'examens de Structures de données ainsi que leurs corrigés

Examen écrit du 7 octobre 1998 ●

Arbre binaire Structures de graphes orientés (tri topologique inverse)

●

comparaison de B-arbres et B*-arbres

●

Hash-coding

●

Examen écrit du 25 juin 1998 ●

Arbres dépliables

●

Recherche dichotomique Hash-coding Tables de décision

● ●

Contrôle continu du 15 juin 1998 ●

Fichiers séquentiels indexés

●

Recherche dans un B-arbre

●

Le chemin du moindre coût

Contrôle continu du 4 mai 1998 ●

Chaînes bidirectionnelles

●

Chaînes mono-directionnelles

●

Anneaux bidirectionnels

●

Arbre syntaxique

Examen écrit de février 1998 ● ●

arbre dépliable de tri Fichiers séquentiels indexés

Examen écrit du 13 octobre 1997 ●

Structures de graphes

●

un réseau de transport

http://cuisung.unige.ch/std/questions.html (3 of 5) [23-09-2001 15:57:36]

Questions d'examens de Structures de données ainsi que leurs corrigés

Examen écrit de juillet 1997 ● ● ●

Arbres binaires Graphe orienté B-arbre

Contrôle continu du 16 juin 1997 ●

Arbre lexicographique

●

Hash-code

●

Tables de décision

Contrôle continu du 28 avril 1997 ●

Chaînes bidirectionnelles

●

Chaînes bidirectionnelles

●

Arbre généalogique

Examen écrit du 5 mars 1997 ●

Tri dans une chaîne Arbres syntaxiques et chaînes

●

B-arbre

●

Examen écrit du 15 octobre 1996 ●

Chaînes bidirectionnelles

●

Fichiers séquentiels indexés et B-arbres

Examen écrit du 9 juillet 1996 ●

Chaînes mono-directionnelles

●

Réseau autoroutier

http://cuisung.unige.ch/std/questions.html (4 of 5) [23-09-2001 15:57:36]

Questions d'examens de Structures de données ainsi que leurs corrigés

Contrôle continu du 17 juin 1996 ●

Anneaux bidirectionnels

●

Arbre de tri

●

Tri topologique inverse

●

B-arbre

Contrôle continu de mars 1996 ●

Structure de chaîne

Contrôle continu du 20 juin 1995 ●

Chaînes bidirectionnelles

●

Arbre lexicographique

●

Plus courts chemins dans un graphe

http://cuisung.unige.ch/std/questions.html (5 of 5) [23-09-2001 15:57:36]

Description du cours "Structures de donnees"

TITRE: STRUCTURES DE DONNEES Enseignant: Bertrand Ibrahim (MER) No: 1803

Heures totales: 84

Destinataire licence informatique diplôme informatique certificat . info et stat. dipl. math.info.

Par semaine: Cours: 4 Exercices: 2

Semestre 2 2 2 4

Oblig.

Facult.

Option

Pratique: Crédits 10 10 10

Objectifs Ce cours a pour but d'introduire un panorama des structures de données complexes en suivant l'approche de la programmation procédurale.

Contenu Note: un calendrier d'avancement dans le cours est disponible pour vous permettre de déterminer ce qui a été abordé à chaque leçon. ● structures de données statiques, types abstraits, notion de pointeur, ● structures dynamiques fondamentales: ❍ chaînes (monodirectionnelles, bidirectionnelles), anneaux (monodirectionnels, bidirectionnels), piles, files d'attentes, ❍ listes généralisées, ❍ arbres , ❍ graphes

● ● ●

algorithmes de construction, de parcours et de manipulation; représentations internes, opérations de base, transformation de clés et «hash-coding», structures complexes: séquentiel indexé et B-arbres, tables et arbres de décision.

Forme de l'enseignement: Cours ex-cathedra, exercices, travaux pratiques

http://cuisung.unige.ch/std/Descr.html (1 of 2) [23-09-2001 15:58:15]

Description du cours "Structures de donnees"

Evaluation: ●

Contrôles continus : ❍ lundi 7 mai 2001 de 14h00 à 16h00, auditoire U600 (Uni Dufour, 1er sous-sol) - notes jeudi 21 juin de 14h00 à 16h00, salle 259 Examen écrit, juillet Evaluation du cours par les étudiants (année 2000) ❍

● ●

Note: dans les deux formes d'évaluation des étudiants (contrôle continu ou examen écrit), la note sera laissée en suspend jusqu'à avoir satisfait aux exigences des travaux pratiques (avoir 75% des TPs acceptés par l'assistant).

Encadrement: Bertrand Ibrahim (bur. 350), Wolfgang Müller (bur. 336), Yvan Petroff (bur. 306).

Documentation: livre support de cours et liste d'ouvrages de référence. Liste des questions d'examens avec leurs corrigés. Enregistrements sonores

Liaison avec d'autres cours: Préalable requis: Algorithmique ou Introduction à l'informatique. Préparation pour: informatique théorique, initiation à la recherche opérationnelle et langages informatiques. B. Ibrahim 19.04.01

http://cuisung.unige.ch/std/Descr.html (2 of 2) [23-09-2001 15:58:15]

Notes du contrôle continu du 7 mai 2001

Structures de Données

Notes du contrôle continu du 7 mai 2001 Nom

Q1 Q2 Note

ALBUQUERQUE Michel

5

19

2,3

BAERTSCHIGER Didier

30

35

6,0

BELKABIR M??

3

0

0,3

BOUDJNANE Yassin

13

26

3,9

BRUNSCHWIG Guillaume

4

2

0,6

CABY Gerda

1

14

1,5

CHARPILLOZ Christophe

25

16

4,1

COSTANITA Rodrigue

9

23

3,2

DUCIMETIERE Jérôme

1

29

3,0

EL HASNAOUI Hassan

4

10

1,4

EMIYAN Stéphane

15

29

4,4

ETIENNE Julien

20

27

4,7

FERROUKHI Sid-Ahmed

0

13

1,3

FIRST Jean

22

33

5,5

FONTIGNIE Jacques

30

29

5,9

GULATI Asheesh

22

35

5,7

[5,5-6,0] xxxxx xxxx

JAMES Mélanie

30

35

6,0

[5,0-5,5[ xxxxx x

JOSS Olivier

30

27

5,7

[4,5-5,0[ xxxxx xx

LAGROUNI Kamal

25

24

4,9

[4,0-4,5[ xxxx

MAGPANTAY Tristan

19

29

4,8

MARQUIS Samuel

22

29

5,1

NGUYEN Duy

22

29

5,1

Répartition des notes

[3,5-4,0[ xxx [3,0-3,5[ xxxxx

http://cuisung.unige.ch/std/CC/010507/Notes.html (1 of 2) [23-09-2001 15:58:19]

[2,5-3,0[ [2,0-2,5[ x

Notes du contrôle continu du 7 mai 2001

NGUYEN Thi Anh Thu

25

12

3,7

[1,5-2,0[ xx

PINEIRO Elvis

25

22

4,7

[1,0-1,5[ xx

PORTA Jonathan

9

29

3,8

PRAPLAN Christophe

22

30

5,2

QUANG Anh

15

26

4,1

REVERDON Ludovic

4

26

3,0

RIVERA CAMACHO Ernesto A. 25

35

6,0

ROSSET Giles

27

35

6,0

SARTORETTI Fabien

25

26

5,1

SAYAH Saïd

15

26

4,1

SCHALLER Cynthia

25

28

5,3

STURB Ronald

1

14

1,5

SUHNER Thierry

12

35

4,7

STRUMIELLO Olivier

24

24

4,8

TUVERI Jairo

25

24

4,9

UMER Ali

4

26

3,0

VILLALBA Alfredo

30

35

6,0

VILLASUSO Pablo

22

29

5,1

WANG ia Ying

12

18

3,0

[0,5-1.0[ x [0-0,5[

Dernière modification: 15.06.01

http://cuisung.unige.ch/std/CC/010507/Notes.html (2 of 2) [23-09-2001 15:58:19]

x

Structuration des Données Informatiques - 8.2, exercice 5

Arbre lexicographique Question posée au contrôle continu du 7 mai 2001 On a construit un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de façon que les chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante

Les arcs sont étiquettés avec les lettres de l'alphabet (on suppose ici que l'on ne tient pas compte des accents sur les lettres) et les noeuds contiennent un booléen indiquant si le chemin de la racine à ce noeud représente un mot complet ou pas (sur le dessin - = faux et * = vrai). Sur la base des déclarations suivantes, écrivez une fonction Trouve indiquant si un mot se trouve dans le dictionnaire. type VersNoeud= ^Noeud; Noeud= record Desc: array['a'..'z'] of VersNoeud; Complet: boolean; end; { Noeud } var Dico: VersNoeud; function Trouve(Mot: string; Dico: VersNoeud):boolean; Solution

http://cuisung.unige.ch/std/ex/8/2e.html [23-09-2001 15:58:24]

Structuration des Données Informatiques - 8.1, exercice 8

Arbre de tri Question posée au contrôle continu du 7 mai 2001 Complétez le code des procédures ajouteElement, sommeArbre et produitArbre. La procédure accumulerArbre est facultative et vaut un bonus de 5 points. { Ajoutez le code necessaire } program completer; type pElement TElement

= ^TElement; = record mContenu : integer; mDroite,mGauche : pTElement; end; { TElement } {un type de FONCTION} TFonction = function(x, y:integer):integer;

var gRacine: pElement; i,gSomme,gProduit, gNouveau : integer; { multiplier: Cette fonction multiplie deux nombres entiers parametres: inX, inY: les deux nombres a multiplier resultat: inX*inY } function multiplier(inX,inY:integer):integer; begin multiplier:=inX*inY; end; { multiplier } { ajouter: Cette fonction ajoute inX a inY parametres: inX, inY: les deux nombres a additionner resultat: http://cuisung.unige.ch/std/ex/8/1h.html (1 of 5) [23-09-2001 15:58:29]

Structuration des Données Informatiques - 8.1, exercice 8

inX+inY } function ajouter(inX,inY:integer):integer; begin ajouter:=inX+inY; end; { ajouter } {---------------------------------------gestion d'arbres ----------------------------------------} { creeElement_Contenu Cette fonction cree un nouveau element d'un arbre avec un contenu donné. Les pointeurs de l'element a creer vont etre mis a NIL. parametres: inNouveauContenu : le contenu de l'element a creer var outElement: le pointeur sur l'element cree } procedure creeElement_Contenu(inNouveauContenu : integer; var outElement : pElement); begin new(outElement); outElement^.mDroite:=nil; outElement^.mGauche:=nil; outElement^.mContenu:=inNouveauContenu; end; { creeElement_Contenu }

{ Ajoute un element a l'arbre pour que l'arbre soit un arbre de tri, les elements les plus petits a gauche. parametres: inNouveauContenu: le contenu de l'element a ajouter inoutRacine: la racine de l'arbre a qui un element va etre ajoute } procedure ajouteElement(inNouveauContenu:integer; var inoutRacine: pElement); begin {QUESTION: http://cuisung.unige.ch/std/ex/8/1h.html (2 of 5) [23-09-2001 15:58:29]

Structuration des Données Informatiques - 8.1, exercice 8

AJOUTEZ LE CODE NECESSAIRE POUR QUE ajouteElement FASSE CE QUI EST DIT DANS LE COMMENTAIRE. Vous n'avez pas besoin de variables supplementaires. Toutefois, on autorise l'ajout de variables LOCALES. }

end; { ajouteElement } { Cette procedure calcule la somme de tous les elements dans l'arbre et l'ajoute a inoutSomme parametres: var inoutSomme: le parametre d'entree et le resultat var inRacine: la racine de l'arbre a traiter } procedure sommeArbre(var inoutSomme:integer; var inRacine: pElement); begin {QUESTION: AJOUTEZ LE CODE NECESSAIRE POUR QUE sommeArbre FASSE CE QUI EST DIT DANS LE COMMENTAIRE. Vous n'avez pas besoin de variables supplementaires. Toutefois, on autorise l'ajout de variables LOCALES. } end; { sommeArbre } { La procedure qui suit calcule le produit de tout les elements dans l'arbre et le multiplie avec inoutProduit parametres: var inoutProduit: le parametre d'entree et le resultat var inRacine: la racine de l'arbre a traiter } procedure produitArbre(var inoutProduit:integer; var inRacine: pElement); begin {QUESTION: AJOUTEZ LE CODE NECESSAIRE POUR QUE produitArbre FASSE CE QUI EST DIT DANS LE COMMENTAIRE. } http://cuisung.unige.ch/std/ex/8/1h.html (3 of 5) [23-09-2001 15:58:29]

Structuration des Données Informatiques - 8.1, exercice 8

... end; { produitArbre } { La procedure qui suit traverse l'arbre en-ordre et applique inFonction au contenu de la racine et inoutAccumulateur dans la maniere suivante: parametres: inoutAccumulateur: contient un nombre entier apres l'appel il contient le resultat de l'appel inFonction: contient une fonction de type TFonction; inRacine: contient la racine d'un arbre de tri genere par ajouteElement Car inRacine contient un arbre de tri, les elements de l'arbre sont trie du plus petit au plus grand si on fait un parcours en-ordre: n_1 < n_2 < ... < n_m 1..m sont les numeros de visite, donc n_1 est visite avant n_2, n_3 etc. Apres un apel d'accumulerArbre avec inoutAccumulateur=i, inFonction=f, et un arbre comme parametre, inoutAccumulateur va contenir: inoutAccumulateur=f(n_m,f(...,f(n_2,f(n_1,i)))) } procedure accumulerArbre(var inoutAccumulateur : integer; inFonction : TFonction; var inRacine: pElement); begin {QUESTION FACULTATIVE: AJOUTEZ LE CODE NECESSAIRE POUR QUE accumulerArbre FASSE CE QUI EST DIT DANS LE COMMENTAIRE. Vous n'avez pas besoin de variables supplementaires. Toutefois, on autorise l'ajout des variables LOCALES. http://cuisung.unige.ch/std/ex/8/1h.html (4 of 5) [23-09-2001 15:58:29]

Structuration des Données Informatiques - 8.1, exercice 8

} ... end; { accumulerArbre } { SI TOUS LES QUESTIONS SONT BIEN RESOLUES, LE PROGRAMME DOIT AFFICHER TROIS FOIS LES MEMES gSomme ET gProduit RESPECTIVEMENT } begin gRacine:=nil; gSomme:=0; gProduit:=1; { cree arbre aleatoire de 4 elements } for i:=1 to 4 do begin gNouveau:=random(10)+1; ajouteElement(gNouveau, gRacine); gSomme:= gSomme + gNouveau; gProduit:= gProduit * gNouveau; end; { for } write('gSomme:'); writeln(gSomme); write('gProduit:'); writeln(gProduit); gSomme:= 0; gProduit:= 1; sommeArbre(gSomme, gRacine); produitArbre(gProduit, gRacine); write('gSomme:'); writeln(gSomme); write('gProduit:'); writeln(gProduit); gSomme:= 0; gProduit:= 1; accumulerArbre(gSomme, ajouter, gRacine); accumulerArbre(gProduit, multiplier, gRacine); write('gSomme:'); writeln(gSomme); write('gProduit:'); writeln(gProduit); end. Solution

http://cuisung.unige.ch/std/ex/8/1h.html (5 of 5) [23-09-2001 15:58:29]

Notes du contrôle continu du 22 juin 2000

Structures de Données

Notes de l'examen du 4 octobre 2000 Nom

Q1 Q2 Q3

Note

Albuquerque Paul Bajrami Gent

Répartition des notes absent

5

12

11

3,0

Ben Hadj Noureddine

[5,5-6,0] [5,0-5,5[

absent

[4,5-5,0[ [4,0-4,5[

Benkacem Omar

5

20

13

en attente des TPs

Benouataf Khalil

0

0

9

1,0

Coron Olivier

10

30

13

5,5

Londo Ilia

5

18

5

en attente des TPs

[2,0-2,5[

Maddi Brahim

3

6

3

1,0

[1,5-2,0[

Nguyen Thi Amh Thu 4

8

7

2,0

[1,0-1,5[

Schaller Cynthia

1

11

2,0

8

Dernière modification: 27.10.00

http://cuisung.unige.ch/std/Exa/Notes001004.html [23-09-2001 15:58:32]

x

x

[3,5-4,0[ [3,0-3,5[

xx

[2,5-3,0[

[0,0-1,0[

xx xx

Structuration des Données Informatiques - 8.1, exercice 7

Exercice suivant

Arbres + chaînes Question posée à l'examen écrit du 4 octobre 2000 Soit une structure d'arbre de tri et une structure de chaîne bidirectionnelle représentées par les déclarations suivantes: type pNoeudArbre = ^NoeudArbre; NoeudArbre = record nombre: integer; gauche, droite: pNoeudArbre; end; { NoeudArbre } PtrNoeudCh = ^NoeudCh; NoeudCh = record Element: pNoeudArbre; Precedent, Suivant: PtrNoeudCh; end; { NoeudCh } Ecrivez une fonction "Chemin" qui prend en paramètre un arbre et une valeur et retourne en résultat une chaîne pointant sur les éléments successifs de l'arbre qui auront été examinés pour trouver la valeur dans l'arbre de tri: function Chemin(MonArbre: pNoeudArbre; MaValeur: integer): PtrNoeudCh; Il faut bien entendu traiter tous les cas particuliers, p.ex. si l'arbre est vide la chaîne sera vide, si la valeur fournie n'existe pas dans l'arbre, il faudra retourner le chemin parcouru jusqu'à trouver que la valeur ne se trouve pas dans l'arbre. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/1g.html [23-09-2001 15:58:34]

Structuration des Données Informatiques - 9.1, exercice 3

Listes Question posée à l'examen du 4 octobre 2000 { Voici un programme qui gère les listes à la façon de Scheme } program liste_scheme; type PPaireOuValeur = ^TPaireOuValeur; TPaireOuValeur = record mEstValeur : boolean; mValeur : integer; mPremier : PPaireOuValeur; mDeuxieme : PPaireOuValeur; end; var i : integer; gChaine : PPaireOuValeur; function cons_paire_paire(inPremier, inSecond: PPaireOuValeur) : PPaireOuValeur; var lResultat: PPaireOuValeur; begin new(lResultat); lResultat^.mEstValeur:=false; lResultat^.mPremier:= inPremier; lResultat^.mDeuxieme := inSecond; cons_paire_paire:=lResultat; end; { cons_paire_paire } function cons_integer_paire(inPremier: integer; inSecond: PPaireOuValeur): PPaireOuValeur; var lInteger: PPaireOuValeur; begin new(lInteger); lInteger^.mEstValeur:=true; lInteger^.mValeur:=inPremier; cons_integer_paire:=cons_paire_paire(lInteger,inSecond); end; { cons_integer_paire } function cons_integer_integer(inPremier : integer; inSecond: integer): PPaireOuValeur;

http://cuisung.unige.ch/std/ex/9/1c.html (1 of 3) [23-09-2001 15:58:37]

Structuration des Données Informatiques - 9.1, exercice 3

var lInteger : PPaireOuValeur; lPaire : PPaireOuValeur; begin new(lInteger); lInteger^.mEstValeur:=true; lInteger^.mValeur:=inSecond; cons_integer_integer:=cons_integer_paire(inPremier,lInteger); end; { cons_integer_integer } { QUESTION: Ecrivez une fonction qui crée une liste à la façon de Scheme avec les entiers dans l'intervalle de inBegin à inEnd. cree_chaine(5,8) devrait retourner l'equivalent de (list 5 6 7 8). cree_chaine(5,5) devrait retourner l'equivalent de (list 5), cree_chaine(5,4) devrait donner nil comme resultat. } function cree_chaine(inBegin,inEnd : integer ):PPaireOuValeur; var lLastCreated: PPaireOuValeur; var i: integer; begin { } end; { QUESTION: Créez une procedure qui parcourt et affiche des chaînes simples à la Scheme de façon à donner p.ex. pour affiche_chaine(cree_chaine(5,7)) la procédure affiche "(5 6 7)" à l'écran La procedure peut être limitée aux chaines simples (pas de listes imbriquées, donc p.ex. "(list 1 2 3 4)" mais pas "(cons (list 1 2) (list 3 4))") } procedure affiche(inPaireOuValeur: PPaireOuValeur); var lCourant: PPaireOuValeur; begin { http://cuisung.unige.ch/std/ex/9/1c.html (2 of 3) [23-09-2001 15:58:37]

Structuration des Données Informatiques - 9.1, exercice 3

} end; { affiche } begin gChaine:=cree_chaine(1,10); writeln('Chaine cree'); affiche(gChaine); affiche(cree_chaine(5,8)); affiche(cons_paire_paire(cree_chaine(1,2), cons_integer_integer(3,4))); end. Solution

http://cuisung.unige.ch/std/ex/9/1c.html (3 of 3) [23-09-2001 15:58:37]

Structuration des Données Informatiques - 14.3, exercice 8

Les B-Arbres Question posée à l'examen du 4 octobre 2000 . Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 25:

b. Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de l'insertion de la valeur 20 c. Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de l'insertion de la valeur 14 d. Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de l'insertion de la valeur 6 e. Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de la suppression de la valeur 60 f. Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de la suppression de la valeur 63 g. Avec le même B-arbre de départ qu'en (a), dessinez le B-arbre résultant de la suppression de la valeur 80 Solution

http://cuisung.unige.ch/std/ex/14/3h.html [23-09-2001 15:58:43]

Notes du contrôle continu du 22 juin 2000

Structures de Données

Notes de l'examen du 3 juillet 2000 Nom

Q1 Q2 Q3 Q4 Note

Bajrami Gent

6

15

2

0

2,5

Ben Hadj Noureddine

2

8

0

0

1,0

Benkacem Omar

5

6

5

0

1,5

[5,5-6,0]

Benouataf Khalil

0

11

0

0

1,0

[5,0-5,5[

Bobo Ngawouo Aimé Patrick 0

1

2

0

0,5

[4,5-5,0[

x

Braik Ahcene

10

15

0

4

3,0

[4,0-4,5[

xx

Buhler Stéphane

10

13

10

7

4,0

Coron Olivier

8

13

5

2

3,0

Etienne Julien

12

13

11

9

Habachi Arash

6

4

15

Maddi Brahim

3

6

Nguyen Thi Amh Thu

1

Petrini Geo Schaller Cynthia

Répartition des notes

[3,5-4,0[ [3,0-3,5[

xx

[2,5-3,0[

xxx

4,5

[2,0-2,5[

x

13

4,0

[1,5-2,0[

x

2

0

1,0

[1,0-1,5[

xxx

12

0

0

2,5

[0,0-1,0[

x

12

0

13

0

2,5

6

12

0

0

2,0

Dernière modification: 21.07.00

http://cuisung.unige.ch/std/Exa/Notes000703.html [23-09-2001 15:58:48]

Structuration des Données Informatiques - 8.1, exercice 6

Exercice suivant

Conversion arbre-chaîne Question posée à l'examen écrit du 3 juillet 2000 Soit une structure d'arbre de tri et une structure de chaîne bidirectionnelle représentées par les déclarations suivantes: type pNoeudArbre = ^NoeudArbre; NoeudArbre = record nombre: integer; gauche, droite: pNoeudArbre; end; { tNoeudArbre } PtrNoeudCh = ^NoeudCh; NoeudCh = record Donnee: integer; Precedent, Suivant: PtrNoeudCh; end; Ecrivez une fonction "Conversion" qui prend en paramêtre un arbre et retourne en résultat une chaîne contenant les valeurs de l'arbre dans l'ordre croissant. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/1f.html [23-09-2001 15:58:54]

Structuration des Données Informatiques - 8.2, exercice 4

Exercice suivant

Arbre multiple Question posée à l'examen écrit du 3 juillet 2000 Le langage XML est un langage de balises destiné à succéder au langage HTML. En simplifiant, on peut dire qu'un document XML contient un élément racine. Cet élément racine est un élément complexe, c'est-à-dire qu'il contient un ou plusieurs autres éléments. Chaque élément est soit du texte simple, soit un élément vide composé uniquement d'une balise de la forme "", soit un élément complexe délimité, à son début, par une balise d'ouverture de la forme "", à sa fin, par une balise de fermeture de la forme "" et contenant, entre deux, une succession d'éléments. Un document XML peut être vu comme une structure arborescente du type arbre multiple. En supposant que <X>Y est représenté par

en appliquant cette représentation récursivement et et en tenant compte des différentes possibilités de représenter des arbres multiples, dessinez deux représentations arborescentes différentes pour le document suivant: <article> Un journaliste <souligne>accuse, un policier <souligne>dément Alain Connu 14 juin 1972 banquise Un journaliste de la place accuse les autorités ... Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/2d.html [23-09-2001 15:58:58]

Structuration des Données Informatiques - 9.1, exercice 2

Exercice suivant

Listes Question posée à l'examen du 3 juillet 2000 program SchemeList; { une structure qui peut contenir soit une valeur, soit une paire } type PSchemePaireOuValeur = ^TSchemePaireOuValeur; TSchemePaireOuValeur = record { le record contient-il une valeur } mEstValeur:boolean; {si ce record est une valeur} mValeur : integer; {si ce record est une paire} { car de la paire} mCar : PSchemePaireOuValeur; { cdr de la paire } mCdr : PSchemePaireOuValeur; end; { TSchemePaireOuValeur } var gSchemePaire: PSchemePaireOuValeur; { Une fonction qui cree une valeur } function creeValeur(inValeur : integer): PSchemePaireOuValeur; var lResultat : PSchemePaireOuValeur; begin new(lResultat); lResultat^.mEstValeur:=true; lResultat^.mValeur:=inValeur; lResultat^.mCar:=nil; lResultat^.mCdr:=nil; creeValeur:=lResultat; end; { creeValeur } { Une fonction qui cree une paire } function creePaire(inCar,inCdr: PSchemePaireOuValeur):PSchemePaireOuValeur; var lResultat : PSchemePaireOuValeur; begin new(lResultat); lResultat^.mEstValeur:=false;

http://cuisung.unige.ch/std/ex/9/1b.html (1 of 2) [23-09-2001 15:59:01]

Structuration des Données Informatiques - 9.1, exercice 2

lResultat^.mValeur:=0; lResultat^.mCar:=inCar; lResultat^.mCdr:=inCdr; creePaire:=lResultat; end; { creePaire } { Une procedure pour afficher } procedure display(inPaire : PSchemePaireOuValeur); {vous etes autorise(es) de mettre des variables ici} begin {Mettez votre code ici. Les commentaires du programme principal vous indiquent ce que la procedure Display est censee imprimer} end; begin gSchemePaire:=creePaire(creeValeur(1), creePaire(creeValeur(2), creePaire(creeValeur(3),nil))); display(nil) {donne "()"}; writeln; display(gSchemePaire); {donne "(1 . (2 . (3 . ())))"} gSchemePaire:=creePaire(creePaire(creeValeur(1), creeValeur(2)), creePaire(creeValeur(3), creeValeur(4))); writeln; display(gSchemePaire); {donne "((1.2).(3.4))"} end. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/9/1b.html (2 of 2) [23-09-2001 15:59:01]

Structuration des Données Informatiques - 11. exercice 4

Graphe orienté Question posée à l'examen écrit du 3 juillet 2000 L'on modélise un planning à l'aide des structures suivantes : var Debut: array [1..NbTaches] of Integer; { pour chaque tâche, le jour auquel elle est censée débuter } Duree: array [1..NbTaches] of Integer; { la durée de chaque tâche, en nombre de jours } Avant: array [1..NbTaches,1..NbTaches] of Boolean; { Avant[X,Y] vrai si la tâche X doit être achevée avant le début de Y } Écrire une procédure/fonction étudiant la cohérence de ces données, c.-à-d. : 1. vérifier que chaque tâche peut bien commencer au jour prévu, en tenant compte de la durée de ses antécédentes; 2. si cela n'est pas vérifié, imprimer où se situe l'erreur, et quel est l'enchaînement des tâches précédentes (depuis l'origine) à prendre en compte pour déterminer la date de début correcte ; 3. le cas échéant, proposer des améliorations locales du planning (quand une tâche pourrait commencer plus tôt que prévu). Il n'est pas demandé de modifier les données initiales, ni de réaliser plusieurs passes, chacune tenant compte des corrections ( avancée ou retardement d'une tâche) de la précédente. Toutefois, s'il vous reste du temps, cela pourra constituer un bonus... Attention : il n'est pas spécifié que les tâches doivent s'effectuer l'une après l'autre, certaines peuvent s'accomplir en parallèle. De même, la racine du processus n'est pas nécessairement unique (ni le graphe connexe). NB: Les variables Debut, Duree et Avant sont globales, et peuvent être utilisées comme telles dans votre code. Solution

http://cuisung.unige.ch/std/ex/11/d.html [23-09-2001 15:59:04]

Notes du contrôle continu du 22 juin 2000

Structures de Données

Notes du contrôle continu du 22 juin 2000 Nom

Q1 Q2 Q3 Note

ARRIS Latifa

5

7

5

1,7

BLANC Jérémy

17

18

20

5,5

BOUGET M.

20

20

20

6,0

Répartition des notes

COLA Stéphane

17

11

17

4,5

[5,5-6,0]

xxxxxx

GEROME-BAUQUIS Isis 16

6

8

3,0

[5,0-5,5[

x

HAENGGELI Christophe

17

18

20

5,5

[4,5-5,0[

xxx

HEUBERGER Joris

17

20

19

5,6

HYSI Hilda

17

10

10

3,7

JABRI Abdelmajid

15

2

8

LOGEAY Camille

17

15

POSKRIAKOV Sergei

17

RAY Nicolas

[4,0-4,5[ [3,5-4,0[

x

[3,0-3,5[

xx

2,5

[2,5-3,0[

x

13

4,5

[2,0-2,5[

20

16

5,3

[1,5-2,0[

17

17

11

4,5

[1,0-1,5[

RENQUIN Johan

18

18

20

5,6

SARAZIN Benoît

17

7

8

3,2

YAPY Luis

20

18

14

5,2

Dernière modification: 19.07.00

http://cuisung.unige.ch/std/CC/000622/Notes.html [23-09-2001 15:59:06]

x

Structuration des Données Informatiques - 11.3, exercice 4

Graphes orientés Question posée au contrôle continu du 22 juin 2000 Dessinez la fermeture transitive de chacun de ces quatre graphes:

Solution

http://cuisung.unige.ch/std/ex/11/3d.html [23-09-2001 15:59:13]

Structuration des Données Informatiques - 11. exercice 3

Exercice suivant

Graphe orienté Question posée au contrôle continu du 22 juin 2000 Il est aisément démontrable que lorsque l'on élève un nombre N au carré, les deux derniers chiffres du résultat ne dépendent que des deux derniers chiffres de N. Ainsi, un nombre se terminant par 05 aura toujours son carré se terminant par 25 ( 105->11025, 1905->3629025 ). L'on peut donc définir une application reliant chacun des nombres de 00 à 99 à un autre de ces nombres, correspondant à la valeur de son carré modulo 100. Ceci compose bien entendu un graphe orienté... 1. Considérant que chacun des noeuds est l'origine d'un et un seul arc, déterminez la structure de données la plus simple adaptée à la représentation des arcs de ce graphe. La propriété précédente amène logiquement ceci : puisqu'un noeud a au plus un successeur (en fait, exactement un), l'on peut définir en suivant les arcs (c'est-à-dire en réitérant le calcul) un chemin unique qui en est issu; puisque tous les noeuds ont au moins un successeur, ce chemin aboutit obligatoirement à un cycle (le nombre de noeuds étant limité). L'on aimerait donc associer à chaque noeud la "séquence terminale" (cycle) qui lui correspond. 2. Écrivez une fonction imprimant, pour un noeud passé en paramètre, les noeuds composant le cycle terminal qui lui est associé. Pensez que chaque composante du graphe ne comporte qu'un seul cycle; rappelez-vous qu'un cycle est un cas particulier de composante fortement connexe... Solution Exercice suivant

http://cuisung.unige.ch/std/ex/11/c.html [23-09-2001 15:59:16]

Structuration des Données Informatiques - 14.3, exercice 6

Exercice suivant

B-Arbres Question posée au contrôle continu du 22 juin 2000 Complétez les procédures pour parcourir des B-arbres. NB: Ces procédures sont sensées marcher avec tous les B-arbres possibles! Une solutions qui marche juste avec l'arbre donné dans ce programme n'est pas considérée comme réponse à cette question (0 points). Sont marquées en caractères gras les parties du code qui sont essentielles à l'élaboration de la solution. program b_arbre; const cTaillePage= ...; type PPage = ^TPage; { un element d'une page de b-arbre} TPageElement = record mCle : integer; { Cle } mEnfant : PPage; { Pointeur } end; { une page du b-arbre TPage = record mPremierEnfant mNombreElements mElements end;

= un noeud du b-arbre

}

: PPage;{ Le premier Enfant } : integer; : array[1..cTaillePage] of TPageElement;

var gArbre : PPage; gAuxiliaire : PPage; gTest : boolean; { Initialiser un element de page } procedure initialisePageElement(var outInitialise : TPageElement); begin outInitialise.mCle:=0; outInitialise.mEnfant:=nil; end; { Creer une page vide

http://cuisung.unige.ch/std/ex/14/3f.html (1 of 4) [23-09-2001 15:59:20]

Structuration des Données Informatiques - 14.3, exercice 6

parameter: outNouveauNoeud, la variable qui va contenir la nouvelle page } procedure creePage(var outNouveauNoeud : PPage); var i : integer; begin { creePage } new(outNouveauNoeud); outNouveauNoeud^.mPremierEnfant:=nil; outNouveauNoeud^.mNombreElements:=0; for i:=1 to cTaillePage do initialisePageElement(outNouveauNoeud^.mElements[i]); end; { creePage } { Ajoute une cle a une page existante parametres: inCle : la nouvelle Cle inoutPage : la page a modifier valeur de resultat: true, si la page n'etait pas encore pleine false, si la page etait pleine } function ajouteCleAPage(var inoutPage: TPage; inCle:integer) :boolean; begin if (inoutPage.mNombreElements
Structuration des Données Informatiques - 14.3, exercice 6

inNouveauEnfant; ajouteCleEtPointeurAPage := true; end else ajouteCleEtPointeurAPage := false; end; { ajouteCleEtPointeurAPage } { Ajoute le premier pointeur a la page } function ajoutePremierPointeurAPage(var inoutPage: TPage; inNouveauEnfant: PPage) :boolean; begin inoutPage.mPremierEnfant:=inNouveauEnfant; ajoutePremierPointeurAPage:=true; end; { ajoutePremierPointeurAPage } { Parcourir et afficher a l'ecran } procedure parcourirBArbreEnOrdre(inArbre: PPage ); { ICI VOUS AVEZ LE DROIT DE METTRE DES VARIABLES } var i : integer; begin { parcourirBArbreEnOrdre } {METTEZ VOTRE SOLUTION ICI!} end; { parcourirBArbreEnOrdre } { Parcourir EN ORDRE INVERSE et afficher a l'ecran } procedure parcourirBArbreEnOrdreInverse(inArbre: PPage ); { ICI VOUS AVEZ LE DROIT DE METTRE DES VARIABLES } var i : integer; begin { parcourirBArbreEnOrdreInverse } {METTEZ VOTRE SOLUTION ICI!} end; { parcourirBArbreEnOrdreInverse } begin creePage(gArbre); creePage(gAuxiliaire); gTest:= ajouteCleAPage(gAuxiliaire^,1); gTest:= ajouteCleAPage(gAuxiliaire^,2); http://cuisung.unige.ch/std/ex/14/3f.html (3 of 4) [23-09-2001 15:59:20]

Structuration des Données Informatiques - 14.3, exercice 6

gTest:= ajouteCleAPage(gAuxiliaire^,3); gTest:= ajoutePremierPointeurAPage(gArbre^,gAuxiliaire); creePage(gAuxiliaire); gTest:= ajouteCleAPage(gAuxiliaire^,5); gTest:= ajouteCleAPage(gAuxiliaire^,6); gTest:= ajouteCleAPage(gAuxiliaire^,7); gTest:= ajouteCleEtPointeurAPage(gArbre^, 4, gAuxiliaire); parcourirBArbreEnOrdre(gArbre); { donne 1 2 3 4 5 6 7 } writeln; writeln; parcourirBArbreEnOrdreInverse(gArbre); { donne 7 6 5 4 3 2 1 } writeln; end. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/14/3f.html (4 of 4) [23-09-2001 15:59:20]

Notes du contrôle continu du 11 mai 2000

Structures de Données

Notes du contrôle continu du 11 mai 2000 Nom

Q1 Q2 Q3 Note

ARRIS Latifa

20

16

16

5,2

BEURET Séverine

18

8

9

3,5

BLANC Jérémy

20

19

18

5,7

BOUGET M.

19

15

16

5,0

BRAIK Ahcène

15

4

12

3,1

BUHLER Stéphane

13

13

2

2,8

COLA Stéphane

18

17

15

5,0

CORON Olivier

16

12

13

4,1

Répartition des notes

GEROME-BAUQUIS Isis 17

18

18

5,3

[5,5-6,0]

xxxxx

HABACHI Arash

15

15

16

4,6

[5,0-5,5[

xxxxx

HAENGGELI Ch.

18

18

10

4,6

[4,5-5,0[

xxxxxxx

HEUBERGER Joris

20

19

16

5,5

[4,0-4,5[

xx

[3,5-4,0[

x

[3,0-3,5[

xx xx

HYSI Hilda

18

17

13

4,8

JABRI Abdelmajid

18

13

10

4,1

[2,5-3,0[

JULIEN Etienne

18

14

0

3,2

[2,0-2,5[

LOGEAY Camille

18

13

14

4,5

[1,5-2,0[

LUONG Fayou

20

15

11

4,6

[1,0-1,5[

MADDI Brahim

0

2

8

1,0

PELLEGRINI David

18

10

0

2,8

PETRINI Geo

20

16

15

5,1

POSKRIAKOV Sergei

20

20

19

5,9

http://cuisung.unige.ch/std/CC/000511/Notes.html (1 of 2) [23-09-2001 15:59:23]

x

Notes du contrôle continu du 11 mai 2000

RAY Nicolas

16

16

14

4,6

RENQUIN Johan

20

20

15

5,5

SARAZIN Benoît

17

10

18

4,5

YAPY Luis

20

19

18

5,7

Dernière modification: 20.07.00

http://cuisung.unige.ch/std/CC/000511/Notes.html (2 of 2) [23-09-2001 15:59:23]

Structuration des Données Informatiques - 7.1, exercice 2

Exercice suivant

Chaînes Question posée au contrôle continu du 11 mai 2000 Complétez ce programme pour que toutes les fonctions fassent ce qui est dit dans les commentaires: program chaines; type { un pointeur sur des elements d'une chaine. } PElement = ^TElement; { un element d'une chaine: } TElement = record {chaque element de la chaine contient un entier} mContenu : integer; { mSuivant: pointeur sur l'element suivant de la chaine, nil pour le dernier element } mSuivant : PElement; end; var gChaineDOrigine : PElement; gChaineResultat : PElement; { VOUS ETES AUTORISES A AJOUTER QUELQUES FONCTIONS ICI (Si vous voulez. Ce n'est pas forcement necessaire, mais ca peut ameliorer la lisibilite de votre solution). DES VARIABLES SUPPLEMENTAIRES NE SONT PAS AUTORISEES. } { La fonction suivante prend la chaine inChaine et retourne une nouvelle chaine, qui contient les memes valeurs que inChaine, mais en ordre inverse: Si inChaine est (1 2 3) le resultat va etre la chaine (3 2 1). AUCUNE VALEUR QUI APPARTIENT A INCHAINE NE DOIT ETRE MODIFIEE } function creeChaineInversee(inChaine:PElement):PElement; { VOUS ETES AUTORISES A METTRE DES VARIABLES ICI. http://cuisung.unige.ch/std/ex/7/1b.html (1 of 2) [23-09-2001 15:59:25]

Structuration des Données Informatiques - 7.1, exercice 2

LES TABLEAUX SONT INTERDITS!!!! } begin { VOTRE SOLUTION ICI Mon conseil: Copier la liste d'entree, en ajoutant les nouveaux elements AU DEBUT de la nouvelle liste } end; { creeChaineInversee } begin { VOUS N'ETES PAS AUTORISE A AJOUTER QUOI QUE CE SOIT ICI } new(gChaineDOrigine); gChaineDOrigine^.mContenu:=2; new(gChaineDOrigine^.mSuivant); gChaineDOrigine^.mSuivant^.mContenu:=4; new(gChaineDOrigine^.mSuivant^.mSuivant); gChaineDOrigine^.mSuivant^.mSuivant^.mContenu:=6; gChaineDOrigine^.mSuivant^.mSuivant^.mSuivant:=nil; gChaineResultat:=creeChaineInversee(gChaineDOrigine); writeln('Si toutes ces expressions sont correctes, il est', 'probable que le programme est lui aussi correct'); write('6 = ');writeln(gChaineResultat^.mContenu); write('4 = ');writeln(gChaineResultat^.mSuivant^.mContenu); write('2 = '); writeln(gChaineResultat^.mSuivant^.mSuivant^.mContenu); end. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/1b.html (2 of 2) [23-09-2001 15:59:25]

Structuration des Données Informatiques - 7.1, exercice 3

Chaînes Question posée au contrôle continu du 11 mai 2000 Étant données deux listes chaînées, comportant des entiers rangés selon l'ordre croissant, et définies comme suit: type pElement = ^tElement; tElement = record nombre : integer; suivant : pElement; end; var debut1, debut2 : pElement; Écrivez une fonction qui opèrera une fusion de ces deux chaînes dans une troisième, respectant également l'ordre croissant de ses éléments, en enlevant les doublons. Ainsi, à partir de: liste 1 : 1 3 5 7 9 liste 2 : 1 2 4 7 11 16 l'on doit obtenir: liste 3 : 1 2 3 4 5 7 9 11 16 Solution

http://cuisung.unige.ch/std/ex/7/1c.html [23-09-2001 15:59:27]

Structuration des Données Informatiques - 8.1, exercice 5

Exercice suivant

Arbre de tri Question posée au controle continu du 11 mai 2000 Soit un arbre de tri représenté par la structure suivante: type pNoeud = ^tNoeud; tNoeud = record nombre : integer; gauche, droite : pNoeud; end; var racine : pNoeud; On suppose que la racine est instanciée à un arbre existant. Proposez alors une fonction permettant de vérifier que cet arbre est bien construit, c'est-à-dire que tous les nombres présents dans le sous-arbre gauche (resp. droit) sont inférieurs (resp. supérieurs) au nombre correspondant au noeud courant, et cela à chaque niveau de l'arbre. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/1e.html [23-09-2001 15:59:29]

Structuration des Données Informatiques - 3.1, exercice 1

Tableaux Question posée au contrôle continu du 28 février 2000 program question1; var gHeap : array [1..7] of integer; procedure affiche(inValeurCourant, inValeurFin : integer); begin if (inValeurCourant<=inValeurFin) then begin writeln('a: ',gHeap[inValeurCourant]); affiche(inValeurCourant*2,inValeurFin); writeln('b: ',gHeap[inValeurCourant]); affiche(inValeurCourant*2+1,inValeurFin); writeln('c: ',gHeap[inValeurCourant]); end (* then *) else begin writeln('d: ',inValeurCourant); end; (* if *) end; { affiche } procedure remplir; var i : integer; begin gHeap[1]:=4; gHeap[2]:=2; gHeap[3]:=5; gHeap[4]:=1; gHeap[5]:=3; gHeap[6]:=6; gHeap[7]:=7; gHeap[7]:=8; end; { remplir } begin remplir writeln('----------premiere partie'); affiche(1,1); writeln('----------deuxieme partie'); affiche(1,3); writeln('----------troisieme partie'); affiche(1,5); writeln('----------fin') end. Qu'est-ce que ce programme affiche à l'écran?

http://cuisung.unige.ch/std/ex/3/1a.html [23-09-2001 15:59:31]

Structuration des Données Informatiques - 7.4, exercice 8

Anneaux bidirectionnels Question posée à l'examen écrit du 28 février 2000 Sur la base des déclarations suivantes: type VersAnneau = ^ElementAnneau; ElementAnneau = RECORD Donnee: integer; Preced, Suivant: VersAnneau; END; Ecrivez une procédure Tri(var Anneau: VersAnneau)qui trie par permutation les données d'un anneau bidirectionnel. On supposera que les données sont tellement volumineuses que la permutation se fera en manipulant les pointeurs et non pas en changeant le champ Info. Solution

http://cuisung.unige.ch/std/ex/7/4j.html [23-09-2001 15:59:38]

Structuration des Données Informatiques - 8.3, exercice 2

Arbres dépliables Question posée aux examens écrits du 30 juin 1999 et du 28 février 2000 . Dessiner un arbre dépliable de tri, qui sera construit à partir des mots de la phrase suivante, en traitant les mots en séquence de gauche à droite: John also reviews the use of increasingly important industry specifications and standards in platform or system issues. b. Détruire l'élément qui contient le mot "increasingly" et dessiner l'arbre dépliable résultant. Solution

http://cuisung.unige.ch/std/ex/8/3b.html [23-09-2001 15:59:40]

Structuration des Donn es Informatiques - 14.3, exercice 5

Exercice suivant

B-Arbres Question posée à l'examen du 28 février 2000 Soit un B-arbre construit à partir des déclarations suivantes: const NodeSize = 4; type PNode = ^TNode; TNode = record UsedSize : integer; Content : array [1..NodeSize] of integer; Children : array [0..NodeSize] of PNode; end; (* TNode *) var gRoot : PNode; Ecrivez une procédure "afficher(Root : PNode)" qui écrit le contenu du B-arbre en ordre croissant. solution Exercice suivant

http://cuisung.unige.ch/std/ex/14/3e.html [23-09-2001 15:59:42]

Structuration des Données Informatiques - 7.4, exercice 8

Exercice suivant

Anneaux bidirectionnels Question posée à l'examen écrit du 11 octobre 1999 Etant donné les déclarations suivantes pour un anneau bidirectionnel: type PtrNoeud = ^Noeud; Noeud = RECORD Donnee: integer; Preced, Suivant: PtrNoeud; END; var TeteAnneau: PtrNoeud; (* pointeur vers premier element *) 1. Ecrire une procédure InsereFin(Anneau, Donnee) pour insérer une donnée à la fin de l'anneau 2. Ecrire une fonction NbElem(Anneau), qui retourne un entier, pour compter le nombre d'éléments de l'anneau 3. Ecrire une procédure Split(Ring, Data, LowerRing, HigherRing), qui prend les données contenues dans le premier paramètre (anneau) pour les recopier dans le troisième ou le quatrième paramètre (eux aussi des anneaux) suivant que ces données sont respectivement soit inférieures, soit supérieures ou égales à la donnée passée en second paramètre. N.B.: à chaque fois, vous devez envisager tous les cas possibles Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4i.html [23-09-2001 15:59:44]

Structuration des Données Informatiques - 8.1, exercice 4

Exercice suivant

Arbre syntaxique Question posée à l'examen du 11 octobre 1999 En supposantque l'on dispose des fonctions suivantes pour contruire une structure d'arbre: type PtrNoeud: ^Noeud; function Feuille(Contenu: char): PtrNoeud; { crée par allocation dynamique un noeud sans descendant et contenant un caractère } function Arbre(ContenuRacine:char; Gauche, Droit: PtrNoeud): PtrNoeud; { crée, par allocation dynamique, un nouveau noeud racine auquel seront rattachés les sous-arbres gauche et droit fournis en paramêtre, de façon à former un nouvel arbre } 1. Quelle sera l'expression, composée d'appels imbriqués aux fonctions Arbre et Feuille, qui permettra de construire, en une seule instruction Pascal, l'arbre suivant:

2. Si, au lieu de créer une structure dynamique en mémoire, on voulait directement évaluer l'expression arithmétique représentée par l'expression Pascal de la première partie de cette question, quel devrait être l'entête et le code des fonctions Feuille et Arbre, en supposant qu'elles retournent des valeurs entières N.B.: on suppose que les opérateurs + et - peuvent être utilisés comme opérateurs monadiques, c'est-à-dire ne portant que sur un seul argument (opérateurs de signe). Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/1d.html [23-09-2001 15:59:49]

Structuration des Données Informatiques - 9.1, exercice 1

Exercice suivant

Listes Question posée à l'examen du 11 octobre 1999 Indiquez ligne après ligne ce qu'imprime le programme suivant: program listes; var gDe,gA:integer; procedure compter1(inDe,inA : integer); begin if(inDe
Structuration des Données Informatiques - 9.1, exercice 1

gDe:=1; gA:=4; writeln('Avant compter1'); compter1(gDe,gA); gDe:=1; gA:=4; writeln('Avant compter2'); compter2(gDe,gA); gDe:=1; gA:=4; writeln('Avant compter3'); compter3(gDe,gA); gDe:=1; gA:=4; writeln('Avant compter4'); compter4(gDe,gA); end. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/9/1a.html (2 of 2) [23-09-2001 15:59:52]

Structuration des Données Informatiques - 11. exercice 2

Exercice suivant

Le chemin le plus court Question posée à l'examen écrit du 11 octobre 1999 Soit un graphe avec 4 noeuds (1,2,3,4), avec des arcs pondérés: Les arcs sont: Départ Arrivée Distance 1

2

1

2

3

1

3

4

1

1

3

10

2

4

100

4

3

1000

Pour trouver les "distances" correspondant aux chemins les plus courts entre le noeud 1 et tous les autres noeuds, exécutez l'algorithme suivant: 1. Soit une liste L et une liste A, toutes deux initialement vides. 2. Ajoutez à la liste L la paire (1;0) pour le noeud 1 et la "distance" 0. Ajoutez pour chaque arc qui lie les noeuds x et y avec une "distance" z le triplet (x;y;z) à la liste A. 3. Retirez la paire (x;y) avec le deuxième élément (y) le plus petit de la liste L. 4. Pour chaque paire (x;y) avec le deuxième élément (y) le plus petit de la liste L, retiré à l'étape 3, faites ce qui suit: ❍ Pour chaque arc (x,a,b) qui lie le noeud x à a avec une distance b ajoutez la paire (a;y+b) à la liste L. ❍ Retirez (x,a,b) de A 5. Pour chaque paire (x;y) dans L: S'il existe une paire (x;z) dans L avec z plus petit ou égal à y effacez (x;y) de L. 6. Continuez en 3 tant qu'il y a encore des éléments dans A Donnez le contenu de A et de L après chaque pas. Exercice suivant

http://cuisung.unige.ch/std/ex/11/b.html [23-09-2001 15:59:54]

Notes de l'examen du 30 juin 1999

Structures de données Notes de l'examen du 30 juin 1999 Nom

Note

Remarque

Tiana Andriaharifara

0,0 absente

Patrick Arbus

0,5

José Barba

3,0

Ahcene Braik

2,0

Denis Bucher

4,5 note en attente des TPs

Hechmi Chnina

0,5

Baba Diao

0,0 absent

Yves Fomekong

3,5

Mouhamed Gningue

3,0

Nicolas Hurzeler

1,0

Sylvan Laurence

1,0

Thomas Pfund

4,0 note en attente des TPs

Bruno Rosa Martins

5,0

Cengiz Ulkü

0,5

N.B.: les notes du contrôle continu sont aussi disponibles

http://cuisung.unige.ch/std/Exa/Notes990630.html [23-09-2001 15:59:56]

Structuration des Données Informatiques - 7.4, exercice 7

Exercice suivant

Anneaux bidirectionnels Question posée à l'examen écrit du 30 juin 1999 Sur la base des déclarations suivantes: type VersAnneau = ^ElementAnneau; ElementAnneau = record Info: ...; Precedent, Suivant: VersAnneau; end; { ElementAnneau } 1. écrivez une fonction Pascal Inverse qui prend en paramètre un anneau bidirectionnel et retourne comme résultat un pointeur vers un autre anneau qui a les mêmes éléments que le paramètre, mais dans l'ordre inverse: function Inverse(Ring: VersAnneau): VersAnneau; 2. écrivez une fonction Pascal EstInverse qui prend en paramètres deux anneaux bidirectionnels et qui indique s'ils sont l'inverse l'un de l'autre: function estInverse(Ring1, Ring2: VersAnneau): boolean; Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4h.html [23-09-2001 15:59:59]

Structuration des Données Informatiques - 11. exercice 1

Exercice suivant

Le chemin le plus court Question posée l'examen écrit du 30 juin 1999 Imaginez un graphe orienté qui est donné par sa matrice de connectivité: sommets d'arrivée 1 1 2 sommets 3 de 4 départ 5 6

2

3

x

4

5

6

7

x x x x x x

7 . Dessinez ce graphe b. Trouvez maintenant le chemin le plus court entre les noeuds 1 et 6. Pour ça vous avez besoin d'une file d'attente FIFO permettant de stocker des chaînes Li. Chaque Li=(Vi,1,...,Vi,n_i) contient une séquence de sommets. L'algorithme à utiliser pour trouver le chemin le plus court entre deux noeuds Vs et Vf est le suivant: 1. Videz la FIFO 2. Insérez la liste (Vs) dans la FIFO. 3. Tirez la première liste de la FIFO. Appelez cet élément L1 4. Si le premier noeud V1,1 contenu dans L1 est égal à Vf, affichez L1 de la fin au début: La séquence dans L1 est un chemin de longueur minimale entre Vs et Vf (il peut y en avoir plusieurs). L'algorithme est terminé. 5. Sinon (le premier noeud V1,1 contenu en L1 n'est pas égal à Vf): visitez V1,1 de la façon suivante: Ajoutez pour chaque voisin v de V1,1 la liste résultant de (cons v L1) . 6. Continuez avec le pas 3, tant que la FIFO n'est pas vide et le chemin le plus court n'a pas été trouvé au pas 4. Les limitations de cet algorithme sont claires. Il doit être possible d'atteindre Vf a partir de Vs. La solution doit donner le contenu de la FIFO à chaque étape de l'algorithme! Solution Exercice suivant

http://cuisung.unige.ch/std/ex/11/a.html [23-09-2001 16:00:01]

Structuration des Donn es Informatiques - 13.4, exercice 3

Adressage associatif par transformation de clés (Hash-code) Question posée à l'examen écrit du 30 juin 1999 . Etant donné le programme en Pascal suivant: program fabrique_fonction_de_H_code_parfaite; const TailleMax MaxIndice NbMots MaxCoeff LongueurMax

= = = = =

...; { taille maximale de la table } TailleMax-1; { indice maximal dans la table } ...; { nombre de mots a stocker } ...; { valeur max pour les coefficients } ...; { longueur max. des mots du vocabulaire}

type StringMax = string[LongueurMax]; var Taille : integer; {Nombre d'éléments utilisables dans la table} T : array[0..MaxIndice] of StringMax; Coeff : array[1..LongueurMax] of 1..MaxCoeff; { coefficients de la fonction H } Vocabulaire : array[1..NbMots] of StringMax; function H( Mot : StringMax ) : integer; begin H := 0; for i := 1 to Length(Mot) do H := H + Coeff[i] * ord( Mot[i] ); H := H mod Taille end; { H } procedure ChercheCoefficients; begin { ChercheCoefficients } { ajustement des coefficients Coeff[i] et Taille } ... end; { ChercheCoefficients } begin { fabrique_fonction_de_H_code_parfaite } ChercheCoefficients; end. { fabrique_fonction_de_H_code_parfaite } Ecrire la procédure 'ChercheCoefficients', permettant de fixer les coefficients ( Coeff[i] et 'Taille' ) de la fonction de H-code, afin qu'elle soit parfaite pour le remplissage du tableau avec les mots du 'Vocabulaire'. La solution doit impérativement minimiser le paramètre 'Taille'. Idéalement, la taille du tableau serait égale au nombre de mots. Il est conseillé d'utiliser la force brute pour résoudre ce problème. Il s'agira donc de tester toutes les valeurs possibles pour les coefficients, jusqu'à tomber sur une fonction de H-code parfaite, ou que l'espace des possibilités soit épuisé. http://cuisung.unige.ch/std/ex/13/4c.html (1 of 2) [23-09-2001 16:00:05]

Structuration des Donn es Informatiques - 13.4, exercice 3

b. Le but de cette question est d'essayer de minimiser le nombre de collisions dans une structure de données remplie à l'aide de l'algorithme de H-code. Nous avons: ❍ un tableau de strings appelé T, dont les éléments T[i] sont initialisés à '' (string vide) ❍ une fonction H(X) retournant l'indice dans le tableau T où l'élément X devrait être stocké. ❍ une fonction P(X) retournant la probabilité d'apparition de l'élément X sur l'ensemble des données traitées. L'optimisation proposée est la suivante : Lors de l'insertion d'un mot X, si l'emplacement T[H(X)] est déjà occupé, le nouveau mot X aura la priorité si sa probabilité est plus élevée que celle du mot dans l'emplacement occupé. Pour sa réalisation, il suffira de compléter la procédure ci-dessous, déjà vue au cours. function Insert( X : string ) : integer; var H0, hi : integer; begin H0 := H(X); hi := H0; while ( T[hi] <> '' ) and ( T[hi] <> X ) do begin {

Ajouter ici le code de l'optimisation }

hi := (hi+1) mod MaxElements; if hi = H0 then begin writeln('tableau plein'); exit(program); end; { if } end; { while } if T[Hi] = '' then T[Hi] := X; Insert := hi; end; { Insert } Solution

http://cuisung.unige.ch/std/ex/13/4c.html (2 of 2) [23-09-2001 16:00:05]

Notes du contrôle continu du 14 juin 1999

Notes du contrôle continu du 14 juin 1999 Nom Roberto Campelo

Q1 Q2 Q3 Note 8

5

0

1,3

Frederic Ehrler

14

20

10

4,4

Christiane James

12

12

20

4,4

Dimitri Kalas

17

18

16

5,1

Julie Lutz

17

12

16

4,5

9

10

16

3,5

Alexandre Nevski

http://cuisung.unige.ch/std/CC/990614/Notes.html [23-09-2001 16:00:11]

Structuration des Donn es Informatiques - 11.3, exercice 3

exercice suivant

Graphes orientés Question posée au contrôle continu du 14 juin 1999 Soit un graphe défini sur la base des relations de dépendances suivantes concernant les ages respectifs d'un groupe de personnes: ● Jean est plus jeune que Paul et Pierre, mais plus agé que Jeanne. ● Jacques est plus jeune que Jeanne et Pierre, mais plus vieux que Marie ● Pierre est plus jeune que Paul, mais plus vieux qu'André et Alice ● Yves est plus jeune que Paul, mais plus vieux que Claude et Alice ● Claude est plus jeune que Pierre et plus vieux qu'André . dessinez le graphe en question b. donnez la matrice de connectivité de ce graphe c. donnez la matrice de connectivité de la fermeture transitive de ce graphe indiquez à quel type de question la fermeture transitive permet de répondre plus facilement d. donnez une séquence de sommets correspondant à un tri topologique, indiquez s'il existe une autre solution possible (si oui, proposez en une). Solution exercice suivant

http://cuisung.unige.ch/std/ex/11/3c.html [23-09-2001 16:00:13]

Structuration des Donn es Informatiques - 14.3, exercice 4

Exercice suivant

B-Arbres Question posée au contrôle continu du 14 juin 1999 Soit un B-Arbre d'ordre 1, c'est-à-dire que chaque page peut avoir soit 1 soit 2 données. . Insertion: Insérez dans l'ordre indiqué les nombres: 1,2,3,6,7,4,5,8,9 dans le B-arbre et dessinez après chaque insertion le B-arbre résultant. b. Complexité d'espace: En supposant que chaque page occupe 512 octets (2 octets pour le nombre de données dans la page, 4 octets par "pointeur" vers une autre page et 249 octets par donnée), indiquez l'espace minimum et maximum nécessaires pour stocker 10'000 données dans ce B-arbre d'ordre 1. c. Profondeur: Quelle profondeur minimum et maximum aura le B-arbre avec 10'000 données. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/14/3d.html [23-09-2001 16:00:15]

Structuration des Donn es Informatiques - 13.4, exercice 2

exercice suivant

Adressage associatif par transformation de clés (Hash-code) Question posée au contrôle continu du 14 juin 1999 Soit une fonction H qui retourne les valeurs numériques suivantes pour les mots suivants: mot: du esprit etait forte illumination jour la lumiere qu si son soudaine traversa une H(mot): 6 13 3 12 9 10 7 15 5 6 5 8 10 2 On décide de placer ces mots dans un tableau de 15 positions (indices 1..15) par la méthode de l'adresse ouvert, en utilisant l'expression suivante pour traiter les collisions: Hi(K) = [(H(K) + i*length(K)) mod 15] + 1, où i représente le nombre de collisions déjà subies lors de l'insertion de K (i = 0 au début) et length(K) est la fonction qui retourne le nombre de caractères d'un mot. N.B.: Au cas où on essaye de placer un nouveau mot dans une position occupée par un mot ayant lui-même été déplacé, on donnera la priorité au nouveau mot. Dessinez le tableau résultant de l'insertion des mots énumérés ci-dessus en les prenant dans l'ordre où ils sont écrits. Solution exercice suivant

http://cuisung.unige.ch/std/ex/13/4b.html [23-09-2001 16:00:18]

Contrôle Continu de Structures de Données du 29 avril 1999

Université de Genève Faculté des Sciences Département d'Informatique

29 avril 1999

Structures de Données Contrôle Continu - Première épreuve Rappel: Ce contrôle continu est un examen. Vous n'êtes donc pas autorisés à communiquer avec d'autres personnes par quelque moyen que ce soit (communication verbale, par support papier ou électronique, courrier électronique, Web, espace disque), à l'exception des assistants chargé de la surveillance de cet examen. Une vérifications des "logs" des serveurs Web, proxy et courrier électronique peut être effectuée pour déterminer si quelqu'un a contrevenu à cette interdiction. Toute tricherie sera sanctionnée par une note de 0 à l'examen final pour tous les contrevenants. Vous êtes par contre autorisés à consulter toute la documentation que vous désirez, que ce soit le livre du cours ou d'autres livres, vos notes personnelles, le site Web du cours (y compris les anciennes questions d'examens et leurs corrigés), ou même des fichiers vous appartenant.

Comment rendre vos réponses aux questions: Les questions portent sur des exercices de programmation. Vos réponses vont donc consister en du code Pascal complétant des programmes qui vous seront fournis. Vous devez rendre vos réponses sur une disquette portant une étiquette sur laquelle votre nom est clairement inscrit. Ces disquettes vous seront rendues par la suite. Si pour une raison quelconque, vous vous trouviez dans l'impossibilité de rendre une disquette, vous devez laisser une copie des fichiers contenant vos réponses dans votre espace disque personnel, en indiquant à au moins un assistant le problème que vous avez rencontré et en lui expliquant où se trouvent vos réponses.

Recommandation: Si vous n'arrivez pas à faire correctement fonctionner votre code pour une des deux questions, ne restez pas bloqués dessus plus de deux heures pour avoir le temps de traiter l'autre question.

http://cuisung.unige.ch/std/CC/990429/ (1 of 4) [23-09-2001 16:00:26]

Contrôle Continu de Structures de Données du 29 avril 1999

Questions Question 1 Description Ici vous trouvez le fichier qui contient un programme en Pascal. Ce programme traite des chaînes bidirectionelles qui ont deux bouts facilement accessibles. Pour l'acces, c'est a dire l'ajout et la suppression des elements et pour la construction et destruction des listes tout les fonctions necessaires sont fournies avec les commentaires. Lisez et comprenez ces procedures. C'est nécessaire pour le reste de cette question.

Question: Completez maintenant les fonctions et procedures suivantes: Cette fonction verifie si une chaine est un palindrome, c'est a dire si le n-ième element est egale au (n-1)-avant-dernier-element Cette fonction genère une nouvelle chaîne qui est exactement la newReverse_Chaine chaîne d'entrène lu a'l envers. Cette fonction ajoute une chaine (deuxième paramètre) a la fin d'une autre (premier paramètre). La chaîne qui était donée comme ajouteApresChaine_Chaine premier paramètre est entierement vide apres exécution de cette fonction. estPalindrome_Chaine

Conseil: Lisez et comprenez vraiment les procédures données. Sinon la question devient beaucoup plus difficile.

Question 2: arbre lexicographique On a construit un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de façon que les chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante:

http://cuisung.unige.ch/std/CC/990429/ (2 of 4) [23-09-2001 16:00:26]

Contrôle Continu de Structures de Données du 29 avril 1999

Les arcs sont étiquettés avec les lettres de l'alphabet (on suppose ici que l'on ne tient pas compte des accents sur les lettres) et les noeuds contiennent un booléen indiquant si le chemin de la racine à ce noeud représente un mot complet ou pas (sur le dessin - = faux et * = vrai). Sur la base des déclarations suivantes, écrivez une fonction Lecture qui construira la structure de dictionnaire à partir d'un fichier Text où les mots sont fournis, un par ligne, et une fonction NbMots comptant les mots du dictionnaire ayant une longueur donnée. Si la longueur est 0, il faut retourner le nombre total de mots, quelle que soit leur longueur. type VersNoeud= ^Noeud; Noeud= record Desc: array['a'..'z'] of VersNoeud; Complet: boolean; end; { Noeud } var Dico: VersNoeud; function Lecture(NomFichier: string): VersNoeud; (* cette fonction doit lire les mots du dictionnaire dans un fichier et construire la structure d'arbre au fur et a mesure de la lecture des mots *) function NbMots(Longueur: integer; Dico: VersNoeud):integer; (* cette fonction doit retourner le nombre de mots contenus dans le dictionnaire, dont le nombre de lettres=Longueur *) Fournis: ● programme avec function PseudoLecture: VersNoeud; ●

jeu de données de test

Indication: Nous vous recommandons de commencer par la fonction NbMots, en invoquant la fonction "PseudoLecture" fournie, à la place de la fonction Lecture qui vous est demandée. Lorsque la fonction NbMots sera au point et si vous en avez encore le temps, vous pourrez essayer de remplacer l'appel à la fonction PseudoLecture par un appel à la fonction Lecture que vous aurez écrite. Solution

http://cuisung.unige.ch/std/CC/990429/ (3 of 4) [23-09-2001 16:00:26]

Contrôle Continu de Structures de Données du 29 avril 1999

Questions? Wolfgang Müller, Jean-Marc Küffer, Hidenori Yoshizumi, José Bernardo, Bertrand Ibrahim ou plutôt oralement Quelques photos sont disponibles, ainsi que le résultat de l'évaluation

http://cuisung.unige.ch/std/CC/990429/ (4 of 4) [23-09-2001 16:00:26]

Notes du contrôle continu du 29 avril 1999

Notes du contrôle continu du 29 avril 1999 Nom

Q1 Q2 Note

Tiana Andriharifara

18

1

1,9

Patrick Arbus

10

0

1,0

8

0

0,8

Roberto Campelo

27

5

3,2

Frederic Ehrler

24

3

2,7

Yves Fomekong

17

0

1,7

Chnina Hechmi

0

0

0

Nicolas Hurzeler

0

0

0

Christiane James

17

0

1,7

Dimitri Kalas

27

20

4,7

Sylvain Laurence

24

3

2,7

Julie Lutz

21

20

4,1

Bruno Martins

22

5

2,7

Alexandre Nevski

29

20

4,9

Jose Barba

http://cuisung.unige.ch/std/CC/990429/Notes.html [23-09-2001 16:00:29]

Structuration des Données Informatiques - 11.5, exercice 2

Tri topologique inverse Question posée à l'examen du 7 octobre 1998 En s'inspirant de la description de graphes orientés en termes de type abstrait vue au cours, nous allons supposer que les types "Graphe" et "SerieDeSommets" ont été définis, sans que vous ne connaissiez les détails de ces structures. Nous allons aussi supposer que les primitives suivantes sont à votre disposition: function Index(NomSommet: string; LeGraphe: Graphe): integer; { retourne un numero compris entre 1 et MaxNbSommets } function NomSommet(IndexSommet: integer; LeGraphe: Graphe) :string; { retourne le nom du sommet dont l'index est fourni } function NombreDeSommets(LeGraphe: Graphe): integer; {retourne le nombre de sommets effectifs composant le graphe} function SommetsVoisins(IndexSommet: integer; LeGraphe: Graphe): SerieDeSommets; { retourne une structure permettant de retrouver l'index des voisins immédiats } function ExtraitSommet(var UneSerie: SerieDeSommets): integer; { extrait un sommets de la série et retourne son index } function FinDeSerie(UneSerie: SerieDeSommets): boolean; { vrai s'il n'y a plus de sommet suivant dans la serie } En utilisant ces primitives, tout en ignorant de quelle façon la structure de graphe est implantée, écrivez une procédure de tri topologique inverse qui imprime les sommets du graphe fourni en paramêtre: TriTopologiqueInverse(LeGraphe: Graphe) Solution

http://cuisung.unige.ch/std/ex/11/5b.html [23-09-2001 16:00:31]

Structuration des Données Informatiques - 14.3, exercice 2

Exercice suivant

Comparaison de B-arbres et B*-arbres Question posée à l'écrit du 7 octobre 1998 Rappel: un B*-arbre est une variante de B-arbre dans laquelle les pages (à l'exception de la racine) sont maintenues au moins au deux tiers pleines Soit un ensemble d'un million de données occupant chacune 47 octets. En supposant que l'on utilise des pages de 1024 octets et des références occupant 4 octets, effectuez les calculs suivants pour le cas où on construit un B-arbre et le cas où on construit un B*-arbre. Expliquez à chaque fois votre raisonnement pour arriver aux résultats que vous fournissez. . ordre du B-arbre et du B*-arbre b. taille minimale et maximale de l'espace disque occupé c. profondeur minimale et maximale de la structure Solution Exercice suivant

http://cuisung.unige.ch/std/ex/14/3c.html [23-09-2001 16:00:33]

Structuration des Données Informatiques - 8.3, exercice 1

Exercice suivant

Arbres dépliables Question posée à l'examen écrit du 25 juin 1998 . Dessiner un arbre dépliable de tri, qui sera construit à partir des mots suivants, en prenant la séquence de gauche à droite : la, lumiere, du, jour, etait, si, forte, qu, une, illumination, soudaine, traversa, son, esprit. b. Détruire l'élément qui se trouve à la racine et dessiner l'arbre dépliable résultant. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/3a.html [23-09-2001 16:00:35]

solution de l'exercice 2, sectionn 15.1

Tables de décision question posée à l'examen écrit du 25 juin 1998 Avec les déclarations suivantes définissant une table de décision ainsi qu'un arbre binaire ordonné, écrivez une fonction «ConstruitArbre» qui convertisse une table de décision condensée (paramètre d'entrée) en arbre binairee (paramètre de sortie) où les feuilles contiennent les indicateurs d'actions d'une règle et les noeuds intermédiaires contiennent le texte des conditions de façon que l'arborescence permette de sélectionner la règle qui s'appliquera à un cas donné. Indication: il faut s'inspirer de l'algorithme de conversion d'une table de décision en cascade de tests, mais construire une structure d'arbre au lieu de produire du code Pascal. const MaxNbCond = ...; MaxNbRegles = ...; MaxNbActions = ...; type Conditions =(Vrai, Faux, Indetermine); TableDecision = record NbConditions: 1..MaxNbCond; NbRegles: 1..MaxNbRegles; ValCond: array[1..MaxNbRegles, 1..MaxNbCond] of Conditions; NbActions: 1..MaxNbActions; Agir: array[1..MaxNbRegles, 1..MaxNbActions] of boolean; TxtConditions:array[1..MaxNbCond] of string[30]; TxtActions:array[1..MaxNbActions] of string[30]; end; { TableDecision } PtrNoeud: ^Noeud; Noeud = record case Feuille: boolean of false: (TxtCond: string[30]; Vrai, Faux: PtrNoeud); true: (Actions: array[1..MaxNbActions] of boolean); end; { Noeud } function ConstruitArbre(Table: TableDecision): PtrNoeud; solution

http://cuisung.unige.ch/std/ex/15/1b.html [23-09-2001 16:00:38]

Structuration des Données Informatiques - 14.2, exercice 2

Fichiers séquentiels indexés Question posée au contrôle continu du 15 juin 1998 Soit une structure de fichier séquentiel indexé contenant des données occupant chacune 80 octets, dont 8 octets contiennent la clé d'accès. 1.a) Quelle taille minimale de bloc de données permet d'éviter d'avoir de l'espace disque inutilisé dans le fichier? (en supposant des pages qui sont des multiples de 512 octets) 1.b) Combien de données par bloc cela représente-t-il? Si l'on prend la taille que vous avez trouvé en 1.a) aussi bien pour les blocs de données que pour les blocs d'index et si l'on suppose qu'une référence d'un bloc d'index vers un autre bloc (d'index ou de données) occupe 4 octets, 1.c) Combien de données par bloc faudrait-il mettre pour atteindre un taux de remplissage d'environ 80%? 1.d) Quelle place disque occupera le fichier lorsqu'il contiendra 100'000 éléments si on remplit les blocs de données à ~80%? 1.e) Indiquez aussi la profondeur de l'arborescence d'index, 1.f) le nombre de blocs d'index à chaque niveau de l'arborescence ainsi que 1.g) le nombre total de blocs de données. Solution

http://cuisung.unige.ch/std/ex/14/2b.html [23-09-2001 16:00:40]

Structuration des Données Informatiques - 14.3, exercice 7

Exercice suivant

Recherche B-Arbre Question posée au contrôle continu du 15 juin 1998 Soit le B-Arbre d'ordre 1 suivant.

2.a) Dessinez le B-arbre résultant de l'insertion de la valeur L dans le B-arbre ci-dessus. 2.b) Dessinez le B-arbre résultant de la suppression de la valeur C dans le B-arbre ci-dessus. 2.c) Dessinez le B-arbre résultant de l'insertion de la valeur Z dans le B-arbre ci-dessus. 2.d) Dessinez le B-arbre résultant de la suppression de la valeur S dans le B-arbre ci-dessus. 2.e) Dessinez le B-arbre résultant de la suppression de la valeur P dans le B-arbre ci-dessus. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/14/3g.html [23-09-2001 16:01:23]

Structuration des Données Informatiques - 10.3, exercice 2

Le chemin du moindre coût Question posée au contrôle continu du 15 juin 1998 1997 Un concurrent d'un cross-country doit traverser un terrain difficile du point A au point B. Avant la course, il veut choisir le chemin à suivre. Il a une carte du terrain:

La légende montre les types de terrains, et un nombre associé à chaque type qui indique la difficulté de sa traversée. D'une case de la carte on ne peut accéder qu'à ses quatre voisines au nord, au sud, à l'est et à l'ouest (le déplacement en diagonale est interdit). Le concurrent est équipé d'un ordinateur, dans lequel la carte peut être stockée. On vous a demandé de participer à l'écriture d'un programme qui lui permette de trouver le meilleur chemin dans cette situation, c'est-à-dire le chemin du moindre coût. 3.a) Comment représenteriez-vous l'ensemble des données fournies par la carte en utilisant un graphe? (Donnez juste une courte explication - ne dessinez pas le graphe entier.) 3.b) Quelle(s) structure(s) de données serait la(les) plus efficace(s) pour stocker les noeuds et arcs d'un tel graphe? Ecrivez les déclarations Pascal qui définissent la(les) structure(s) que vous proposez. 3.c) Quel algorithme de recherche utiliseriez-vous pour trouver le chemin le moins coûteux entre les points A et B? Justifier votre réponse, en considérant d'autres algorithmes possibles. 3.d) Ecrivez une description précise, en pseudo-code, de l'algorithme de recherche choisi. http://cuisung.unige.ch/std/ex/10/3b.html (1 of 2) [23-09-2001 16:02:07]

Structuration des Données Informatiques - 10.3, exercice 2

Solution

http://cuisung.unige.ch/std/ex/10/3b.html (2 of 2) [23-09-2001 16:02:07]

Structuration des Données Informatiques - 7.4, exercice 6

Exercice suivant

Chaînes bidirectionnelles Question posée au contrôle continu du 4 mai 1998 Supposons qu'un programme d'édition de texte utilise la structure de chaîne de strings suivante pour représenter le texte en cours d'édition: type VersLigne = ^UneLigne; UneLigne = record Texte: string; LignePrecedente, LigneSuivante: VersLigne; end; { UneLigne } var LeTexte: VersLigne; Ecrivez une procédure "Paragraphes", selon les déclarations suivantes, qui parcourt la structure de donnée pour détermine où se trouvent les paragraphes du texte (les paragraphes sont composés de une ou plusieurs lignes non vides séparées par une ou plusieurs lignes vides). Le résultat sera fourni comme une chaîne bidirectionnelle de descripteurs de paragraphes (type Para). Prenez bien soin à traiter tous les cas particuliers qui peuvent survenir type PtrPara: ^Para; Para = record Debut, Fin: integer; Preced, Suivant: PtrPara; end; { Para } procedure Paragraphes(UnTexte: VersLigne; var ChainePara: PtrPara); Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4f.html [23-09-2001 16:02:09]

Structuration des Données Informatiques - 7.1, exercice 1

Exercice suivant

Chaînes mono-directionnelles Question posée au contrôle continu du 4 mai 1998 Compléter le programme suivant en donnant le corps des procédures Insertion et Afficher, étant donnée la structure de données citée par la suite N.B. On conserve dans un tableau TabElement des chaînes avec leur taille respective. Program Chaines; {Programme qui permet d'affecter des valeurs aux chaînes qui se trouvent dans un tableau et d'afficher le contenu de ce tableau} CONST MaxNbSommets = ...; MaxNumChaine = ...; TYPE PtrNoeud = ^Noeud; Noeud = RECORD Donnee: integer; Suivant: PtrNoeud; END; EltNoeud = RECORD Taillechaine: Integer; Chaine: PtrNoeud; END; VAR TabElement: ARRAY[1..MaxNumChaine] OF EltNoeud; Procedure Insertion(Valeur, NumChaine : integer); {Procédure permettant d'insérer une valeur à la fin de la NumChaine-ème chaîne} Procedure Afficher; {Procédure permettant d'afficher le contenu du champs "Donnee" pour toutes les chaînes du tableau} Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/1a.html [23-09-2001 16:02:12]

Structuration des Données Informatiques - 7.4, exercice 6

Exercice suivant

Anneaux bidirectionnels Question posée au contrôle continu du 4 mai 1998 Avec les déclarations suivantes définissant un anneau bidirectionnel, on aimerait ranger une valeur dans l'anneau où les données sont triées dans l'ordre croissant. Pour ce faire, écrire d'abord la procédure d'insertion ChercherInsertion, qui permet de déterminer le noeud d'insertion pour une valeur donnée. Puis écrire la procédure RangerValeur, qui fait appel à ChercherInsertion pour trouver où insérer la nouvelle valeur et fait l'insertion proprement dite à l'aide de la procédure InsererNoeud que nous supposerons déjà exister. N.B. On suppose que le code de la procédure InsererNoeud est déjà fourni. TYPE PtrNoeud = ^Noeud; Noeud = RECORD Donnee : integer; Precedent, Suivant: PtrNoeud; END; VAR Entete : PtrNoeud; AnneauVide : boolean;

{Entête pour l'anneau} {Indicateur d'anneau vide}

Procedure InsererNoeud(var NPtr,TPtr : PtrNoeud); {Insère le Noeud NPtr après TPtr Vous n'avez pas besoin d'écrire le code de cette procédure} Procedure ChercherInsertion(Valeur: Integer; VAR NoeudInsertion: PtrNoeud); {Permet de déterminer le noeud d'insertion pour la valeur donnée. ChercherInsertion retourne, dans NoeudInsertion, un pointeur vers le plus grand élément encore inférieur à la valeur passée en paramètre, ou NIL, si Valeur existe déjà dans l'anneau. } Procedure RangerValeur(Valeur: Integer); {Permet de ranger une valeur donnée dans l'anneau trié } Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4g.html [23-09-2001 16:02:18]

Structuration des Données Informatiques - 8.1, exercice 3

Exercice suivant

Arbre syntaxique Question posée au contrôle continu du 4 mai 1998 En supposantque l'on dispose des fonctions suivantes pour contruire une structure d'arbre: type PtrNoeud: ^Noeud; function Feuille(Contenu: char): PtrNoeud; { crée par allocation dynamique un noeud sans descendant et contenant un caractère } function Arbre(ContenuRacine:char; Gauche, Droit: PtrNoeud): PtrNoeud; { crée, par allocation dynamique, un nouveau noeud racine auquel seront rattachés les sous-arbres gauche et droit fournis en paramêtre, de façon à former un nouvel arbre } . Quelle sera l'expression qui permettra de construire, en une seule instruction Pascal, l'arbre suivant:

b. Donnez une déclaration possible pour le type Noeud ainsi que le code des deux fonctions Feuille et Arbre. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/1c.html [23-09-2001 16:02:23]

Structuration des Données Informatiques - 10.3, exercice 1

exercice suivant

Structures de graphes Question posée à l'examen écrit du 13 octobre 1997 En s'inspirant de la description de graphes non-orientés en termes de type abstrait vue au cours, nous allons supposer que les types "Graphe" et "SerieDeSommets" ont été définis, sans que vous ne connaissiez les détails de ces structures. Nous allons aussi supposer que les primitives suivantes sont à votre disposition: function Index(NomSommet: string; LeGraphe: Graphe): integer; { retourne un numero compris entre 1 et MaxNbSommets } function NomSommet(IndexSommet: integer; LeGraphe: Graphe) :string; { retourne le nom du sommet dont l'index est fourni } function NombreDeSommets(LeGraphe: Graphe): integer; {retourne le nombre de sommets effectifs composant le graphe} function SommetsVoisins(IndexSommet: integer; LeGraphe: Graphe): SerieDeSommets; { retourne une structure permettant de retrouver l'index des voisins immédiats } function PremierSommet(var UneSerie: SerieDeSommets): integer; { extrait le premier des sommets de la série et retourne son index } function SommetSuivant(var UneSerie: SerieDeSommets): integer; { extrait le prochain sommet de la serie & retourne son index} function FinDeSerie(UneSerie: SerieDeSommets): boolean; { vrai s'il n'y a plus de sommet suivant dans la serie } En utilisant ces primitives, tout en ignorant de quelle façon la structure de graphe est implantée, écrivez une procédure de parcours en profondeur qui imprime les noms des sommets du graphe fourni en paramêtre: procedure DFS(LeGraphe: Graphe); Solution exercice suivant

http://cuisung.unige.ch/std/ex/10/3a.html [23-09-2001 16:02:25]

Structuration des Données Informatiques - 10.4, exercice 1

Arbre lexicographique Question posée au contrôle continu du 16 juin 1997 On veut construire un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de sorte que les chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante

Les arcs sont étiquettés avec les lettres de l'alphabet (on suppose ici que l'on ne tient pas compte des accents sur les lettres) et les noeuds contiennent un booléen indiquant si le chemin de la racine à ce noeud représente un mot complet ou pas (sur le dessin - = faux et * = vrai). Sur la base des déclarations suivantes, écrivez une procédure imprimant touts les mots du dictionnaire dans l'ordre croissant de longueur de mot et, pour des mots d'une même longueur, par ordre alphabétique: type VersNoeud= ^Noeud; Noeud= record Desc: array['a'..'z'] of VersNoeud; Complet: boolean; end; { Noeud } var Dico: VersNoeud; procedure Imprime(LeDico: VersNoeud); Note: vous avez intérêt à considérer cet arbre lexicographique comme un graphe orienté et appliquer une des méthodes de parcours de graphe. Vous pouvez aussi considérer, si vous en avez besoin, que vous disposez d'un type "Pile" ou "FileDAttente" avec leurs procédures de manipulation. Vous pouvez aussi utiliser des strings pour réconstituer une séquence de lettres formant un mot. Solution

http://cuisung.unige.ch/std/ex/10/4a.html [23-09-2001 16:02:27]

Structuration des Données Informatiques - 13.4, exercice 1

exercice suivant

Hash-code Question posée au contrôle continu du 16 juin 1997 Soient deux fonctions de hash-code H1 et H2 retournant les valeurs numériques suivantes: mot: les examens du premier cycle pour lesquels il n y aurait qu H1(mot): 15 6 11 1 3 6 2 5 7 15 2 9 H2(mot): 8 5

12 14

2

10

17

7 5 13 8

22

mot: un examen oral a subir sont admis si chaque note atteint quatre H1(mot): 13 18 16 11 10 23 8 89 20 15 22 H2(mot): 9 6

1

4 3

7

13

6 17

2

12

16

On suppose que l'on utilise la méthode du chaînage externe à partir d'un tableau de 11 positions, en utilisant H1 pour déterminer quelle chaîne utiliser et H2 pour trier les éléments d'une même chaîne (c'est-à-dire qu'au sein d'une même chaîne, un mot mi sera placé avant un autre mot mj si H2(mi)
http://cuisung.unige.ch/std/ex/13/4a.html [23-09-2001 16:02:29]

Structuration des Données Informatiques - 15.1, exercice 1

exercice suivant

Tables de décision Question posée au contrôle continu du 16 juin 1997 Avec les déclarations suivantes définissant des tables de décision, écrivez une procédure "Extension" qui convertisse une table de décision condensée (paramètre d'entrée) en table étendue (paramètre de sortie): const MaxNbCond = ...; MaxNbRegles = ...; MaxNbActions = ...; type Conditions =(Vrai, Faux, Indetermine); TableDecision = record NbConditions: 1..MaxNbCond; NbRegles: 1..MaxNbRegles; ValCond: array[1..MaxNbRegles, 1..MaxNbCond] of Conditions; NbActions: 1..MaxNbActions; Agir: array[1..MaxNbRegles, 1..MaxNbActions] of boolean; TxtConditions:array[1..MaxNbCond] of string[30]; TxtActions:array[1..MaxNbActions] of string[30]; end; { TableDecision } procedure Extension(Entree: TableDecision; var Sortie: TableDecision); Note: Pour simplifier l'écriture, vous pourrez supposer que l'affectation d'enregistrements ou de tableaux est autorisée en Pascal. Solution exercice suivant

http://cuisung.unige.ch/std/ex/15/1a.html [23-09-2001 16:02:32]

Structuration des Données Informatiques - 7.4, exercice 4

Exercice suivant

Chaînes bidirectionnelles Question posée au contrôle continu du 28 avril 1997 Supposons qu'un programme d'édition de texte utilise la structure de chaîne de strings suivante pour représenter le texte en cours d'édition: type VersLigne = ^UneLigne; UneLigne = record Texte: string; LignePrecedente, LigneSuivante: VersLigne; end; { UneLigne } var LeTexte: VersLigne; a) Ecrivez une procédure "EchangeLignes", selon la déclaration suivante, qui échange deux éléments de la structure (on ne veut pas juste échanger le contenu du champs Texte): procedure EchangeLignes(var UnTexte: VersLigne; NoLigne1, NoLigne2: integer); b) Ecrivez une procédure "InverserLignes", selon la déclaration suivante, qui inverse complètement l'ordre des lignes dans la structure de donnée: procedure InverserLignes(var UnTexte: VersLigne); Dans les deux cas, il faudra prendre soin de vérifier tous les cas particuliers et diagnostiquer toutes les erreurs éventuelles. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4d.html [23-09-2001 16:02:34]

Structuration des Données Informatiques - 7.4, exercice 5

Exercice suivant

Chaînes bidirectionnelles Question posée au contrôle continu du 28 avril 1997 Dans le programme suivant, vous disposez d'une chaine bidirectionnelle qui a un pointeur supplémentaire (appelé ici S2): program test(input, output); type Ptr = ^Noeud; Noeud = record info : integer; Preced, Suiv, S2 : Ptr; end; var LaChaine, P : Ptr; procedure CreeS2(Depart:Ptr); var Deplacement, i:integer; Courant, Etape : Ptr; FinEtape : boolean; begin Etape := Depart; while Etape <> nil do begin Deplacement := Etape^.info; i := 1; Courant := Etape; FinEtape := false; if Deplacement > 0 then begin while (i <= Deplacement) and (not FinEtape) do if Courant^.Suiv <> nil then begin i := i+1; Courant := Courant^.Suiv; end {then} else begin Courant := nil; FinEtape := true; end; {if} Etape^.s2 := Courant; end {then} else begin Deplacement := -Deplacement; while (i <= Deplacement) and (not FinEtape) do if Courant^.Preced <> nil then begin i := i+1; Courant := Courant^.Preced; http://cuisung.unige.ch/std/ex/7/4e.html (1 of 2) [23-09-2001 16:02:39]

Structuration des Données Informatiques - 7.4, exercice 5

end {then} else begin Courant := nil; FinEtape := true; end; {if} Etape^.s2 := Courant; end; {else} Etape := Etape^.Suiv; end; {while} end; {CreeS2} begin initialise(LaChaine); CreeS2(LaChaine); P := LaChaine; if P <> nil then repeat write(P^.info:1,'->'); P := P^.s2; until P = nil; else writeln('nil'); end. où la procédure initialise(var Depart:Ptr); est utilisée pour faire les initialisations: créer la chaine et initialiser le pointeur S2 à nil. Quel résultat sera affiché quand LaChaine pointe sur: 1. 2 -> 0 -> 1 -> 1 -> -3 2. 3 -> -1 -> 2 -> -1 -> -3 Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4e.html (2 of 2) [23-09-2001 16:02:39]

Structuration des Données Informatiques - 8.2, exercice 2

Exercice suivant

Arbre généalogique Question posée au contrôle continu du 28 avril 1997 program arbre_genealogique; const MaxLongueurNom = 30; type Genre = (Masculin, Feminin); Noms = array[1..MaxLongueurNom] of char; ChaineFreresSoeurs = ^NoeudFrereSoeur; PersonnePtr = ^Personne; NoeudFrereSoeur = record FrereOuSoeur: PersonnePtr; FrereSoeurSuivant: ChaineFreresSoeurs; end; {NoeudFrereSoeur} Personne = record Nom: Noms; Prenom: Noms; Sexe: Genre; Epoux: PersonnePtr; FreresEtSoeurs: ChaineFreresSoeurs; Enfants: ChaineFreresSoeurs; end; {Personne} function NouvellePersonne(SonNom, SonPrenom: Noms; SonSexe: Genre): PersonnePtr; var laPersonne: PersonnePtr; begin new(laPersonne); with laPersonne^ do begin Nom := SonNom; Prenom := SonPrenom; Sexe := SonSexe; Epoux := nil; FreresEtSoeurs := nil; end; {with} NouvellePersonne := laPersonne; end; {NouvellePersonne}

http://cuisung.unige.ch/std/ex/8/2b.html (1 of 2) [23-09-2001 16:02:41]

Structuration des Données Informatiques - 8.2, exercice 2

procedure Epouse(epoux1, epoux2: PersonnePtr); begin epoux1^.Epoux := epoux2; epoux2^.Epoux := epoux1; end; {Epoux} procedure AjouteEnfant(Parent, Enfant: PersonnePtr); var NouveauNoeud, EnfantCourant, EnfantPrecedent: ChaineFreresSoeurs; begin new(NouveauNoeud); with NouveauNoeud^ do begin FrereOuSoeur := Enfant; FrereSoeurSuivant := nil; end; {with} EnfantCourant := Parent^.Enfants; if EnfantCourant = nil then begin {Ce nouvel Enfant est leur premier Enfant} Parent^.Enfants := NouveauNoeud; if Parent^.Epoux <> nil then Parent^.Epoux^.Enfants := NouveauNoeud; Enfant^.FreresEtSoeurs := NouveauNoeud; end {if} else begin Enfant^.FreresEtSoeurs := EnfantCourant; {cherche le dernier Enfant} while EnfantCourant <> nil do begin EnfantPrecedent := EnfantCourant; EnfantCourant := EnfantCourant^.FrereSoeurSuivant; end; {while} EnfantPrecedent^.FrereSoeurSuivant := NouveauNoeud; end; {else} end; {AjouteEnfant} Sur la base des déclarations et procédures ci-dessus, qui permettent de construire un arbre généalogique: 1. dessinez un diagramme qui montre l'utilisation de cette structure pour une famille contennant au moins deux generations; 2. écrivez une procédure qui trouvera tous les petits-enfants d'une personne et imprimera leurs noms et prénoms: procedure ImprimePetitsEnfants(LaPersonne: PersonnePtr); Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/2b.html (2 of 2) [23-09-2001 16:02:41]

Structuration des Données Informatiques - 8.1, exercice 2

Exercice suivant

Arbre syntaxique et chaîne Question posée à l'écrit du 5 mars 1997 Soit un arbre syntaxique contenant une expression arithmétique, basé sur les déclarations suivantes: type Contenus = (Operande, Operateur); Operations=(Addition, Soustraction, Multiplication, Division); VersNoeud = ^Noeud; Noeud = record case Contenu: Contenus of Operande: (Valeur: integer); Operateur:(Operation: Operations; Gauche,Droite: VersNoeud); end; (* Noeud *) Ecrivez une procédure qui convertira un tel arbre syntaxique en une chaîne contenant la même expression arithmétique en notation polonaise postfixée. Vous utiliserez à cet effet les déclarations suivantes: type VersMaillon = ^Maillon; Maillon = record Suivant: VersMaillon; case Contenu: Contenus of Operande: (Valeur: integer); Operateur:(Operation: Operations); end; (* Maillon *) Pour rappel, la notation polonaise postfixée consiste à noter une expression arithmétique avec l'opérateur à la suite des opérandes sur lesquels il porte. Cette notation ne nécessite donc pas de parenthèses. Par exemple, l'expression (85 - 9) * ((78 + 45) / (6 - 2)) est notée, en notation polonaise postfixée, de la façon suivante: 85 9 - 78 45 + 6 2 - / *. Pour vous aider, sachez que cette conversion correspond à une des méthodes classiques de parcours d'arbre. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/1b.html [23-09-2001 16:02:44]

Structuration des Données Informatiques - 14.3, exercice 2

Exercice suivant

B-arbre Question posée à l'écrit du 5 mars 1997 a) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 10

b) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 21

c) Avec le même B-arbre de départ qu'au point b, dessinez le B-arbre résultant de la suppression de la valeur 55. d) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 23

e) Avec le même B-arbre de départ qu'au point d, dessinez le B-arbre résultant de l'insertion de la valeur 4. f) Avec le même B-arbre de départ qu'au point d, dessinez le B-arbre résultant de la suppression de la valeur 15. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/14/3b.html [23-09-2001 16:02:58]

Structuration des Données Informatiques - 7.4, exercice 3

Exercice suivant

Chaînes bidirectionnelles Question posée à l'examen écrit du 15 octobre 1996 Supposons qu'un programme d'édition de texte utilise la structure de chaîne de strings suivante pour représenter le texte en cours d'édition: type VersLigne = ^UneLigne; UneLigne = record Texte: string; LignePrecedente, LigneSuivante: VersLigne; end; { UneLigne } var LeTexte: VersLigne; a) Ecrivez une procédure "EffaceLigne", selon la déclaration suivante, qui change la structure de donnée pour refléter la suppression d'une ligne du texte: procedure EffaceLigne(var UnTexte: VersLigne; NumeroLigne: integer); b) Ecrivez une procédure "JoindreLignes", selon la déclaration suivante, qui change la structure de donnée pour combiner la ligne courante et la ligne suivante en une seule ligne (le contenu de la ligne suivante est inséré à la fin de la ligne courante et la ligne suivante est alors supprimée): procedure JoindreLignes(var UnTexte: VersLigne; LigneCourante: integer); Dans les deux cas, il faudra prendre soin de vérifier tous les cas particuliers et diagnostiquer toutes les erreurs éventuelles. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4c.html [23-09-2001 16:03:00]

Structuration des Données Informatiques - 14.2, exercice 1

Exercice suivant

Fichiers séquentiels indexés et B-arbres Question posée à l'examen du 15 octobre 1996 a) Quelle est la taille de l'espace disque nécessaire pour être sûr de pouvoir créer un fichier séquentiel indexé qui doit contenir 1'000'000 éléments, sachant qu'un élément nécessite une place de 76 octets, dont une clé de 8 octets, que les blocs de données ont une taille de 1536 octets et les blocs d'index 1024 octets et que les pages de données sont initialement remplies à 80%? On supposera que les références, dans un bloc d'index, à un autre bloc d'index ou à un bloc de donnée, tiennent sur 4 octets. Justifiez votre réponse et donnez le détail des calculs. En plus de la taille de l'espace disque, vous indiquerez, entre autres, le nombre de blocs de données, la profondeur de l'arborescence des blocs d'index et le nombre de blocs d'index à chaque niveau. b) Pour les mêmes données (même nombre et même taille d'élément), quelle sera la taille de l'espace disque nécessaire et le nombre de niveaux si l'on utilise une structure de B-arbre avec des pages de 1024 octets (donnez les valeurs minimales et maximales possibles, dans l'hypothèse de pages à moitié pleines ou entièrement pleines)? Là aussi, justifiez votre réponse et donnez le détail des calculs: ordre du B-arbre, nombre de pages minimum et maximum, ... N.B. Comme pour le séquentiel indexé, les références à une page occupent 4 octets. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/14/2a.html [23-09-2001 16:03:28]

Structuration des Données Informatiques - 7.2, exercice 1

Chaînes mono-directionnelles Question posée à l'examen écrit du 9 juillet 1996 Soit une d`une chaîne monodirectionnelle avec des éléments entiers. Ecrivez une procédure Pascal qui supprime à la fois le premier et le dernier élément de la chaîne, et ceci de manière répétitive, jusqu`a ce qu'il ne reste qu'un seul élément, ou jusqu'a ce que la chaîne soit vide. La procédure donnera comme résultat soit le dernier élément restant, soit le pointeur "nil". Exemples: 1.

Dans ce cas, on supprime les éléments contenant les valeurs entièlres 2 et -1, et le résultat de la procédure sera alors 3. 2.

Dans ce cas, on supprimera d'abord 2 et 5, ensuite 3 et -1, et le résultat sera alors "nil". Solution

http://cuisung.unige.ch/std/ex/7/2a.html [23-09-2001 16:03:36]

Structuration des Données Informatiques - 11.3, exercice 2

Exercice suivant

Réseau autoroutier Soit un réseau autoroutier tel que celui-ci:

1. Quelle structure(s) de donnée(s) utiliseriez-vous pour le représenter; dessinez-la. 2. Donnez le détail des déclarations que vous feriez, en Pascal. 3. Ecrivez une fonction qui déterminera la distance minimale à parcourir entre deux villes données en paramètre. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/11/3b.html [23-09-2001 16:04:08]

Structuration des Données Informatiques - 7.4, exercice 1

Exercice suivant

Anneaux bidirectionnels Question posée au conctrôle continu du 17 juin 1996 On vous fournit un entier ainsi qu'un anneau bidirectionnel ayant comme éléments des entiers, pouvant être négatifs. On vous demande de vous déplacer dans l'anneau à la position absolue donnée par l'entier qui vous est donné. Là, vous prenez l'entier qui se trouve dans l'élément courant, vous supprimez l'élément courant, et vous vous déplacez dans l'anneau, cette fois-ci de façon relative à la position courante en fonction du nombre qui s'y trouvait. Vous devez répéter ces pas (prendre l'entier, supprimer l'élément, se déplacer) jusqu'à ce que il n'y ait plus d'élément dans l'anneau, jusqu'à ce que vous sortiez de l'anneau, ou bien jusqu'à ce que vous rencontriez la valeur 0 (zéro) dans l'anneau. (Attention, si vous arrivez à la fin de l'anneau, il ne faut pas repartir depuis le début; de même, si on arrive au début, il ne faut pas continuer à la fin). On vous demande de fournir, dans un paramètre de sortie, le type d'arrêt et d'imprimer, dans la procédure, les valeurs se trouvant dans les éléments visités. Utilisez les déclarations suivantes: type TypeArret = (SortieAnneau, ElementNul, AnneauVide); Anneau = ^Element; Element = record Entier : Integer; Predecesseur, Succeseur : Anneau; end; { Element } procedure DeplacerDansAnneau(var UnAnneau : Anneau; Deplacement: integer; var Arret : TypeArret); Exemple:

Dans le cas ci-dessus, si l'entier donné initialement est 1, on va à la première position, on prend 2, on l'imprime et on supprime la première position de l'anneau. On se déplace en avant de 2 positions (correspondant à la position 3 dans l'anneau initial), on prend -2, on l'imprime et on supprime l'é lément. Ensuite il faut signaler la fin du programme, parce qu'avant l'élément que l'on vient de suprimer il n'y a qu'un seul élément (contenant 4) et l'on ne peut donc pas se déplacer de 2 éléments en arrière. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4a.html [23-09-2001 16:04:14]

Structuration des Données Informatiques - 8.1, exercice 1

Exercice suivant

Arbre de tri Question posée au conctrôle continu du 17 juin 1996 a) Etant donné l'arbre de tri suivant, donnez une séquence possible des données fournies en entrée qui aurait permis d'aboutir à l'arbre de tri en question:

b) idem pour l'arbre suivant:

Solution Exercice suivant

http://cuisung.unige.ch/std/ex/8/1a.html [23-09-2001 16:04:24]

Structuration des Données Informatiques - 11.5, exercice 1

Exercice suivant

Tri topologique inverse Question posée au conctrôle continu du 17 juin 1996 En s'inspirant de la description de graphes non-orientés en termes de type abstrait vue au cours, nous allons supposer que les types "Graphe" et "SerieDeSommets" ont été définis, sans que vous ne connaissiez les détails de ces structures. Nous allons aussi supposer que les primitives suivantes sont à votre disposition: function Index(NomSommet: string; LeGraphe: Graphe): integer; { retourne un numero compris entre 1 et MaxNbSommets } function NomSommet(IndexSommet: integer; LeGraphe: Graphe) :string; { retourne le nom du sommet dont l'index est fourni } function NombreDeSommets(LeGraphe: Graphe): integer; {retourne le nombre de sommets effectifs composant le graphe} function SommetsVoisins(IndexSommet: integer; LeGraphe: Graphe): SerieDeSommets; { retourne une structure permettant de retrouver l'index des voisins immédiats } function PremierSommet(var UneSerie: SerieDeSommets): integer; { extrait le premier des sommets de la série et retourne son index } function SommetSuivant(var UneSerie: SerieDeSommets): integer; { extrait le prochain sommet de la serie & retourne son index} function FinDeSerie(UneSerie: SerieDeSommets): boolean; { vrai s'il n'y a plus de sommet suivant dans la serie } En utilisant ces primitives, tout en ignorant de quelle façon la structure de graphe est implantée, écrivez une procédure "TriTopologiqueInverse(LeGraphe: Graphe)" qui imprime les sommets du graphe dans l'ordre topologique inverse. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/11/5a.html [23-09-2001 16:04:26]

Structuration des Données Informatiques - 14.3, exercice 1

Exercice suivant

B-arbre Question posée au contrôle continu du 17 juin 1996 Dessinez le B-arbre résultant de la suppression de la valeur g dans le B-arbre d'ordre 1 suivant:

Solution Exercice suivant

http://cuisung.unige.ch/std/ex/14/3a.html [23-09-2001 16:04:59]

Structuration des Données Informatiques - 7.4, exercice 2

Exercice suivant

Chaînes bidirectionnelles Question posée au conctrôle continu du 20 juin 1995 On dispose d'une chaîne bidirectionnelle avec des éléments contenant un nombre entier (pouvant être négatif). Ecrire une procédure qui reçoive en paramètre la chaîne et un entier, puis se déplace à la position dans la chaîne indiquée par cet entier et utilise le contenu de cette position (nombre entier pouvant être négatif) pour se déplacer à nouveau, mais cette fois de manière relative à la position courante. La procédure réitère ces déplacement relatifs en fonction de la nouvelle position courante jusqu'à ce qu'un déplacement la fasse sortir de la chaîne ou que l'on revienne sur un élément déjà visité. La procédure retournera alors le type d'arrêt et la position du dernier élément examiné. Exemple:

Si l'on donne à la procédure le nombre 1, elle ira examiner le 1er élément de la chaîne, qui contient la valeur 2. Elle ira ensuite examiner la position 3 (position courante=1, déplacement relatif=2), puis la position 2 (position courante=3, déplacement relatif=-1) et s'arrêtera là car la prochaine position serait 6 et que la chaîne est de longueur 4. N.B.: En plus de la procédure, donner les déclarations de type nécessaires pour la structure de chaîne. Solution Exercice suivant

http://cuisung.unige.ch/std/ex/7/4b.html [23-09-2001 16:05:04]

Structuration des Données Informatiques - 8.2, exercice 1

exercice suivant

Arbre lexicographique Question posée au contrôle continu du 20 juin 1995 On veut construire un arbre multiple d'ordre 26 permettant de stocker des mots d'un dictionnaire de sorte que les chemins partant de la racine représentent des mots du dictionnaire, de la façon suivante

Les arcs sont étiquettés avec les lettres de l'alphabet (on suppose ici que l'on ne tient pas compte des accents sur les lettres) et les noeuds contiennent un booléen indiquant si le chemin de la racine à ce noeud représente un mot complet ou pas (sur le dessin - = faux et * = vrai). En utilisant la possibilité que donne le langage Pascal d'indexer un tableau de pointeurs à l'aide d'un intervalle de caractères afin de représenter les étiquettes des arcs, donner: a) les déclarations de types et de variables nécessaires à la construction d'un tel dictionnaire, b) une fonction booléenne ayant pour paramètre le dictionnaire et un string et indiquant si le mot contenu dans le string se trouve dans le dictionnaire, c) une procédure imprimant touts les mots du dictionnaire dans l'ordre alphabétique. Solution exercice suivant

http://cuisung.unige.ch/std/ex/8/2a.html [23-09-2001 16:05:07]

Structuration des Données Informatiques - 11.3, exercice 1

Exercice suivant

Plus courts chemins dans un graphe Question posée au conctrôle continu du 20 juin 1995 En s'inspirant de la méthode de Warshall (page 157 du livre) pour déterminer la fermeture transitive d'un graphe représenté par une matrice de connectivité, dériver un algorithme construisant une matrice de valeurs numériques indiquant la longueur du plus court chemin entre tous les divers noeuds d'un graphe. Une approche simple consiste à d'abord construire la matrice résultat à partir de la matrice de connectivité, en mettant la valeur 1 là où il y a des arcs dans la matrice de connectivité. Puis, selon la méthode de Warshall, examiner toutes les combinaisons X->Y->Z telles qu'il existe un chemin de X vers Y et de Y vers Z et comparer la longueur de X->Y + Y->Z avec le contenu de la matrice résultat pour la case (X,Z). Si la somme est plus petite, elle remplacera l'ancienne valeur de la case (X,Z). (Faites bien attention à l'initialisation de la matrice résultat!) Solution Exercice suivant

http://cuisung.unige.ch/std/ex/11/3a.html [23-09-2001 16:05:09]

http://cuisung.unige.ch/std/ex/7/2a.txt

type versElement = ^Element; Element = record info : integer; suivant : versElement; end; { Debut est le pointeur de debut de chaine, Resultat contiendra le resultat - nil ou un pointeur vers un element de la chaine } procedure Suppression(var Debut, Resultat : versElement); var courant : versElement; fin : boolean; begin fin := false; while not fin do begin if Debut = nil then begin {chaine vide} fin := true; Resultat := nil; end else if Debut^.suivant = nil then begin {un seul element} Resultat := Debut; fin := true; end else begin {on efface le premier element} courant := Debut; Debut:= Debut^.suivant; dispose(courant); if Debut^.suivant = nil then begin {il y avait 2 el} dispose(Debut); Resultat := nil; fin := true; end else begin {plus de 2 elements} courant := Debut; { on est sur qu'il n'est pas nil} while courant^.suivant^.suivant <> nil do courant := courant^.suivant; dispose(courant^.suivant); courant^.suivant:=nil; {c'est bien necessaire afin d'indiquer la fin de la chaine} end; {else/begin} end; {else/begin} end; {while} end; {Suppression}

http://cuisung.unige.ch/std/ex/7/2a.txt [23-09-2001 16:06:38]

http://cuisung.unige.ch/std/ex/8/2e.txt

{ version recursive } function Trouve(Mot: string; Dico: VersNoeud): boolean; begin { Trouve } if Dico=nil then Trouve := false else if Mot = '' then Trouve := Dico^.Complet else Trouve := Trouve(Dico^.Desc[Mot[1]], copy(Mot,2,length(Mot)-1)); end; { Trouve } { version non-recursive } function Trouve(Mot: string; Dico: VersNoeud) : boolean; var i: integer; Courant: VersNoeud; begin { Trouve } i:=1; Courant := Dico; while (i<=Length(Mot)) and (Courant<>nil) do begin Courant := Courant^.Desc[Mot[i]]; i := i+1; end; { while } if Courant=nil then Trouve := false else Trouve := Courant^.Complet; end; { Trouve }

http://cuisung.unige.ch/std/ex/8/2e.txt [23-09-2001 16:07:08]

http://cuisung.unige.ch/std/ex/8/1h.txt

procedure ajouteElement(inNouveauContenu:integer; var inoutRacine: pElement); begin if (inoutRacine=nil)then begin creeElement_Contenu(inNouveauContenu, inoutRacine); end else begin if (inoutRacine^.mContenu < inNouveauContenu) then begin ajouteElement(inNouveauContenu,inoutRacine^.mGauche); end else begin ajouteElement(inNouveauContenu,inoutRacine^.mDroite); end; end; end; { ajouteElement } procedure sommeArbre(var inoutSomme:integer; var inRacine: pElement); begin if (inRacine<>nil)then begin sommeArbre(inoutSomme,inRacine^.mGauche); sommeArbre(inoutSomme,inRacine^.mDroite); inoutSomme := inoutSomme + inRacine^.mContenu; end; end; { sommeArbre } procedure produitArbre(var inoutProduit:integer; var inRacine: pElement); begin if (inRacine<>nil)then begin produitArbre(inoutProduit,inRacine^.mGauche); produitArbre(inoutProduit,inRacine^.mDroite); inoutProduit:= inoutProduit * inRacine^.mContenu; end; end; { produitArbre } procedure accumulerArbre(var inoutAccumulateur : integer; inFonction : TFonction; var inRacine: pElement); begin if (inRacine<>nil)then begin accumulerArbre(inoutAccumulateur, inFonction, inRacine^.mGauche); inoutAccumulateur := inFonction(inRacine^.mContenu, inoutAccumulateur); accumulerArbre(inoutAccumulateur, inFonction, inRacine^.mDroite); end; end; { accumulerArbre }

http://cuisung.unige.ch/std/ex/8/1h.txt [23-09-2001 16:07:33]

http://cuisung.unige.ch/std/ex/8/1g.txt

function Chemin(MonArbre: pNoeudArbre; MaValeur: integer): PtrNoeudCh; var Courant: pNoeudArbre; DebutChaine, FinChaine: PtrNoeudCh; procedure AjouteFinChaine(UnNoeud: pNoeudArbre); var Fin: PtrNoeudCh; begin Fin := FinChaine; if DebutChaine = nil then begin new(DebutChaine); FinChaine := DebutChaine; end else begin new(FinChaine^.Suivant); FinChaine := FinChaine^.Suivant; end; with FinChaine^ do begin Element := UnNoeud; Precedent := Fin; Suivant := nil; end; { with } end; { AjouteFinChaine } begin { Chemin } if MonArbre = nil then Chemin := nil else begin Courant := MonArbre; DebutChaine := nil; FinChaine := nil; while (Courant <> nil) do begin AjouteFinChaine(Courant); if MaValeur = Courant^.Valeur then Courant := nil else if MaValeur < Courant^.Valeur then Courant := Courant^.Gauche else Courant := Courant^.Droite; end; { while } Chemin := DebutChaine; end; { if } end; { Chemin }

http://cuisung.unige.ch/std/ex/8/1g.txt [23-09-2001 16:08:03]

solution de l'execrcice

. La valeur 25 devrait normalement venir dans la deuxième feuille à partir de la gauche. La page en question étant pleine, on examine les pages adjacentes pour voir s'il y a de la place pour opérer une "roccade". En l'occurrence, la voisine de droite a une place libre. La valeur 40, de la page parente, va donc occuper cette place libre et est remplacée par la valeur 30, qui est la plus grande valeur de la page devant subir l'insertion. La feuille qui contenait la valeur 30 a maintenant une place libre permettant d'accueillir la valeur 25.

b. mécanisme similaire pour l'insertion de la valeur 20.

c. La valeur 14 devrait normalement venir dans la feuille qui se trouve à l'extrème gauche. La page en question étant pleine et sa voisine aussi, il faut scinder la page en deux et insérer l'élément milieu (9) dans la page parente

d. La valeur 6 devrait normalement venir dans la feuille qui se trouve à l'extrème gauche. La page en question étant pleine et sa voisine aussi, il faut scinder la page en deux et insérer l'élément milieu (6) dans la page parente. C'est donc la nouvelle valeur qui vient s'insérer dans la page parente.

e. Pour supprimer la valeur 60, il faut la remplacer par la plus grande valeur du sous-arbre gauche ou la plus petite valeur du sous-arbre droit. Ici, nous avons choisi la valeur 51 (plus grande valeur du sous-arbre gauche). La feuille qui contenait la valeur 51 a encore 2 éléments, ce qui est suffisant pour ne pas nécessiter plus d'opérations.

http://cuisung.unige.ch/std/ex/14/3h.sol.html (1 of 3) [23-09-2001 16:09:52]

solution de l'execrcice

Par contre, si nous choisissons de remplacer la valeur 60 par la plus petite valeur du sous-arbre droit (63), la feuille contenant 63 tombera en dessous du seuil minimum (il ne restera que la valeur 70). Comme sa voisine de droite est au seuil minimum, on ne peut pas lui emprunter d'élément. Il faut donc combiner la page ne contenant plus que 70 avec sa voisine de droite contenant 76 et 79, en absorbant au passage la valeur de la page parente (75) qui se trouve entre les deux pages à combiner. On obtient ainsi une page contenant 70, 75, 76 et 79. Mais la page parente ne contient plus que la valeur 80. Sa voisine de gauche étant au seuil minimum (valeurs 15 et 40), il faut combiner les deux pages en absorbant la valeur de la page parente (63) qui se trouve entre elles. On obtient ainsi une page contenant 15, 40, 63 et 80. L'autre page, maintenant vide, peut être supprimée, ainsi que la page racine qui, elle aussi, est maintenant vide.

f. La page contenant la valeur 63 étant déjà à son seuil minimum, la suppression de la valeur 63 implique soit de rééquilibrer en empruntant une valeur d'une page voisine (ayant même page parente) si une de celles-ci a assez d'éléments, ou en la recombinant avec une page voisine sinon. En l'occurrence, la page voisine de droite est elle aussi au seuil minimum. Il faut donc recombiner les deux pages en une en absorbant par la même occasion l'élément (75) qui se trouvait dans la page parente, entre les deux pages à combiner. On a donc une page qui contient les valeurs 70, 75, 76 et 79. Mais la page parente est maintenant au-dessous du seuil minimum (elle ne contient que la valeur 80) et l'on doit donc soit emprunter une valeur à une des pages adjacentes (il n'y en a qu'une, qui contient 15 et 40), soit combiner la page (80) avec sa voisine (15, 40) tout en absorbant l'élément de la page au-dessus (60) qui se trouvait entre les deux pages en question. On obtient ainsi une page contenant 15, 40, 60 et 80. L'autre page, maintenant vide, peut être supprimée, ainsi que la page racine qui, elle aussi, est maintenant vide.

g. La suppression de la valeur 80 se fait en la remplaçant par la plus grande valeur du sous-arbre gauche (79) ou la plus petite valeur du sous-arbre droit (85). Si l'on prend la valeur 79, la page qui contenait cette valeur initialement va tomber en dessous du seuil minimum (elle ne contient plus que 76). Comme on ne peut pas emprunter une valeur d'une page voisine, il faut combiner la page ne contenant plus que 76 avec une de ses voisines. Si l'on prend la voisine de droite (contenant 85 et 90) et que l'on absorbe la valeur qui se trouve entre ces deux pages dans la page parente (79), on obtient une page contenant 76, 79, 85 et 90. Mais la page parent ne contient plus que la valeur 75 et se trouve donc en dessous du seuil minimum. Comme cette page n'a pas de voisine à laquelle emprunter de valeur, il faut la combiner avec sa voisine (contenant 15 et 40) en absorbant la valeur de la page parente qui se trouve entre elles (60). On obtient donc une page contenant 15, 40, 60 et 75. La page racine devient vide et peut être supprimée.

http://cuisung.unige.ch/std/ex/14/3h.sol.html (2 of 3) [23-09-2001 16:09:52]

solution de l'execrcice

Si l'on avait échangé la valeur 80 par la valeur 85 (plus petite valeur du sous-arbre droit), on aurait quand même abouti au même résultat.

http://cuisung.unige.ch/std/ex/14/3h.sol.html (3 of 3) [23-09-2001 16:09:52]

http://cuisung.unige.ch/std/ex/8/1f.txt

On peut soit parcourir l'arbre dans l'ordre Droite-Racine-Gauche et faire des insertions en debut de chaine, soit parcourir l'arbre en ordre et faire des insertions en fin de chaine. La solution qui suit correspond a la premiere approche: function Conversion(Arbre: pNoeudArbre): PtrNoeudCh; var Res: PtrNoeudCh; procedure ParcoursEnOrdreInverse(P: pNoeudArbre); var Tmp: PtrNoeudCh; begin { ParcoursEnOrdreInverse } if P <> nil then begin ParcoursEnOrdreInverse(P^.droite); new(Tmp); with Tmp^ do begin Donnee := P^.nombre; Precedent := nil; Suivant := Res; end; { with } if Res<> nil then Res^.Precedent := Tmp; Res := Tmp; ParcoursEnOrdreInverse(P^.gauche); end; { if } end; { ParcoursEnOrdreInverse } begin Res := nil; ParcoursEnOrdreInverse(Arbre); Conversion := Res; end; { Conversion }

http://cuisung.unige.ch/std/ex/8/1f.txt [23-09-2001 16:10:14]

solution de l'exercice

La première solution consiste à représenter le document XML comme un vrai arbre multiple, où la racine de l'arbre représente l'élément principal du document XML et chaque sous-arbre représente un élément directement imbriqué dans l'élément principal du document XML:

Cette structure d'arbre multiple peut aussi être représentée comme un arbre binaire avec un pointeur fils pointant sur le premier sous-élément et un pointeur frère pointant d'un descendant vers un autre descendant du même ancêtre immédiat:

http://cuisung.unige.ch/std/ex/8/2d.sol.html [23-09-2001 16:10:54]

http://cuisung.unige.ch/std/ex/9/1b.txt

procedure display(inPair : PSchemePairOuValeur); {vous etes autorise(es) de mettre des variables ici} begin if(inPair<>nil)then begin if(inPair^.mEstValeur)then begin write(inPair^.mValeur); end else begin write('('); display(inPair^.mCar); write(' . '); display(inPair^.mCdr); write(')'); end; end else begin write( '()' ); end; end;

http://cuisung.unige.ch/std/ex/9/1b.txt [23-09-2001 16:11:21]

Structuration des Données Informatiques - 11.3, solution exercice 4

La fermeture transitive est l'opération qui consiste à ajouter un arc entre toute paire de noeuds pour laquelle il existe un chemin du premier noeud vers le deuxième. Il ne faut bien entendu pas oublier d'ajouter un arc d'un noeud vers lui-même s'il existe un chemin simple qui part de ce noeud pour y revenir (comme dans l'exemple b).

http://cuisung.unige.ch/std/ex/11/3d.sol.html [23-09-2001 16:12:15]

http://cui.unige.ch/eao/www/std/ex/14/3f.txt

{ Parcourir et afficher a l'ecran } procedure parcourirBArbreEnOrdre(inArbre : PPage ); var i : integer; begin { parcourirBArbreEnOrdre } if (inArbre<>nil)then begin if (inArbre^.mPremierEnfant <> nil)then begin parcourirBArbreEnOrdre(inArbre^.mPremierEnfant); end; for i:=1 to inArbre^.mNombreEnfants do begin write(inArbre^.mElement[i].mCle); write(' '); if (inArbre^.mElement[i].mEnfant <> nil)then begin parcourirBArbreEnOrdre(inArbre^.mElement[i].mEnfant); end; { if } end; { for } end; { if } end; { parcourirBArbreEnOrdre } { Parcourirr EN ORDRE INVERSE et afficher a l'ecran } procedure parcourirBArbreEnOrdreInverse(inArbre : PPage ); var i : integer; begin { parcourirBArbreEnOrdreInverse } if (inArbre<>nil)then begin for i:=inArbre^.mNombreEnfants to 1 do begin if (inArbre^.mElement[i].mEnfant <> nil)then begin parcourirBArbreEnOrdreInverse(inArbre^.mElement[i].mEnfant); end; { if } write(inArbre^.mElement[i].mCle); write(' '); end; { for } if (inArbre^.mPremierEnfant <> nil)then begin parcourirBArbreEnOrdreInverse(inArbre^.mPremierEnfant); end; { if } end; { if } end; { parcourirBArbreEnOrdreInverse }

http://cui.unige.ch/eao/www/std/ex/14/3f.txt [23-09-2001 16:13:21]

http://cuisung.unige.ch/std/ex/7/1b.txt

{ Cette fonction prend la chaine inChaine et retourne une nouvelle chaine, qui contient les memes valeurs que inChaine, mais en ordre inverse: Si inChaine est (1 2 3) le resultat va etre la chaine (3 2 1). AUCUNE VALEUR QUI APPARTIENT A INCHAINE NE DOIT ETRE MODIFIE } function creeChaineInversee(inChaine:PElement):PElement; var lRoot : PElement; lNouveau : PElement; lIterator : PElement; begin lRoot:=nil; lIterator:=inChaine; while(lIterator<>nil) do begin new(lNouveau); lNouveau^.mContenu:=lIterator^.mContenu; { N.B.: Ca marche pour le premier element de la nouvelle liste aussi. } lNouveau^.mSuivant:=lRoot; lRoot:=lNouveau; lIterator:=lIterator^.mSuivant; end; { while } creeChaineInversee:=lRoot; end; { creeChaineInversee }

http://cuisung.unige.ch/std/ex/7/1b.txt [23-09-2001 16:14:29]

Structuration des Données Informatiques - 8.1, exercice 5, solution

Solution de Wolfgang Mueller: question concernant cette solution: ● lors de l'appel initial à la fonction, que doit valoir le deuxième paramêtre? function verifieArbre(inRacine: PNoeud; var inoutDerniereVisitee:integer):boolean; var lReturnValue : boolean; begin if(inRacine=nil)then begin { un arbre vide est un arbre de tri valide } return true; end else begin {verifie qu'a gauche c'est bien trie} lReturnValue:=verifieArbre(inRacine^.mLeft, inoutDerniereVisitee); { verifie que la valeur de la racine courante est plus grande que celle du dernier noeud parcouru } lReturnValue:= lReturnValue and (inoutDerniereVisitee <= inRacine^.mValue); { maintenant la valeur de la racine courante est la derniere visitee } inoutDerniereVisitee:= inRacine^.mValue; { verifie qu'a droite c'est bien trie } lReturnValue:=lReturnValue and verifieArbre(inRacine^.mRight, inoutDerniereVisitee); verifieArbre := lReturnValue; end; (* if else *) end; (* verifieArbre *)

Solution de Bertrand Ibrahim: function verifieArbre(Racine: PNoeud):boolean; (* effectue un parcours en-ordre et verifie, a chaque valeur traitee, qu'elle est bien superieure a la derniere valeur traitee jusqu'a present. Arrete la verification des qu'une erreur est trouvee. *) var Ok: boolean; LastVal: integer; (* derniere valeur traitee, modifiee par effet de bord *) procedure Parcours(P: PNoeud); (* accede a la variable LastVal par effet de bord *) begin if (P<>nil) and Ok then begin

http://cuisung.unige.ch/std/ex/8/1eSol.html (1 of 2) [23-09-2001 16:15:13]

Structuration des Données Informatiques - 8.1, exercice 5, solution

Parcours(P^.gauche); if LastVal > P^.nombre then Ok := false else LastVal := P^.nombre Parcours(P^.droite); end; (* Parcours *) begin Ok:= true; LastVal:= -MaxInt; Parcours(Racine); return Ok; end; (* verifieArbre *)

http://cuisung.unige.ch/std/ex/8/1eSol.html (2 of 2) [23-09-2001 16:15:13]

http://cui.unige.ch/eao/www/std/ex/7/4j.txt

procedure Tri(var Anneau: VersAnneau); var P1, P2, Dernier, Pred, Suiv, NextInnerStep, NextOuterStep: VersAnneau; begin (* Tri *) if Anneau <> nil then if Anneau <> Anneau^.Suivant then begin (* anneau a au moins 2 elem. *) Dernier := Anneau^.Precedent; if Dernier = Anneau^.Suivant then begin (* que 2 elem. au total *) if P1^.Info > P2^.Info then Anneau := Dernier; end else begin (* l'anneau a au moins 3 elem. *) P1 := Anneau; while P1 <> Dernier do begin NextOuterStep := P1^.Suivant; P2 := NextOuterStep; while P2 <> Anneau do begin NextInnerStep := P2^.Suivant; if P1^.Info > P2^.Info then begin if P1^.Suivant = P2 then (* permute deux elem. adjascents *) with P1^ do begin Pred := Precedent; Suiv := P2^.Suivant; Precedent := P2; Suivant := Suiv; Pred^.Suivant := P2; P2^.Precedent := Pred; P2^.Suivant := P1; Suiv^.Precedent := P1; end (* with *) else if P1^.Precedent = P2 then (* perm. premier et dernier *) with P1^ do begin Pred := P2^.Precedent; Suiv := P1^.Suivant; Precedent := Pred; Suivant := P2; Suiv^.Precedent := P2; Pred^.Suivant := P1; P2^.Precedent := P1; P2^.Suivant := Suiv; end (* with *) else with P1^ do begin (* perm. 2 el. separes par au moins 1 el *) Pred := Precedent; Suiv := Suivant; Precedent := P2^.Precedent; Suivant := P2^.Suivant; Pred^.Suivant := P2; Suiv^.Precedent := P2; P2^.Precedent := Pred; P2^.Suivant := Suiv; Pred := Precedent; Suiv := Suivant; Pred^.Suivant := P1; Suiv^.Precedent := P1; end; (* with *) if Anneau = P1 then Anneau := P2; P2 := NextInnerStep; end; (* while P2 *) P1 := NextOuterStep; end; (* while P1 *) end; (* if *) end; (* if *) end; (* Tri *)

http://cui.unige.ch/eao/www/std/ex/7/4j.txt [23-09-2001 16:16:25]

solution, 8.3 exercice 2

1.

2.

http://cui.unige.ch/eao/www/std/ex/8/3b.sol.html [23-09-2001 16:16:54]

http://cuisung.unige.ch/std/ex/7/4i.txt

procedure InsereFin(var Anneau: PtrNoeud; LaDonnee: integer); var Nouveau: PtrNoeud; begin if Anneau = nil then begin new(Anneau); with Anneau^ do begin Preced:= Anneau; Suivant:= Anneau; Donnee:= LaDonnee; end; (* with *) end (* then *) else begin new(Nouveau); with Nouveau^ do begin Donnee:= LaDonnee; Suivant:= Anneau; Preced:= Anneau^.Preced; Anneau^.Preced^.Suivant := Nouveau; Anneau^.Preced := Nouveau; end; (* with *) end; (* if *) end; (* InsereFin *) function NbElem(Anneau: PtrNoeud): integer; var Courant: PtrNoeud; Nb: integer; begin if Anneau = nil then NbElem := 0 else begin Courant := Anneau^.Suivant; Nb := 1; while Courant <> Anneau do begin Courant := Courant^.Suivant; Nb := succ(Nb); end; (* while *) NbElem := Nb; end; (* if *) end; (* NbElem *) procedure Split(Ring: PtrNoeud; Data: integer; var LowerRing, HigherRing: PtrNoeud); var Courant: PtrNoeud; begin LowerRing := nil; HigherRing := nil; if Ring <> nil then begin Courant := Ring; repeat if Courant^.Donnee < Data then InsereFin(LowerRing, Courant^.Donnee) else InsereFin(HigherRing, Courant^.Donnee); Courant := Courant^.Suivant; until Courant=Ring; end; (* if *) end; (* Split *)

http://cuisung.unige.ch/std/ex/7/4i.txt [23-09-2001 16:17:45]

http://cuisung.unige.ch/std/ex/8/1d.txt

1) Arbre('-', Arbre('*', Feuille('5'), Arbre('-', Feuille('4'), Arbre('+', Feuille('3'), Arbre('-', nil, Arbre('-', nil, Feuille('2') ) ) ) ) ), Arbre('/', Arbre('-', Feuille('1'), Feuille('9') ), Arbre('+', nil, Arbre('*', Feuille('8'), Feuille('7') ) ) ) ) 2) function Feuille(Contenu: integer): integer; begin Feuille := Contenu; end; (* Feuille *) function Arbre(ContenuRacine: char; Gauche, Droit: integer): integer; (* Dans ce cas, il faut remplacer dans l'expression 1) les "nil" par des "0" *) begin case ContenuRacine of '+': Arbre := Gauche + Droit; '-': Arbre := Gauche - Droit; '*': Arbre := Gauche * Droit; '/': Arbre := Gauche div Droit; end; (* case *) end; (* arbre *)

http://cuisung.unige.ch/std/ex/8/1d.txt [23-09-2001 16:18:07]

http://cuisung.unige.ch/std/ex/7/4h.txt

function Inverse(Ring: VersAnneau): VersAnneau; var Fin, { sert a memoriser la fin de l'anneau resultant } Courant, { sert a parcourir l'anneau d'entree } Invers: VersAnneau; { pointeur debut de l'anneau resultant } begin if Ring=nil then Inverse:=nil { si l'anneau est vide, le resultat est vide } else begin new(Fin); { cree l'element qui sera a la fin de l'anneau resultant } Fin^.Info := Ring^.Info; { y copie l'info du ler elt. de l'anneau d'entree } Invers := Fin; { le pointeur debut pointe sur l'elt que l'on vient de creer} Courant := Ring^.Suivant; { on va parcourir le reste de l'anneau d'entree } while Courant<>Ring do begin {boucle tant qu'on n'est pas revenu au 1er elt} new(Tmp); { cree un nouvel element } with Tmp^ do begin Info := Courant^.Info; { y copie l'info de l'element courant } Suivant := Invers; { fait une insertion debut dans l'anneau } Suivant^.Precedent := Tmp; { resultant sans se preoccuper de fermer } end; { with } { l'anneau a chaque fois } Invers := Tmp; Courant := Courant^.Suivant; end; { while } Fin^.Suivant := Invers; { reste a ferme l'anneau en reliant le premier } Invers^.Precedent := Fin;{ element au dernier, dans les deux sens } Inverse:= Invers; end; { if } end; { Inverse } function estInverse(Ring1, Ring2: VersAnneau): boolean; var Different: boolean; Cur1, Cur2: VersAnneau; begin if Ring1=nil then estInverse := Ring2=nil else if Ring2=nil then estInverse := false else begin Cur1 := Ring1; Cur2 := Ring2^.Precedent; repeat Different := Cur1^.Info<>Cur2^.Info; Cur1 := Cur1^.Suivant; Cur2 := Cur2^.Precedent; until Different or (Cur1=Ring1) or (Cur2=Ring2); estInverse := not Different and (Cur1=Ring1) and (Cur2=Ring2); end; { if } end; { estInverse }

http://cuisung.unige.ch/std/ex/7/4h.txt [23-09-2001 16:19:11]

Le chemin le plus court/Examen 30.6.1999

Le chemin le plus court Solution pour la question posée à l'examen écrit le 30.6.1999 contenu du FIFO étape

L1 en notation Scheme

1 2 3 4 5 3

() ((1)) () () ((2 1) (4 1)) ((4 1))

non défini non défini (1) (1) (1) (2 1)

4 5 3 4 5 3 4 5 3 4 5 3 4 (TROUVE)

((4 1)) ((4 1) (5 2 1)) ((5 2 1)) ((5 2 1)) ((5 2 1) (7 4 1)) ((7 4 1)) ((7 4 1)) ((7 4 1) (6 5 2 1)) ((6 5 2 1)) ((6 5 2 1)) ((6 5 2 1)) () ()

(2 1) (2 1) (4 1) (4 1) (4 1) (5 2 1) (5 2 1) (5 2 1) (7 4 1) (7 4 1) (5 2 1) (6 5 2 1) (6 5 2 1)

Le chemin le plus court est: 1 2 5 6 Wolfgang Müller Last modified: Thu Aug 19 00:11:24 MEST 1999

http://cuisung.unige.ch/std/ex/11/a_solution.html [23-09-2001 16:19:43]

13.4 exercice 3, solution

. Les parties importantes du code à réaliser sont: 1. Initialisation des coefficients (1 pt) 2. Parcours de l'espace des solutions (6 pts) 3. Fonction vérifiant si les coefficients trouvés produisent un H-code parfait (3 pts) 4. Boucle principale, testant toutes les solutions, minimisant la taille (2 pts) 1) procedure initialiseCoefficients; var i : integer; begin for i = 1 to LongueurMax do Coeff[i] := 0; end;

2) function incrementeCoefficients : boolean; begin while ( index < LongueurMax AND Coeff[index] = MaxCoeff ) do begin Coeff[index] := 0; index := index + 1; end; {while} if ( index > LongueurMax ) then begin incrementeCoefficients := false; else begin Coeff[index] := Coeff[index] + 1; index := 0; end; {if} end; {function}

3) function estParfaite : boolean; var i : integer, code : integer; begin for i = 1 to MaxIndice do tab[i] := false; for i = 1 to NbMots do begin code := H(Vocabulaire[i]); if ( tab[code] = true ) then begin estParfaite := false; exit function; end tab[code] := true; end; {for} end; {function}

4) begin for Taille = NbMots to TailleMax do begin initialiseCoefficients; while incCoeffs do if estParfaite then exit procedure; end; {while}

http://cuisung.unige.ch/std/ex/13/4c.sol.html (1 of 2) [23-09-2001 16:20:13]

13.4 exercice 3, solution

end; {for} { si on arrive la, aucune fonction parfaite n'a été trouvée. } end. {procedure chercheCoefficients} b. Les parties importantes du code a réaliser sont: 1. Comparaison des probabilités du mot à insérer et du mot se trouvant déjà dans la table (1 pt) 2. Remplacement du mot dans la table par le nouveau mot (si sa prob est supérieure) (1 pt) 3. Insertion du mot qui vient d'être remplacé (1 pt) function Insert( X : string ) : integer; var H0, hi : integer; temp : string; begin H0 := H(X); hi := H0; while ( T[hi] <> '' ) and ( T[hi] <> X ) do begin -----------------------------------------------------1) if ( P(X) > P(T[hi]) ) then begin 2)

temp := T[hi]; T[hi] := X; { solution 1 : simplement rappeler la fonction insert ... }

3a)

Insert( temp );

3b)

{ solution 2 : trouver la nouvelle valeur de hi et continuer... mais comme les collisions sont traitées de façon linéaire, cette partie est inutile dans ce cas. } X = temp;

else begin --------------------------------------------------------------------hi := (hi+1) mod MaxElements; if hi = H0 then begin writeln('tableau plein'); exit(program); end; end; end; if T[Hi] = '' then T[Hi] := X; Insert := hi; end;

http://cuisung.unige.ch/std/ex/13/4c.sol.html (2 of 2) [23-09-2001 16:20:13]

Structuration des Donn es Informatiques - 11.3, solution ex. 3

(question) . Si l'on adopte la convention que x->y signifie "x est plus jeune que y", on obtient le graphe suivant:

Si l'on adopte la convention que x->y signifie "x est plus vieux/vieille que y", on obtient le graphe suivant:

b. C Arc: A A l ligne vers colonne l n a = i d u est plus jeune que c r d e é e

J e a n

J e a n n e

J a c q u e s

M a r i e

P a u l

P i e r r e

Y v e s

Alice

F F F F F F F F V V

André

F F V F F F F F V F

Claude

F F F F F F F F V V

Jean

F F F F F F F V V F

Jeanne

F F F V F F F F F F

Jacques

F F F F V F F F V F

Marie

F F F F F V F F F F

http://cuisung.unige.ch/std/ex/11/3c.sol.html (1 of 2) [23-09-2001 16:20:56]

Structuration des Donn es Informatiques - 11.3, solution ex. 3

Paul

F F F F F F F F F F

Pierre

F F F F F F F V F F

Yves

F F F F F F F V F F

avec cette même matrice, on pourrait considérer que les arcs vont de la colonne vers la ligne et signifient "est plus vieux que" c. C Arc: A A l ligne vers colonne l n a = i d u est plus jeune que c r d e é e

J e a n

J e a n n e

J a c q u e s

M a r i e

P a u l

P i e r r e

Y v e s

Alice

F F F F F F F V V V

André

F F V F F F F V V V

Claude

F F F F F F F V V V

Jean

F F F F F F F V V F

Jeanne

F F F V F F F V V F

Jacques

F F F V V F F V V F

Marie

F F F V V V F V V F

Paul

F F F F F F F F F F

Pierre

F F F F F F F V F F

Yves

F F F F F F F V F F

Cette fermeture transitive permet de facilement trouver qui est certainement plus jeune ou plus vieux qu'une personne donnée. Pour trouver qui est certainement plus vieux que X, il suffit de regarder la ligne contenant X et chercher les colonnes où il y a un "V". Pour trouver qui est certainement plus jeune que X, il suffit de regarder la colonne contenant X et chercher les lignes contenant un "V" On ne peut par contre pas dire qui est lel plus vieux ou le plus jeune, car nous ne sommes pas en présence d'une relation d'ordre totale et il n'y a peut-être aucun moyen de dire qui est le plus vieux (la plus vielle) ou le (la) plus jeune. En l'occurrence, Alice, André et Marie sont les trois plus jeunes, mais on ne peut rien dire sur leurs ages respectifs. d. Marie, Alice, André, Jacques, Claude, Yves, Jeanne, Jean, Pierre, Paul. D'autres possibilités consisteraient à permuter Alice, Marie et André (toutes les permutations sont possibles puisqu'il n'y a aucune relation directe entre eux).

http://cuisung.unige.ch/std/ex/11/3c.sol.html (2 of 2) [23-09-2001 16:20:56]

Structuration des Donn es Informatiques - 14.3, solution ex. 4

(question) . Insertion de 1, puis de 2: 1

- 1 2

Insertion de 3, puis de 6, puis de 7: 2

2

3

1

-

3

1

3 6

1 2

6 7

Insertion de 4, puis de 5: 3

6

3

6

1 2

4

7

1 2

4 5

7

Insertion de 8: 3 1 2

6 4 5

7 8

Insertion de 9: 6 3 1 2

8 4 5

7

9

b. Si chaque page occupe 512 octets et qu'une page contient au minimum 1 donnée et au maximum 2 données (b-arbre d'ordre 1), le cas le plus défavorable est quand toutes les pages ne contiennent qu'une donnée chacune et le cas le plus favorable est lorsque toutes les pages contiennent deux données chacune. L'espace utilisé est respectivement: ❍ 10'000 données et 1 donnée/page => 10'000 pages = 10'000*512 octets ❍ 10'000 données et 2 données/page => 5'000 pages = 5'000*512 octets c. Quand les pages sont pleines, les différents niveaux contiennent: niveau nb. pages du niveau nb. pages cumulés 1

1

1

2

3

4

3

9

13

4

27

40

http://cuisung.unige.ch/std/ex/14/3d.sol.html (1 of 2) [23-09-2001 16:21:50]

Structuration des Donn es Informatiques - 14.3, solution ex. 4

5

81

121

6

243

364

7

729

1093

8

2187

3280

9

6561

9841

Quand les pages ne sont qu'à moitié pleines, les différents niveaux contiennent: niveau nb. pages du niveau nb. pages cumulés 1

1

1

2

2

3

3

4

7

4

8

15

5

16

31

6

32

63

7

64

127

8

128

255

9

256

511

10

512

1'023

11

1024

2'047

12

2048

4'095

13

4096

8'191

14

8192

16'383

On voit donc qu'il faut au minimum 9 niveaux pour avoir 5'000 pages pleines et au plus 14 niveaux pour avoir 10'000 pages à moitié pleines

http://cuisung.unige.ch/std/ex/14/3d.sol.html (2 of 2) [23-09-2001 16:21:50]

Structuration des Donn es Informatiques - 13.4, solution exercice 2

(question) Pour le tableau ci-dessous, on a supposé que la position initiale d'un mot est calculée comme étant H0(K)=(H(K) mod 15)+1 indice

contenu

Nb.collisions positions examinées

1

lumiere

0

1

2

soudaine

1

9, 2

3

une

0

3

4

etait

0

4

5

traversa

3

11, 4, 12, 5

6

qu

0

6

7

du

0

7

8

la

0

8

9

si

1

7, 9

10

illumination 0

10

11

jour

0

11

12

son

2

6, 9, 12

13

forte

0

13

14

esprit

0

14

15

http://cuisung.unige.ch/std/ex/13/4b.sol.html [23-09-2001 16:22:27]

http://cuisung.unige.ch/std/ex/8/2c.txt

program Lexico; type VersNoeud= ^Noeud; Noeud= record Desc: array['a'..'z'] of VersNoeud; Complet: boolean; end; { Noeud } var Dico: VersNoeud; Longueur: integer; function Lecture(NomFichier: string): VersNoeud; var F: text; Status: integer32; i: integer; l: char; Mot: string; Rac, P: VersNoeud; begin (* Lecture *) new(Rac); open(F, NomFichier,'old', Status); if Status <> 0 then begin writeln('probleme pour ouvrir le fichier'); halt; end; reset(F); while not eof(F) do begin Read(F,Mot); P:= Rac; (* for i := 1 to length(Mot) do begin *) i := 1; while Mot[i]<> ' ' do begin if P^.Desc[Mot[i]] = nil then begin new(P^.Desc[Mot[i]]); with P^.Desc[Mot[i]]^ do begin Complet := false; for l:='a' to 'z' do Desc[l] := nil; end; (* with *) end; (* if *) P:= P^.Desc[Mot[i]]; i:= i+1; end; (* while *) P^.Complet := true; readln(F); end; (* while not eof *) Lecture := Rac; end; (* Lecture *) function NbMots(Longueur: integer; Dico: VersNoeud):integer; var Nb: integer; procedure Parcours1Niveau(Rac: VersNoeud; NiveauxRestants: integer); var Reste: integer; l: char; begin (* Parcours1Niveau *) if Rac <> nil then if NiveauxRestants = 0 then begin if Rac^.Complet then Nb := succ(Nb) end else begin if NiveauxRestants = -1 then begin Reste := NiveauxRestants;

http://cuisung.unige.ch/std/ex/8/2c.txt (1 of 2) [23-09-2001 16:23:02]

http://cuisung.unige.ch/std/ex/8/2c.txt

if Rac^.Complet then Nb := succ(Nb) end else Reste := pred(NiveauxRestants); for l := 'a' to 'z' do if Rac^.Desc[l] <> nil then Parcours1Niveau(Rac^.Desc[l], Reste); end; (* else *) end; (* Parcours1Niveau *) begin (* NbMots *) Nb := 0; if Longueur = 0 then Parcours1Niveau(Dico, -1) else Parcours1Niveau(Dico, Longueur); NbMots := Nb; end; (* NbMots *) begin (* Dico := PseudoLecture; *) readln(Longueur); Dico := Lecture('990229.dat'); writeln('Nb. mots de longueur', Longueur, '=', NbMots(Longueur,Dico)); end.

http://cuisung.unige.ch/std/ex/8/2c.txt (2 of 2) [23-09-2001 16:23:02]

http://cuisung.unige.ch/std/ex/11/5b.txt

procedure TriTopoInverse(LeGraphe: Graphe); const MaxNbSommets=20; var i, CmptrVisite, IndexSommet : 0..MaxNbSommets; NumDOrdre : array[1..MaxNbSommets] of integer; Parcouru:array[1..MaxNbSommets] of boolean; NbSommets: integer; procedure Visite (IndexSommet : integer); var AutreSommet : integer; Voisins: SerieDeSommets; begin CmptrVisite := CmptrVisite + 1; NumDOrdre[IndexSommet] := CmptrVisite; Parcouru[IndexSommet] := true; Voisins := SommetsVoisins(IndexSommet, LeGraphe); while not FinDeSerie(Voisins) do begin AutreSommet := ExtraitSommet(Voisins); if Parcouru[AutreSommet] then writeln(NomSommet(AutreSommet,LeGraphe), ' fait partie d''un cycle') else if NumDOrdre[AutreSommet] = 0 then Visite (AutreSommet); end; { while } Parcouru[IndexSommet] := false; write(NomSommet(IndexSommet,LeGraphe)); end; { Visite } begin { TriTopoInverse } NbSommets := NombreDeSommets(LeGraphe); CmptrVisite := 0; for IndexSommet := 1 to NbSommets do NumDOrdre[IndexSommet]:=0; for IndexSommet := 1 to NbSommets do if NumDOrdre[IndexSommet]=0 then begin for i := 1 to NbSommets do Parcouru[i] := false; Visite (IndexSommet); end; { if } end; { TriTopoInverse }

http://cuisung.unige.ch/std/ex/11/5b.txt [23-09-2001 16:23:32]

Structuration des Données Informatiques - 14.3, solution 3

Nous allons considérer deux cas, suivant que l'on considère qu'une page ne contient que les données et les pointeurs vers les pages descendantes ou que l'on compte, en plus, un compteur indiquant le nombre effectif de données dans la page

Cas où une page ne contient pas de compteur . Puisqu'il y a un pointeur de plus que de données, le nombre de données par page est: (1024-4) div (47+4) = 20 l'ordre du B-arbre est donc de 10 et nous arondissons celui du B*-arbre à 14. b. Pour le B-arbre: ❍ La page racine peut contenir au minimum 1 donnée, reste 999'999 données à répartir au minimum 10 par page. Le nombre total de pages, quand celles-ci sont remplies au minimum est: 1+(999'999 div 10) = 100'000 pages (soit 100'000 KiloOctets) ❍ Si toutes les pages sont entièrement remplies, le nombre total de pages est: 1'000'000 div 20 = 50'000 pages (soit 50'000 KiloOctets) Pour le B*-arbre: ❍ La page racine peut contenir au minimum 1 donnée, reste 999'999 données à répartir au minimum 14 par page. Le nombre total de pages, quand celles-ci sont remplies au minimum est: 1+(999'999 div 14) = 71'429 pages (soit 71'429 KiloOctets) ❍ Si toutes les pages sont entièrement remplies, le nombre total de pages est le même que pour le B-arbre, soit 50'000 pages. c. Pour le B-arbre: ❍ Quand les pages sont remplies au minimum, les niveaux successifs contiennent le nombre de pages suivant: 1, 2, 22, 242, 2662, 29'282, 322'102

❍

Il faut donc au moins 7 niveaux pour arriver à un total de 100'000 pages Quand les pages sont remplies au maximum, les niveaux successifs contiennent le nombre de pages suivant: 1, 21, 441, 9'261, 194'481 Il faut donc au moins 5 niveaux pour arriver à un total de 50'000 pages

Pour le B*-arbre: ❍ Quand les pages sont remplies au minimum, les niveaux successifs contiennent le nombre de pages suivant: 1, 2, 30, 450, 6'750, 101'250 Il faut donc au moins 6 niveaux pour arriver à un total de 71'429 pages

http://cuisung.unige.ch/std/ex/14/3c.sol.html (1 of 2) [23-09-2001 16:24:06]

Structuration des Données Informatiques - 14.3, solution 3

❍

Quand les pages sont remplies au maximum, le nombre de niveaux est le même que pour le B-arbre, soit 5 niveaux.

Cas où une page contient un compteur .

http://cuisung.unige.ch/std/ex/14/3c.sol.html (2 of 2) [23-09-2001 16:24:06]

solution de l'exercice 1, section 8.3

. la constrution est très similaire à celle d'un arbre binaire de tri, si ce n'est qu'à chaque fois qu'un noeud n'a pas de descendant droit, son pointeur droit pointe vers l'ancêtre dont le contenu est immédiatement supérieur au contenu du noeud courant, selon l'ordre de tri:

b. la suppression se fait de manière similaire à un arbre de tri: si l'élément à détruire a deux descendants, on échange le contenu du noeud à détruire avec celui du noeud le plus à droite de son sous-arbre gauche (ou le plus à gauche de son sous-arbre droit), puis l'on détruit ce dernier:

http://cuisung.unige.ch/std/ex/8/3a.sol.html [23-09-2001 16:25:42]

http://cuisung.unige.ch/std/ex/15/1b.txt

procedure AjouteRegle(Table:TableDecision;R:integer;var NewTable:TableDecision); { AjouteRegle insere la regle R de la table "Table" dans la table "NewTable" en supprimant la premiere condition } var c: integer; begin {AjouteRegle} NewTable.NbRegles := succ(NewTable.NbRegles); for c:=2 to Table.NbConditions do NewTable.ValCond[NewTable.NbRegles,c-1] := Table[R,c]; end; {AjouteRegle} function ConstruitArbre(Table: TableDecision): PtrNoeud; var NewTable: TableDecision; P: PtrNoeud; begin { ConstruitArbre } { si la table n'a pas de conditions, l'arbre sera vide } if Table.NbConditions <= 0 then ConstruitArbre := nil else begin { on va traiter la 1ere condition } new(P); with P^ do begin Feuille := false; TxtCond := Table.TxtConditions[1]; Vrai := nil; Faux := nil; end; {with} { si la table n'a qu'une seule condition, on cree directement les noeuds descendants (il ne devrait rester qu'au plus 2 regles dans la table) } if Table.NbConditions = 1 then begin for R := 1 to Table.NbRegles do if Table.ValCond[R,1] <> Faux then begin new(P^.Vrai); with P^.Vrai^ do begin Feuille := true; for a := 1 to Table.NbActions do Actions[a] := Table.Agir[R,a]; end; {with} end; if Table.ValCond[R,1] <> Vrai then begin new(P^.Faux); with P^.Faux^ do begin Feuille := true; for a := 1 to Table.NbActions do Actions[a] := Table.Agir[R,a]; end; {with} end end else begin { si la table a plus qu'une condition, on va creer deux sous-tables avec chacune une condition de moins que la table courante } NewTable.NbConditions := pred(Table.NbConditions); (* on construit la sous-table pour le cas ou la condition 1 est fausse *) NewTable.NbRegles := 0; for R := 1 to Table.NbRegles do if Table.ValCond[R,1] <> Vrai then AjouteRegle(Table, R, NewTable); { on appelle recursivement ConstruitArbre pour traiter cette sous-table } P^.Faux := ConstruitArbre(NewTable); (* on construit la sous-table pour le cas ou la condition 1 est vrai *) NewTable.NbRegles := 0; for R := 1 to Table.NbRegles do if Table.ValCond[R,1] <> Faux then AjouteRegle(Table, R, NewTable); { on appelle recursivement ConstruitArbre pour traiter cette sous-table } P^.Vrai := ConstruitArbre(NewTable); end

http://cuisung.unige.ch/std/ex/15/1b.txt (1 of 2) [23-09-2001 16:27:44]

http://cuisung.unige.ch/std/ex/15/1b.txt

end; end; { ConstruitArbre }

http://cuisung.unige.ch/std/ex/15/1b.txt (2 of 2) [23-09-2001 16:27:44]

Structures de Données, 2ème contrôle continu 1998, solution à la question 1

Ce qui suit est basé sur l'hypothèse que les blocs de données ne contiennent pas de référence à un bloc de débordement 1.a) Si les blocs de données ne contiennent pas de référence à un bloc de débordement, le plus petit multiple de 512 qui soit aussi multiple de 80 est 2'560. 1.b) on a 2'560 octets/bloc et 80 octets/donnée => 1 bloc=(2'560/80) données=32 données. 1.c) round(32*80)/100) = round(25,6)=> il faudra 26 données/bloc. 1.d) ❍

❍

Avec 26 données/bloc, 100'000 données occuperont (100'000/26) =3'847 blocs de données une paire (clé+réf. à une page) occupe 12 octets => 1 bloc d'index de 2'560 octets peut contenir 2'560/12 =213 paires clé+réf.

❍

la couche d'index la plus basse doit contenir 3'847/213 =19 blocs d'index

❍

la couche immédiatement supérieure contiendra 18/213 =1 bloc d'index le nombre total de blocs = 3'847 + 19 + 1 = 3'867 blocs et comme chaque bloc occupe 2'560 octets => la place disque occupée = (3'867*2'560) octets = 9'899'520 octets.

❍

1.e) l'arborescence d'index a 2 niveaux 1.f) niveau 1: 1 bloc niveau 2: 19 blocs 1.g) 3'847 blocs de données Si l'on prend l'hypothèse que les blocs de données contiennent chacun une référence à un bloc de débordement, il ne peut pas y avoir de solution à la question 1.a, c'est-à-dire qu'il n'y a pas de taille de bloc de données qui permette de ne pas avoir d'espace disque inutilisé. Par contre, avec 19 données et des blocs de 1'536 octets on aura le plus petit gaspillage possible (12 octets). Pour s'en convaincre, on peut démontrer qu'il suffit d'examiner les 32 premiers multiples de 80 et calculer le nombre de pages de 512 octets qui permette de les contenir. En effet, si (n*80) + 4 = m*512 + gaspillage alors ((n+32) *80) + 4 = ((m+5)*512) + gaspillage

http://cuisung.unige.ch/std/ex/14/2b.sol.html (1 of 2) [23-09-2001 16:28:47]

Structures de Données, 2ème contrôle continu 1998, solution à la question 1

En d'autres termes, pour n données/bloc et (n+32) données/bloc, on a le même gaspillage (en valeur absolue!). 1.a) avec des blocs de 1'536 octets, on n'a que 12 octets de gaspillage 1.b) on a 1536 octets/bloc et 80 octets/donnée => 1 bloc=(1'536-4) div 80=19 données/bloc 1.c) round(19*80/100)=round(15,2)=15 données/bloc 1.d) ❍

avec 15 données/bloc, 100'000 données occuperont (100'000/15) =6'667 blocs de données une paire (clé+réf. à une page) occupe 12 octets => 1 bloc d'index de 1'536 octets peut contenir 1'536/12 =128 paires clé+réf.

❍

la couche d'index la plus basse doit contenir 6'667/128 =53 blocs d'index

❍

la couche immédiatement supérieure contiendra 53/128 =1 bloc d'index le nombre total de blocs = 6'667 + 53 + 1 = 6'721 blocs et comme chaque bloc occupe 1'536 octets => la place disque occupée = (6'721*1'536) octets = 10'323'456 octets.

❍

❍

1.e) l'arborescence d'index a 2 niveaux 1.f) niveau 1: 1 bloc niveau 2: 53 blocs 1.g) 6'667 blocs de données

http://cuisung.unige.ch/std/ex/14/2b.sol.html (2 of 2) [23-09-2001 16:28:47]

Structures de données: 2ème contrôle continu 1998, solution à la question 2

. B-arbre résultant de l'insertion de la valeur L dans le B-arbre initial:

b. B-arbre résultant de la suppression de la valeur C dans le B-arbre initial:

c. B-arbre résultant de l'insertion de la valeur Z dans le B-arbre initial:

d. B-arbre résultant de la suppression de la valeur S dans le B-arbre initial:

http://cuisung.unige.ch/std/ex/14/3g.sol.html (1 of 3) [23-09-2001 16:29:58]

Structures de données: 2ème contrôle continu 1998, solution à la question 2

autre solution:

e. B-arbre résultant de la suppression de la valeur P dans le B-arbre initial:

autre solution:

http://cuisung.unige.ch/std/ex/14/3g.sol.html (2 of 3) [23-09-2001 16:29:58]

Structures de données: 2ème contrôle continu 1998, solution à la question 2

http://cuisung.unige.ch/std/ex/14/3g.sol.html (3 of 3) [23-09-2001 16:29:58]

Structuration des Données Informatiques - 10.3, solution 2

3.a) On peut imaginer deux genres de solution. Dans la première, on utilise un graphe dont les arcs ne sont ni orientés, ni pondérés. Chaque noeud du graphe représente une case de la carte, et le nombre correspondant à son type de terrain est stocké dans l'enregistrement du noeud. Il y a un arc de chaque noeud à chacun de ses voisins accessibles. Il n'est pas nécessaire de représenter les cases impraticables dans le graphe. La représentation de la case B9 et ses voisines serait

L'autre genre de solution utilise un graphe dont les arcs sont orientés et pondérés. Un arc représente le coût d'aller d'une case à une de ses voisines (c'est-à-dire le coût pour arriver à la case voisine). La partie du graphe autour de la case B9 serait

3.b) Une matrice de connectivité serait la façon la plus efficace pour stocker les arcs, parce que leur densité (NbSommets*~4/NbSommets^2 = ~0.04) dépasse 3%, en fait. Puisque le nombre de noeuds est constant, on peut utiliser un tableau pour les stocker. Pour la première structure proposée ci-dessus, on pourrait utiliser les structures suivantes: const MaxNoeuds = 100; {Pour la carte donnée} type NoeudIntervalle = 1..MaxNoeuds; var {Matrice de connectivité} Connexe: packed array[NoeudIntervalle, NoeudIntervalle] of boolean; {On ne stocke que le coût associé a chaque noeud} CoutDeNoeud: array[NoeudIntervalle] of integer; 3.c) Pour trouver le chemin le plus court, j'utiliserai la recherche en largeur, parce qu'elle évite de visiter les chemins plus longs que le chemin recherché. Mais ce problème est différent: on ne cherche pas le chemin le plus court, on cherche le chemin du moindre coût. On ne peut pas dire qu'on a trouvé le bon chemin dès qu'on arrive au point B - il est possible

http://cuisung.unige.ch/std/ex/10/3b.sol.html (1 of 3) [23-09-2001 16:31:35]

Structuration des Données Informatiques - 10.3, solution 2

qu'il y ait un autre chemin, peut-être plus long, mais moins coûteux. J'utiliserais donc la recherche en profondeur avec "back-tracking" ainsi que quelques petites modifications: à tout instant, je garde le chemin du moindre coût déjà trouvé (dans un tableau, p. ex.), ainsi que le coût lui-même. Si le coût du chemin qu'on est en train de parcourir dépasse le coût du meilleur chemin déjà trouvé jusqu'à ce noeud là, on peut arrêter de suivre ce chemin. Sinon, quand on arrive au noeud d'arrivée, si le coût du chemin suivi est inférieur à celui du meilleur chemin déjà trouvé, on les échange. On continue jusqu'à ce qu'on ait essayé (peut être incomplètement) tous les chemins possibles. 3.d) Le programme principal: Lire les données; Créer le matrice de connectivité; Obtenir les noeuds de départ et arrivée; Initialiser les variables: MeilleurCoût := MaxNoeuds*MaxNoeuds*MaxCoûtDeNoeud; CheminTrouvé := Faux; Mettre CoûtJusquIci[i] à zero pour tous les noeuds i; TrouverCheminDuMoindreCoût(0, 1, NoeudDeDepart, NoeudDArrivee); si CheminTrouvé alors Ecrire MeilleurChemin et son coût sinon Ecrire "Pas de chemin entre NoeudDeDepart et NoeudDArrivée!" La procédure TrouverCheminDuMoindreCoût, qui est récursive: procedure TrouverCheminDuMoindreCoût(Coût, NombreDEtapes, Noeud, NoeudDArrivee); begin {Ajoute le noeud actuel au chemin qu'on est en train d'explorer} CeChemin[NombreDEtapes] := Noeud; inc(NombreDEtapes); {Est-ce qu'on a trouvé le noeud d'arrivée?} si Noeud = NoeudDArrivée begin CheminTrouvé := Vrai; si Coût < MeilleurCoût {On a trouvé un meilleur chemin, donc on le stocke} begin MeilleurCout := Coût; LongueurDuChemin := NombreDEtapes - 1; Copier CeChemin dans MeilleurChemin; end; end; sinon {ce n'est pas le noeud d'arrivée} begin {Ajoute le coût du noeud actuel au coût du chemin qu'on explore, et le stocke pour le noeud actuel} Coût := Coût + CoûtDeNoeud[Noeud]; CoûtJusquIci[Noeud] := Coût; Pour tous les noeuds i faire si Connexe[Noeud, i] et ((CoûtJusquIci[i] = 0) ou {c'est-à-dire pas encore visité} (Coût + CoûtDeNoeud[i] < CoûtJusquIci[i])) {Si on a déjà trouvé ce noeud en passant par un chemin moins coûteux, on n'étend plus ce chemin. Cette astuce réduit beaucoup le coût de la recherche.}

http://cuisung.unige.ch/std/ex/10/3b.sol.html (2 of 3) [23-09-2001 16:31:35]

Structuration des Données Informatiques - 10.3, solution 2

TrouverCheminDuMoindreCoût(Coût, NombreDEtapes, i, NoeudDArrivée); {sinon la procédure retourne, et le "back-tracking" commence} end; end;

http://cuisung.unige.ch/std/ex/10/3b.sol.html (3 of 3) [23-09-2001 16:31:35]

http://cuisung.unige.ch/std/ex/7/4f.txt

procedure Paragraphes(UnTexte: VersLigne; var ChainePara: PtrPara); var P: VersLigne; Para: PtrPara; L: integer; NotDone: boolean; begin { Paragraphes } ChainePara := nil; P := UnTexte; L := 1; repeat { determine s'il y a lieu de sauter des lignes vides } if P=nil then NotDone := false else NotDone := P^.Texte=''; { tant que NotDone est vrai, on saute des lignes vides } while NotDone do begin P := P^.LigneSuivante; L := L+1; if P=nil then NotDone := false else NotDone := P^.Texte=''; end; { while } { on a fini de sauter des lignes vides, reste-t-il encore qq chose?} if P<>nil then begin { on est sur le debut d'une serie de lignes non vides, il faut donc creer un nouveau descripteur de paragraphes } if ChainePara = nil then begin new(ChainePara); Para := ChainePara; Para^.Preced := nil; end else begin new(Para^.Suivant); Para^.Suivant^.Preced := Para; Para := Para^.Suivant; end; Para^.Suivant := nil; Para^.Debut := L; NotDone := true; { maintenant, cherche la fin du bloc de lignes non vides } while NotDone do begin P := P^.LigneSuivante; L := L+1; if P=nil then NotDone := false else NotDone := P^.Texte<>'' end; { while } Para^.Fin := L-1; end; { if } until P = nil; end; { Paragraphes }

http://cuisung.unige.ch/std/ex/7/4f.txt [23-09-2001 16:31:54]

http://cuisung.unige.ch/std/ex/7/1a.txt

procedure Insertion( Valeur, NumChaine : integer); {Procedure permettant d'affecter une valeur a la liste qui se trouvre a NumChaine dans le tableau} var Courant,Entete: PtrNoeud; begin if (NumChaine> MaxNbSommets) OR (NumChaine < 1) then begin writeln('L''indice du tableau doit etre entre 1 et ', MaxNbSommets); readln; halt end else begin {Creation du noeud a inserer} New(Entete); with Entete^ do begin Donnee:= Valeur; Suivant:= nil; end; { with } if TabElement[NumChaine].Chaine = NIL then TabElement[NumChaine].Chaine:= Entete else begin Courant:= TabElement[NumChaine].Chaine; while Courant^.Suivant<>NIL DO Courant:= Courant^.Suivant; {Insertion de Entete dans Courant} Courant^.Suivant := Entete; end; { if TabElement... else } TabElement[NumChaine].Taillechaine := succ(TabElement[NumChaine].Taillechaine); end; { if (NumChaine> MaxNbSommets)... else } end; { Insertion } Procedure afficher; {Parcourir la Chaine et afficher le contenu de la Chaine} var j: integer; PtCourant: PtrNoeud; begin { afficher } for j:= 1 to MaxNumChaine do begin writeln('TabElement[',j,']'); PtCourant:= TabElement[j].Chaine; while PtCourant <> nil do begin writeln(PtCourant^.Donnee); PtCourant:= PtCourant^.Suivant; end; { while } readln; end; { for } end; { afficher }

http://cuisung.unige.ch/std/ex/7/1a.txt [23-09-2001 16:32:13]

http://cuisung.unige.ch/std/ex/7/4g.txt

Procedure ChercherInsertion(Valeur: Integer; VAR NoeudInsertion: PtrNoeud); {Permet de determiner le noeud d'insertion pour la valeur donnee: NoeudInsertion retourne NIL, si Valeur existe deja dans l' anneau} Var Courant: PtrNoeud; begin Courant:= Entete^.Suivant; while (Courant <> Entete) and (Courant^.Donnee < Valeur) do Courant:= Courant^.Suivant; if Courant = Entete then NoeudInsertion:= Courant^.Precedent else {Courant^.Donnee >= Valeur} if Courant^.Donnee = Valeur then NoeudInsertion := NIL else NoeudInsertion := Courant^.Precedent; end; {Chercher Insertion} Procedure RangerValeur(Valeur: Integer); {Permet de ranger une valeur donnee dans l'anneau trié} VAR NInsertion, Nouveau : PtrNoeud; begin AnneauVide := False; New(Nouveau); Nouveau^.Donnee:= Valeur; if Entete=nil then InsererNoeud(Nouveau,Entete) else begin ChercherInsertion(Valeur, NInsertion); if (NInsertion = Entete) and (Entete^.Donnee < Valeur) then Entete := Nouveau; {On changera l'entete si la valeur donnee est plus grande que celle de l'entete} if NInsertion <> NIL then InsererNoeud(Nouveau,NInsertion) else writeln('Cette Valeur existe deja dans la liste'); end; { if Entete=nil ... else } end;{RangerValeur}

http://cuisung.unige.ch/std/ex/7/4g.txt [23-09-2001 16:32:46]

http://cuisung.unige.ch/std/ex/8/1c.txt

a) Arbre('-', Arbre('*', Arbre('-', Feuille('a'), Arbre('+', Feuille('b'), Feuille('c') ) ), Feuille('d') ), Arbre('/', Arbre('-', Feuille('e'), Feuille('f') ), Arbre('*', Feuille('g'), Feuille('h') ) ) ) b) type Noeud = record Operateur: char; G, D: PtrNoeud; end; { Noeud } function Feuille(Contenu: char): PtrNoeud; var P: PtrNoeud; begin new(P); with P^ do begin Operateur := Contenu; G := nil; D := nil; end; {with} Feuille:=P; end; { Feuille } function Arbre(Contenu: char; Gauche, Droit: PtrNoeud): PtrNoeud; var P: PtrNoeud; begin new(P); with P^ do begin Operateur := Contenu; G := Gauche; D := Droit; end; {with} Arbre:=P; end; { Arbre }

http://cuisung.unige.ch/std/ex/8/1c.txt [23-09-2001 16:33:07]

http://cuisung.unige.ch/std/ex/10/3a.sol.txt

procedure DFS( LeGraphe: Graphe); var CmptrVisite, IndexSommet : 0..MaxNbSommets; NumeroDOrdre: array[1..MaxNbSommets] of integer; procedure Visite (IndexSommet : integer); var Voisins: SerieDeSommets; Voisin: integer; begin CmptrVisite := CmptrVisite + 1; NumeroDOrdre[IndexSommet]:=CmptrVisite; write(NomSommet(IndexSommet,LeGraphe), ' '); Voisins := SommetsVoisins(IndexSommet,LeGraphe); Voisin := 0; if not FinDeSerie(Voisins) then begin repeat if Voisin=0 then Voisin := PremierSommet(Voisins) else Voisin := SommetSuivant(Voisins); if NumeroDOrdre[Voisin]=0 then Visite (Voisin); until FinDeSerie(Voisins); end; { if not FinDeSerie } end; { Visite } begin { DFS } CmptrVisite := 0; for IndexSommet:= 1 to NombreDeSommets(LeGraphe: Graphe) do NumeroDOrdre[IndexSommet]:=0; for IndexSommet := 1 to NombreDeSommets(LeGraphe: Graphe) do if NumeroDOrdre[IndexSommet] = 0 then Visite (IndexSommet) end; { DFS }

http://cuisung.unige.ch/std/ex/10/3a.sol.txt [23-09-2001 16:33:39]

http://cuisung.unige.ch/std/ex/10/4a.sol.txt

procedure Imprime(LeDico: VersNoeud); const TailleFile = 100; type Objet=record Mot: String80; Place: VersNoeud; end; { Objet } FileCirculaire=record Element: array[0..TailleFile] of Objet; IndexIn, IndexOut: 0..TailleFile; Plein:boolean; end; { FileCirculaire } var MaFile: FileCirculaire; Obj: Objet; procedure Avance(N: VersNoeud; S: String80); var c:char; Splus:String80; l: integer; O: Objet; begin { Avance } if N^.Complet then writeln(S); Splus := S; l := length(Splus)+1; Insert(' ',Splus, l); for c := 'a' to 'z' do if N^.Desc[c]<>nil then begin Splus[l] := c; O.Mot := Splus; O.Place := N^.Desc[c]; Met(MaFile, O); end; { if N^.Desc[c]<>nil } end; { Avance } begin { Imprime } MaFile.IndexIn := 0; MaFile.IndexOut := 0; MaFile.Plein := false; if LeDico<>nil then Avance(LeDico, ''); while not Vide(MaFile) do begin Ote(MaFile, Obj); Avance(Obj.Place, Obj.Mot); end; {while} end; { Imprime }

http://cuisung.unige.ch/std/ex/10/4a.sol.txt [23-09-2001 16:33:54]

Structuration des Données Informatiques - 13.4, solution 1

indice du tableau

chaîne associée valeur entre () = H2(Mot)

0 1 2 3 4 5 6 7 8 9 10

a (4)->du (12)->quatre (16) sont (7)->premier (14) aurait (2)->un (9)->lesquels (17) cycle (2) les (8)->atteint (12)->y (13) oral (1)->le (7) examens (5)->pour (10) n (5)->examen(6) si (6)->admis(13) note (2)->chaque (17)->qu (22) subir (3)

http://cuisung.unige.ch/std/ex/13/4a.sol.html [23-09-2001 16:34:06]

http://cuisung.unige.ch/std/ex/15/1a.sol.txt

procedure Extension(Entree: TableDecision; var Sortie: TableDecision); var Regle: 0..MaxNbRegles; Condition, Cond: 0..MaxNbCond; Action: 0..MaxNbActions; begin { Extension } Sortie.NbConditions := Entree.NbConditions; Sortie.NbRegles := Entree.NbRegles; Sortie.NbActions := Entree.NbActions; for Regle := 1 to Entree.NbRegles do begin for Condition := 1 to Entree.NbConditions do Sortie.ValCond[Regle,Condition] := Entree.ValCond[Regle,Condition]; for Action := 1 to Entree.NbActions do Sortie.Agir[Regle,Action] := Entree.Agir[Regle,Action]; end; { for } Regle := 1; while Regle <= Sortie.NbRegles do begin for Cond := 1 to Sortie.NbConditions do if Sortie.ValCond[Regle,Cond] = Indetermine then begin Sortie.ValCond[Regle,Cond] := Vrai; Sortie.NbRegles := succ(Sortie.NbRegles); for Condition := 1 to Sortie.NbConditions do Sortie.ValCond[Sortie.NbRegles,Condition] := Sortie.ValCond[Regle,Condition]; Sortie.ValCond[Sortie.NbRegles,Cond] := Faux; for Action := 1 to Sortie.NbActions do Sortie.Agir[Sortie.NbRegles,Action] := Sortie.Agir[Regle,Action]; end; { if } Regle := succ(Regle); end; { while } end; { Extension }

http://cuisung.unige.ch/std/ex/15/1a.sol.txt [23-09-2001 16:34:20]

http://cuisung.unige.ch/std/ex/7/4d.txt

procedure EchangeLignes(var UnTexte: VersLigne; NoLigne1,NoLigne2:integer); var Ligne, L1, L2, L1Suiv, L2Pred: VersLigne; No: integer; begin { EchangeLignes } { recherche des pointeurs correspondant aux numeros de ligne donnes } Ligne := UnTexte; L1 := nil; L2 := nil; No := 0; while (Ligne<>nil) and ( (L1=nil) or (L2=nil)) do begin No := No + 1; if No = NoLigne1 then L1 := Ligne; if No = NoLigne2 then L2 := Ligne; Ligne := Ligne^.LigneSuivante; end; { while } { validation des parametres } if (L1=nil) or (L2=nil) then begin if L1=nil then writeln('Le numero de ligne ',NoLigne1, ' n''est pas dans l''intervalle 1..',No); if L2=nil then writeln('Le numero de ligne ',NoLigne2, ' n''est pas dans l''intervalle 1..',No); end else if NoLigne1<>NoLigne2 then begin { on arrive ici si les parametres fournis sont valides et differents } { pour faciliter le traitement on va s'assurer que L1 pointe toujours sur un element qui precede celui pointe par L2 } if NoLigne1 > NoLigne2 then begin Ligne := L1; L1 := L2; L2 := Ligne; end; { ici, on procede a l'echange proprement dit } if L1=UnTexte then UnTexte := L2 else L1^.LignePrecedente^.LigneSuivante := L2; L2Pred := L2^.LignePrecedente; L2^.LignePrecedente := L1^.LignePrecedente; L1Suiv := L1^.LigneSuivante; L1^.LigneSuivante := L2^.LigneSuivante; if L2^.LigneSuivante <> nil then L2^.LigneSuivante^.LignePrecedente := L1; if L1Suiv=L2 then begin L2^.LigneSuivante := L1; L1^.LignePrecedente := L2 end else begin L2^.LigneSuivante := L1Suiv; L1^.LignePrecedente := L2Pred; L2Pred^.LigneSuivante := L1; L1Suiv^.LignePrecedente := L2; end; { if L1Suiv=L2 } end; { if } end; { EchangeLignes } procedure InverserLignes(var UnTexte: VersLigne);

http://cuisung.unige.ch/std/ex/7/4d.txt (1 of 2) [23-09-2001 16:34:35]

http://cuisung.unige.ch/std/ex/7/4d.txt

var Ligne, Tmp: VersLigne; begin { InverserLignes } Ligne := UnTexte; while Ligne<>nil do begin Tmp := Ligne^.LigneSuivante; Ligne^.LigneSuivante := Ligne^.LignePrecedente; Ligne^.LignePrecedente := Tmp; UnTexte := Ligne; Ligne := tmp; end; { while } end; { InverserLignes }

http://cuisung.unige.ch/std/ex/7/4d.txt (2 of 2) [23-09-2001 16:34:35]

Structuration des Données Informatiques - 7.4, solution de l'exercice 5

1. la chaîne 2 -> 0 -> 1 -> 1 -> -3 produira 2->1->1->-3->0->0->0->0->0->0->0... avec la valeur 0 qui se répète à l'infini. 2. la chaîne 3 -> -1 -> 2 -> -1 -> -3 produira la séquence 3->-1->2->-3->-1->... qui se répète à l'infini.

http://cuisung.unige.ch/std/ex/7/4e.sol.html [23-09-2001 16:34:53]

Solution de l'exercice 2, chapître 8 section 2

1)

http://cuisung.unige.ch/std/ex/8/2b.sol.html (1 of 2) [23-09-2001 16:35:40]

Solution de l'exercice 2, chapître 8 section 2

2) procedure ImprimePetitsEnfants(LaPersonne: PersonnePtr); var CourantEnfant, CourantPetitEnfant: ChaineFreresSoeurs; begin if (LaPersonne = nil) then writeln('Erreur: pointeur nil passe a la procedure ImprimePetitsEnfants') else begin {trouve le NoeudFrereSoeur de son premier enfant} CourantEnfant := LaPersonne^.Enfants; while (CourantEnfant <> nil) do begin {trouve le NoeudFrereSoeur de son premier petit-enfant. Note: Il faut utiliser le champ FrereOuSoeur pour acceder au pointeur de type PersonnePtr} CourantPetitEnfant := CourantEnfant^.FrereOuSoeur^.Enfants; while (CourantPetitEnfant <> nil) do begin write(CourantPetitEnfant^.FrereOuSoeur^.Nom,', '); writeln(CourantPetitEnfant^.FrereOuSoeur^.Prenom); CourantPetitEnfant := CourantPetitEnfant^.FrereSoeurSuivant; end; {while (CourantPetitEnfant <> nil)} CourantEnfant := CourantEnfant^.FrereSoeurSuivant; end; {while (CourantEnfant <> nil)} end; {else} end; {ImprimePetitsEnfants}

http://cuisung.unige.ch/std/ex/8/2b.sol.html (2 of 2) [23-09-2001 16:35:40]

Structuration des Données Informatiques - 14.3, solution 2

a) La page racine étant déjà pleine, l'adjonction de la valeur 10 va nécessiter la scission de cette page en deux et la création d'une page au niveau au-dessus contenant l'élément charnière (qui est 10). Le B-arbre résultant est:

b) La page dans laquelle devrait venir la nouvelle valeur (21) est déjà pleine. La page de même niveau qui est à sa gauche peut recevoir un élément supplémentaire. L'élément intermédiaire (20) qui se trouve dans le niveau au dessus est donc déplacé dans la page de gauche et la place ainsi libérée peut être occupée par le plus petit élément de la page excédentaire. Le B-arbre résultant est:

c) En supprimant la valeur 55, la page en question tombe en dessous du nombre minimum d'éléments. La page d'à côté ayant plus que le minimum d'éléments, on peut lui emprunter un élément (42) qui vient remplacer l'élément intermédiaire (50) qui se trouve dans le niveau au dessus. Cet élément intermédiaire (50) vient alors dans la page dans laquelle il manquait un élément. Le B-arbre résultant est:

d) La page dans laquelle devrait venir la nouvelle valeur (23) est déjà pleine. Les deux pages voisines de même niveau sont aussi pleines. Il faut donc scinder la page excédentaire en deux, avec comme élément charnière la valeur 23 qui ira dans la page du niveau au-dessus. Les deux pages résultant de la scission seront connectées à l'élément charnière nouvellement rajouté au niveau au-dessus. Le B-arbre résultant est:

e) La page dans laquelle devrait venir la nouvelle valeur (4) est déjà pleine. La page voisine de même niveau est aussi pleine. Il faut donc scinder la page excédentaire en deux, avec comme élément charnière la valeur 4 qui ira dans la page du niveau au-dessus. Les deux pages résultant de la scission seront connectées à l'élément charnière nouvellement rajouté au niveau au-dessus. Le B-arbre résultant est:

http://cuisung.unige.ch/std/ex/14/3b.sol.html (1 of 2) [23-09-2001 16:37:08]

Structuration des Données Informatiques - 14.3, solution 2

f) Pour supprimer la valeur 15, on va d'abord l'échanger avec la valeur qui se trouve le plus à droite du sous-arbre gauche, en l'occurence la valeur 7. La valeur 7 remplace donc la valeur 15 dans la page racine et doit être supprimée de la feuille dans laquelle elle se trouvait précédemment. Cette page feuille ayant assez d'éléments, la suppression peut se faire sans autre. Le B-arbre résultant est:

http://cuisung.unige.ch/std/ex/14/3b.sol.html (2 of 2) [23-09-2001 16:37:08]

http://cuisung.unige.ch/std/ex/7/4c.txt

procedure EffaceLigne(var UnTexte: VersLigne; NumeroLigne: integer); var courant: VersLigne; i: integer; begin if NumeroLigne < 1 then writeln ('NumeroLigne doit etre >= 1') else begin courant := UnTexte; i := 1; while (courant<>nil) and (i < NumeroLigne) do begin courant := courant^.LigneSuivante; i := i+1; end; (* while *) if courant=nil then writeln('La chaine est trop courte') else begin with courant^ do begin if courant = UnTexte then UnTexte := LigneSuivante else LignePrecedente^.LigneSuivante := LigneSuivante; if LigneSuivante <> nil then LigneSuivante^.LignePrecedente := LignePrecedente; end; (* with *) dispose(courant); end; (* if courant=nil *) end; (* if NumeroLigne < 1 *) end; (* EffaceLigne *) procedure JoindreLignes(var UnTexte: VersLigne; LigneCourante: integer); var courant, LigneADetruire: VersLigne; i: integer; begin if LigneCourante < 1 then writeln ('LigneCourante doit etre >= 1') else begin courant := UnTexte; i := 1; while (courant<>nil) and (i < LigneCourante) do begin courant := courant^.LigneSuivante; i := i+1; end; (* while *) if courant=nil then writeln('La chaine est trop courte') else if courant^.LigneSuivante = nil then writeln('On est sur la derniere ligne') else begin with courant^ do begin Texte := concat(Texte, LigneSuivante^.Texte); if LigneSuivante^.LigneSuivante = nil then dispose(LigneSuivante) else begin LigneSuivante^.LigneSuivante^.LignePrecedente := courant; LigneADetruire := LigneSuivante; LigneSuivante := LigneSuivante^.LigneSuivante; end; (* if LigneSuivante... *) end; (* with *) dispose(LigneADetruire); end; (* if courant^.LigneSuivante = nil *) end; (* if LigneCourante < 1 *) end; (* JoindreLignes *)

http://cuisung.unige.ch/std/ex/7/4c.txt [23-09-2001 16:37:37]

Structuration des Données Informatiques - 14.2, solution 1

a) Etant donné qu'un bloc de données dispose de 1536 octets et qu'une donnée occupe 76 octets, il peut y avoir au plus 20 données par bloc (1536 div 76=20 et restent 16 octets qui peuvent être utilisés pour pointer vers le bloc suivant et vers un eventuel bloc de débordement). Du fait que les blocs ne sont initialement remplis qu'à 80%, il n'y aura que 16 données par bloc (20*80/100 = 16). Il faudra donc 62'500 blocs de données pour stocker 1'000'000 éléments (1'000'000/16 = 62'500). Pour ce qui est des blocs d'index, chaque élément du bloc est composé d'une clé de 8 octets et d'une référence de 4 octets, soit 12 octets par élément. Il y a donc 85 éléments par bloc d'index (1024 div 12 = 85, reste 4). La première couche de blocs d'index, qui pointent vers des blocs de données, doit contenir un élément par bloc de données. Il y a donc 736 blocs (62'500 div 85 = 735, reste 25; c'est-à-dire qu'il y a 735 blocs entièrement pleins et le dernier bloc ne contenant que 25 éléments). La deuxième couche de blocs d'index occupe 9 blocs (736 div 85 = 8, reste 56 -> 8 blocs pleins et le neuvième avec 56 éléments). La troisième et dernière couche de blocs d'index ne contient qu'un seul bloc, avec seulement 9 éléments sur 85 occupés. La taille de l'espace disque occupé est donc: (nombre de blocs de données*taille d'un bloc de données) + (nombre de blocs d'index*taille d'un bloc d'index) = 62'500*1536 + (736+9+1)*1024 = 96'763'904 octets. En résumé: ❍ nombre de blocs de données = 62'500 ❍ profondeur de l'arborescence d'index = 3 ❍ nombre de blocs d'index = 736 puis 9 puis 1 ❍ espace disque occupé = 96'763'904 b) Etant donné qu'une page du B-arbre dispose de 1024 octets et qu'il faut stocker une référence de plus que de données, en supposant que l'on utilise 2 octets pour stocker le nombre d'éléments effectifs dans la page, il peut y avoir ((1024-4-2) div (76+4) = 12, reste 58 octets inutilisés). Le B-arbre est donc d'ordre 6. Si l'on suppose que toutes les pages sont pleines, 1'000'000 éléments occuperaient alors 83'334 pages (1'000'000 div 12 = 83'333, reste 4 éléments qui vont occuper partiellement la 83'334ème page). Si, à l'autre extrème, l'on suppose que les pages ne sont qu'à moitié pleines, 1'000'000 éléments occuperont alors 166'667 pages (1'000'000 div 6 = 166'666, reste 4 éléments qui vont occuper une page de plus). L'espace disque nécessaire sera donc compris entre 85'334'016 octets (83'334*1024) et 170'667'008 octets (166'667*1024). Pour ce qui est du nombre de niveaux de l'arborescence, il faut là aussi envisager les 2 cas http://cuisung.unige.ch/std/ex/14/2a.sol.html (1 of 2) [23-09-2001 16:38:00]

Structuration des Données Informatiques - 14.2, solution 1

extrèmes de pages toutes entièrement pleines ou toutes à moitié pleines: ❍ Quand les pages sont entièrement pleines, chaque page a 13 descendants. On peut facilement calculer le nombre de pages à chaque niveau puisque ce sont les puissances successives de 13: 1, 13, 169, 2197, 28561, 371'293. On voit alors facilement qu'il faut 6 niveaux pour avoir les 83'334 pages nécessaires pour stocker les 1'000'000 éléments. ❍ Dans le cas le plus défavorable où la racine ne contient qu'un seul élément (et deux descendants) et toutes les autres pages 6 éléments (et 7 descendants), les niveaux successifs contiennent: 1, 2, 14, 98, 686, 4802, 16'807 et, finalement 235'298 pages. Cela correspond à 2*7n-2 pages pour le niveau n. On voit donc qu'il faut 8 niveaux dans ce cas. En résumé: ❍ nombre de pages: entre 83'334 et 166'667 ❍ espace disque: entre 85'334'016 et 170'667'008 octets ❍ niveaux: entre 6 et 8.

http://cuisung.unige.ch/std/ex/14/2a.sol.html (2 of 2) [23-09-2001 16:38:00]

Structuration des Données Informatiques - 11.3, solution 2

1. Comme il s'agit d'un graphe pondéré, il faudra une matrice d'entiers pour représenter les arcs et une autre structure pour représenter les sommets, par exemple un tableau de strings. En supposant que les sommets sont rangés dans le tableau dans l'ordre suivant: ['Bern', 'Genève', 'Lausanne', 'Lucerne', 'Lugano', 'Milan', 'Neuchâtel', 'Zürich'], la matrice de pondération pourrait être ainsi (l'absence d'arc est notée -1): 0 -1 96 92 -1 -1 -1 120 -1 0 60 -1 -1 325 -1 -1 96 60 0 -1 -1 -1 68 -1 92 -1 -1 0 174 -1 -1 -1 -1 -1 -1 174 0 78 -1 206 -1 325 -1 -1 78 0 -1 -1 -1 -1 68 -1 -1 -1 0 -1 120 -1 -1 -1 206 -1 -1 0 2. Les déclarations Pascal pourraient être: var Distance:array[1..MaxNbSommets,1..MaxNbSommets] of integer; Villes: array[1..MaxNbSommets] of string; NbSommets: integer; 3. Une possibilité est de calculer le graphe de fermeture transitive indiquant la longueur du plus court chemin entre deux sommets (en utilsant une variante de l'algorithme de Warshall): for y:= 1 to NbSommets do for x:= 1 to NbSommets do if Distance[x,y] > -1 then for j:= 1 to NbSommets do if Distance[y,j] > -1 then if (Distance[x,j] > (Distance[x,y]+Distance[y,j])) or (Distance[x,j] = -1) then Distance[x,j] := Distance[x,y]+Distance[y,j]; Après quoi, la fonction pour déterminer la distance minimale entre deux villes x et y n'aura qu'à retourner Distance[index(x),index(y)]: function MinDist(Ville1, Ville2: string): integer; { accès à la matrice de fermeture transitive "Distance" par effet de bord. Retourne la plus courte distance entre Ville1 et Ville2. Retourne -1 s'il n'y a pas de chemin entre Ville1 et Ville2. } begin MinDist := Distance[index(Ville1),index(Ville2)]; end; { MinDist } =================================================================== Une autre possibilité consiste à reprendre l'algorithme de DFS et à ajouter des paramètres à la procédure Visite pour conserver la longueur du chemin partiel et retourner la distance minimale quand on a atteind le noeud de destination (on pourrait utiliser le BFS, mais cela impliquerait de mémoriser la longueur de tous les chemins partiels pour effectuer la comparaison à l'arrivée):

http://cuisung.unige.ch/std/ex/11/3b.sol.html (1 of 2) [23-09-2001 16:38:44]

Structuration des Données Informatiques - 11.3, solution 2

function MinDist(Ville1, Ville2: string): integer; { accès à la matrice "Distance" par effet de bord. Retourne la plus courte distance entre Ville1 et Ville2. Retourne MaxInt s'il n'y a pas de chemin entre Ville1 et Ville2. } var DistMin, i, Index2: integer; Parcouru: array[1..MaxNbSommets] of boolean; procedure Visite (IndexSommet : integer; DistPartielle:integer; var DistMin: integer); var AutreSommet : integer; begin if IndexSommet=Index2 then begin { on est arrivé à destination. Par un chemin plus court qu'avant? } if DistPartielle < DistMin then DistMin := DistPartielle end else begin Parcouru[IndexSommet]:=true; { marque par où on passe } for AutreSommet := 1 to NbSommets do { Y a-t-il un arc vers AutreSommet et pas de cycle? } if (Distance[IndexSommet,AutreSommet] > 0) and not Parcouru[AutreSommet] then Visite(AutreSommet, DistPartielle+Distance[IndexSommet,AutreSommet], DistMin); { ôte la marque en rebroussant chemin pour pouvoir repasser par ce même noeud par un autre chemin } Parcouru[IndexSommet]:=false; end; { if } end; { Visite } begin { MinDist } for i := 1 to NbSommets do Parcouru[i]:= false; Index2 := index(Ville2); DistMin := MaxInt; Visite(index(Ville1), 0, DistMin); MinDist := DistMin; end; { MinDist } Le bût du tableau Parcouru est d'éviter de boucler dans des cycles, en marquant chaque noeud par lequel on passe. On enlève la marque dès que l'on fait marche arrière pour permettre à l'algorithme de repasser éventuellement par ce même noeud, au cas où celui-ci se trouverait le long d'un autre chemin qui serait plus court.

http://cuisung.unige.ch/std/ex/11/3b.sol.html (2 of 2) [23-09-2001 16:38:44]

http://cuisung.unige.ch/std/ex/7/4a.txt

procedure DeplacerDansAnneau(UnAnneau: Anneau; var Arret: TypeArret; Depl: integer); var i : integer; pointeur : Anneau; { pointe normalement sur l'elem. qui serait detruit si Depl=1} ALaFin, { sera vrai si on detruit l'elem. en derniere position de l'anneau } PasFini : boolean; procedure Supprime(var Courant : Anneau; var ALaFin: boolean); {procedure pour supprimer un element de l'anneau et ajuster le pointeur "Courant" en consequence. Si on detruit le permier element, ajuste UnAnneau en consequence. ALaFin sera vrai si on est en train de detruire le dernier element. } var temp : Anneau; begin {1} if Courant^.predecesseur = Courant then begin {2} { on detruit l'unique element restant } dispose(Courant); UnAnneau := nil; end {2} { if ... then } else begin {3} {on efface l'element de l'anneau} Courant^.predecesseur^.successeur := Courant^.successeur; Courant^.successeur^.predecesseur := Courant^.predecesseur; ALaFin := Courant^.successeur=UnAnneau; temp := Courant; {on ajuste le pointeur} Courant := Courant^.successeur; {si on detruit le 1er elem., ajuster "UnAnneau" } if temp=UnAnneau then UnAnneau := Courant; {on efface physiquement l'element} dispose(temp); end; {3} { if ... else } end; {1} { Supprime }

http://cuisung.unige.ch/std/ex/7/4a.txt (1 of 2) [23-09-2001 16:39:11]

http://cuisung.unige.ch/std/ex/7/4a.txt

begin {4} { DeplacerDansAnneau } PasFini := UnAnneau<>nil; Arret := AnneauVide; ALaFin := false; pointeur := UnAnneau; while PasFini do begin {5} {si le deplacement est nul, on s'arrete} if Depl = 0 then begin {6} Arret := ElementNul; PasFini := false; end {6} { if ... then } else if Depl > 0 then begin {7} {si le deplacement est positif et on est a la fin, on s'arrete } if ALaFin then begin {8} PasFini := false; Arret := SortieAnneau; end {8} { if ALaFin then } else begin {9} {si le deplacement est positif} i := 1; while i < Depl do begin {10} {on se deplace} pointeur := pointeur^.successeur; {on verifie qu'on sort pas de l'anneau} if pointeur = UnAnneau then begin {11} Arret := SortieAnneau; i := Depl; PasFini := false; end {11} { if then } else i := i+1; end; {10} { while } end {9} { If ALaFin ... else } end {7} { if Depl > 0 } else begin {12} {de meme, pour le cas ou le deplacement est negatif} i := 0; while i > Depl do begin {13} { on veut reculer d'un cran, a moins d'etre au debut } if (pointeur=UnAnneau) and not ALaFin then begin {14} Arret := SortieAnneau; i := Depl; PasFini := false; end {14} { if } else begin {15} pointeur := pointeur^.predecesseur; i := i-1; end; {15} { if ... else } end; {13} { while } end; {12} { if ... else } if PasFini then begin {16} {on prend la nouvelle valeur pour le deplacement et on l'imprime} Depl := pointeur^.Entier; writeln(pointeur^.Entier); {on supprime l'element de l'anneau } Supprime(pointeur, ALaFin); {si l'anneau est vide apres cette suppression, il faudra s'arreter} PasFini := pointeur <> nil; end; {16} { if PasFini } end; {5} { while PasFini } end; {4} { DeplacerDansAnneau }

http://cuisung.unige.ch/std/ex/7/4a.txt (2 of 2) [23-09-2001 16:39:11]

Structuration des Données Informatiques - 8.1, solution 1

Il y a bien entendu beaucoup de solutions possibles. Le tout est de ne pas mettre un descendant avant un de ses ancêtres. On peut donc envisager de sérialiser les données de l'arbre, une ligne après l'autre, de la racine vers les feuilles: a) 20 18 42 3 26 14 39 7 30 10 34 b) vos beaux yeux amour marquise d mourir font me On aurait pu aussi imaginer faire un parcours en pré-ordre de l'arbre...

http://cuisung.unige.ch/std/ex/8/1a.sol.html [23-09-2001 16:39:35]

http://cuisung.unige.ch/std/ex/11/5a.txt

procedure TriTopoInverse(LeGraphe: Graphe); const MaxNbSommets=20; var i, CmptrVisite, IndexSommet : 0..MaxNbSommets; NumDOrdre : array[1..MaxNbSommets] of integer; Parcouru:array[1..MaxNbSommets] of boolean; NbSommets: integer; procedure Visite (IndexSommet : integer); var AutreSommet : integer; Voisins: SerieDeSommets; begin CmptrVisite := CmptrVisite + 1; NumDOrdre[IndexSommet] := CmptrVisite; Parcouru[IndexSommet] := true; Voisins := SommetsVoisins(IndexSommet, LeGraphe); if not FinDeSerie(Voisins) then begin AutreSommet := PremierSommet(Voisins); repeat if Parcouru[AutreSommet] then writeln(NomSommet(AutreSommet,LeGraphe), ' fait partie d''un cycle') else if NumDOrdre[AutreSommet] = 0 then Visite (AutreSommet); if FinDeSerie(Voisins) then AutreSommet := 0 else AutreSommet := SommetSuivant(Voisins); until AutreSommet = 0; end; { if } Parcouru[IndexSommet] := false; write(NomSommet(IndexSommet,LeGraphe)); end; { Visite } begin { TriTopoInverse } NbSommets := NombreDeSommets(LeGraphe); CmptrVisite := 0; for IndexSommet := 1 to NbSommets do NumDOrdre[IndexSommet]:=0; for IndexSommet := 1 to NbSommets do if NumDOrdre[IndexSommet]=0 then begin for i := 1 to NbSommets do Parcouru[i] := false; Visite (IndexSommet); end; { if } end; { TriTopoInverse }

http://cuisung.unige.ch/std/ex/11/5a.txt [23-09-2001 16:39:49]

Structuration des Données Informatiques - 14.3, solution 1

Le B-arbre résultant est:

Pour y arriver, on passe par les étapes suivantes: ● En supprimant g, on se trouve dans la situation suivante qui va nécessiter de fusionner la page où se trouvait g avec sa voisine de gauche et l'élément charnière du niveau au-dessus:

●

●

En effet, la page où se trouvait g est tombée en dessous du seuil minimum et la page voisine est au seuil minimum. On ne peut donc pas lui "emprunter" d'élément. On aboutit donc à la situation suivante, où la page qui contenait g doit être supprimée et la page du niveau au-dessus est tombée en dessous du seuil minimum et doit fusionner avec sa voisine de droite puisque celle-ci est au seuil minimum:

On aboutit ainsi à la situation finale, où la page qui contenait q ainsi que la page racine doivent être supprimées.

http://cuisung.unige.ch/std/ex/14/3a.sol.html [23-09-2001 16:40:12]

http://cuisung.unige.ch/std/ex/7/4b.txt

type VersMaillon = ^Maillon; Maillon = record Precedent, Suivant: VersMaillon; Contenu: integer; Visite: boolean; end; { Maillon } Arrets = (SortieChaine, Cycle); procedure Deplacement(LaChaine: VersMaillon; PremierSaut: integer; var TypeArret: Arrets; var PositionArret: integer); var Courant: VersMaillon; Deplace, Tmp: integer; begin PositionArret := 1; Deplace := PremierSaut-1; Courant := LaChaine; while Courant <> nil do begin Courant^.Visite := false; Courant := Courant^.Suivant; end; { while } Courant := LaChaine; while Deplace <> 0 do begin Tmp := Deplace; while ((Deplace < 0) and (Courant^.Precedent <> nil)) or ((Deplace > 0) and (Courant^.Suivant <> nil)) do if Deplace > 0 then begin Courant := Courant^.Suivant; Deplace := Deplace-1; end else begin Courant := Courant^.Precedent; Deplace := Deplace+1; end; if Deplace <> 0 then begin TypeArret := SortieChaine; Deplace := 0; end else if Courant^.Visite then begin TypeArret := Cycle; Deplace := 0; end else begin PositionArret := PositionArret + Tmp; Deplace := Courant^.Contenu; Courant^.Visite := true; end; {if } end; { while } end; { Deplacement }

http://cuisung.unige.ch/std/ex/7/4b.txt [23-09-2001 16:40:36]

http://cuisung.unige.ch/std/ex/8/2a.txt

type VersNoeud= ^Noeud; Noeud= record Desc: array['a'..'z'] of VersNoeud; Complet: boolean; end; { Noeud } var Dico: VersNoeud; function Trouve(LeDico: VersNoeud; LeMot: string) : boolean; begin { Trouve } if LeDico=nil then Trouve := false else if LeMot = '' then Trouve := LeDico^.Complet else Trouve := Trouve(LeDico^.Desc[LeMot[1]], copy(LeMot,2,length(LeMot)-1)); end; { Trouve } { version non-recursive } function Trouve(LeDico: VersNoeud; LeMot: string) : boolean; var i: integer; Courant: VersNoeud; begin { Trouve } i:=1; Courant := LeDico; while (i<=Length(LeMot)) and (Courant<>nil) do begin Courant := Courant^.Desc[LeMot[i]]; i := i+1; end; { while } if Courant=nil then Trouve := false else Trouve := Courant^.Complet; end; { Trouve } procedure Imprime(LeDico: VersNoeud); procedure Print(N: VersNoeud; S: string); var i:char; Splus:string; begin if N^.Complet then writeln(S); Splus := Insert(' ',S, length(S)+1); for i := 'a' to 'z' do if N^.Desc[i]<>nil then begin Splus[length(Splus)] := i; Print(N^.Desc[i],Splus); end; { if N^.Desc[i]<>nil } end; { Print } begin { Imprime } if LeDico<>nil then Print(LeDico, ''); end; { Imprime }

http://cuisung.unige.ch/std/ex/8/2a.txt [23-09-2001 16:40:50]

http://cuisung.unige.ch/std/ex/11/3a.txt

(* variation de la methode de Warshall pour calculer le chemin le plus court entre tous les sommets d'un graphe oriente *) for x:= 1 to MaxNbSommets do for y:= 1 to MaxNbSommets do Longueur[x,y]:=0; ... (* lecture du graphe dans "Longueur" *) for y:= 1 to NbSommets do for x:= 1 to NbSommets do if Longueur[x,y]>0 then for j:= 1 to NbSommets do if Longueur[y,j]>0 then if (Longueur[x,j] > (Longueur[x,y]+Longueur[y,j])) or (Longueur[x,j]=0) then Longueur[x,j] := Longueur[x,y]+Longueur[y,j];

http://cuisung.unige.ch/std/ex/11/3a.txt [23-09-2001 16:41:02]