Exercice 0 (4,5 points)
Répondez aux différentes questions sur la feuille annexe. Chaque question est sur 0,5 points
Exercice 1 (6,5 points)
On s¹intéresse aux arbres AVL.
A (1 pt.)- On considère l¹arbre ci dessous. En rappelant les propriétés des arbres AVL, expliquez pourquoi il s¹agit d¹un arbre AVL, et décorez le sur la page fournie en annexe, en y portant les déséquilibres.
B (0,5 pt)- Rappelez ce qu¹est l¹opération d¹adjonction dans un arbre AVL.
C (2 pts.)- En partant de l¹arbre AVL ci-dessus, donner les arbres obtenus en ajoutant successivement 50 puis 25 On s¹attachera particulièrement à expliquer le raisonnement.
D (0,5 pt.)- Donner la liste infixée de l¹arbre donné en A, en justifiant votre raisonnement. Quelle propriété a-t-elle ? Est-ce toujours le cas ?
E (0,5 pt.)- Rappelez ce qu¹est l¹opération de suppression.
F (1 pt.)- Donner l¹arbre obtenu par suppression de 20 dans l¹arbre ci-dessous, en justifiant votre raisonnement.
1 pt. G- Donner l¹arbre obtenu par suppression de 40 dans l¹arbre donné dans la question F.
Exercice 2 (9 points)
Les questions A.1, B.1 et C.1 sont des exemples qui sont là pour vous aider à comprendre ce qu¹il faut faire dans les questions A.2, B.2 et C.2 où il faut écrire des programmes dans le langage de programmation de votre choix, compréhensible par le correcteur.
Un texte est une suite quelconque de caractères. Il peut être représenté par une liste contiguë de caractères. On se propose d¹implanter quelques opérations spécifiques sur les textes. La spécification d¹un paquetage correspondant en Ada est donné en fin d¹exercice, pour information, étant entendu que vous pouvez utiliser le langage de programmation de votre choix, en utilisant les opérations sur les listes contiguës. Vous n¹avez pas accès à la représentation elle-même. Les dessins des exemples néanmoins y feront référence, car plus explicites. En particulier, on dispose des trois listes suivantes.
A- On étudie l¹opération Recherche, qui retourne la première position du texte De dans le texte Dans, s¹il est présent et lève l¹exception Erreur_Specification s¹il n¹y est pas.
A.1 (1 pt.)- Donner le résultat de Recherche (De => L2, Dans => L1), et celui de Recherche (De => L3, Dans => L1), en expliquant votre raisonnement.
A.2 (2 pts.)- Proposer une implantation de l¹opération Recherche. Evaluer la complexité.
B- On étudie l¹opération Supprimer_Les_Espaces_Inutiles, qui supprime les espaces qui suivent immédiatement un autre espace dans le texte Dans.
B.1 (0,5 pt.)- Donner le résultat de Supprimer_Les_Espaces_Inutiles (L1), en expliquant votre raisonnement.
B.2 (2 pts.)- Proposer une implantation de l¹opération Supprimer_Les_Espaces_Inutiles, Evaluer la complexité.
C- On étudie l¹opération Substituer, qui remplace la première occurrence du texte La_Chaine dans le texte Dans par le texte Par, s¹il est présent et lève l¹exception Erreur_Specification s¹il n¹y est pas.
C.1 (1 pt.)- Donner le résultat de Substituer (La_Chaine => L2, Par => L3, Dans => L1), en expliquant votre raisonnement.
C.2 (2,5 pts.)- Proposer une implantation de l¹opération Substituer. Evaluer la complexité.
Spécification du paquetage en Ada.
with Listes_Contigues;
package Les_Textes is
type Texte (Taille_Max: Positive) is private;
function Recherche (De, Dans: Texte) return Positive;
procedure Substituer (La_Chaine: in Texte;
Par: in Texte;
Dans: in
out Texte);
procedure Supprimer_Les_Espaces_Inutiles
(Dans: in
out Texte);
private
package L_C is new Listes_Contigues
(Character);
type Texte (Taille_Max: Positive) is
new L_C.Liste (Taille_Max);
end Les_Textes;
Annexe à rendre
Numéro de copie:
Utiliser cette feuille pour répondre aux questions ci-dessous.
1 Décorez l¹arbre AVL suivant en y portant les déséquilibres (Exercice 1 Q.A).
2 Dans un B-arbre d'ordre 10, qui contient 100 000 valeurs, à combien estimez-vous le nombre d¹accès disque pour rechercher un élément ?
|
|
|
|
|
|
3 Dans un B-arbre d'ordre m, qui contient N valeurs, si on applique une recherche dichotomique sur les n¦uds, combien y aura-t-il de comparaisons ?
|
|
|
|
|
|
4 Si on trie une liste contiguë, qui contient 100 000 valeurs, par un tri par tas, sur une machine dont le temps de base d¹une comparaison ou d¹un transfert est de l¹ordre de la dizaine de microsecondes, à combien estimez-vous le temps de tri?
|
|
|
|
|
|
5 Si on trie une liste contiguë, qui contient 100 000 valeurs, par un tri par la méthode de la bulle, sur une machine dont le temps de base d¹une comparaison ou d¹un transfert est de l¹ordre de la dizaine de microsecondes, à combien estimez-vous le temps de tri?
|
|
|
|
|
|
6 Quel est l¹ordre de grandeur de la complexité au pire de l¹opération qui teste si deux arbres binaires de recherche contiennent les mêmes éléments, en supposant qu¹ils en contiennent au plus n?
|
|
|
|
|
|
7 Si on définit début(x)=cons(premier(x),listevide), parmi les cinq égalités suivantes, quelle est celle qui est obligatoirement vraie?
concaténer(début(x),x)=concaténer(x,fin(x))
début(fin(x))=x
concaténer(début(x),fin(x))=x
début(fin(x))=fin(début(x))
fin(début(x))=x
8 Supposons une liste construite à l¹aide des types suivants:
type Place; type Pt_Place is access Place;
type Place is record
Contenu: Element;
Suivant: Pt_Place;
end record;
Quel groupe d¹instructions implante l¹opération insérer p après q, où q repère un élément de la liste et p repère l¹élément à insérer?
Q.Suivant
:= P.Suivant; P.Suivant := Q;
P.Suivant
:= Q; Q.Suivant := P.Suivant;
P.Suivant
:= Q.Suivant; Q.Suivant := P;
Q.Suivant
:= P; P.Suivant := Q.Suivant;
Q.Suivant
:= P.Suivant; P.Suivant := Q.Suivant;
9 Ajouter 45 dans l'arbre binaire de recherche suivant, et expliquer.
|
______________________________________ |
|
10 On dispose d¹un fichier de hachage qui contient 100 000 éléments. Chaque bloc disque peut contenir 40 éléments. La fonction de hachage a pour résultat un nombre entre 1 et 1000, équitablement répartis. A combien estimez-vous le nombre d¹accès disque pour rechercher un élément ?
|
|
|
|
|
|