2025 Mines Info MPI 1 — Corrigé

Étude des tableaux associatifs

Préliminaires

L’épreuve est composée d’un problème unique, comportant 34 questions. Le problème consiste en l’étude et l’implémentation d’un tableau associatif en C, suivant différentes méthodes.

Le problème est divisé en 4 sections distinctes :

  • l’implémentation du tableau associatif en utilisant une structure d’arbre (section 1),

  • l’ajout d’un « ramasse miettes » pour gérer la mémoire (section 2),

  • l’implémentation du tableau associatif en utilisant un algorithme probabiliste (section 3),

  • la conception d’un analyseur syntaxique pour créer un tableau associatif à partir d’une chaîne de caractères (section 4).

Les quatre sections sont indépendantes.

Travail attendu

Les résultats attendus pour certaines questions pourront être admis afin de faciliter la résolution des questions suivantes. Le langage C constitue l’unique langage autorisé pour le traitement des questions de programmation.

Une attention particulière sera portée quant à la correction et la lisibilité du code proposé.

Si une tolérance raisonnable peut être envisagée sur certains aspects syntaxiques dans le cadre d’une épreuve réalisée sur support papier (par exemple, l’oubli d’un « ; »), un code difficilement lisible ou l’emploi de fonctions ou structures de contrôle non conformes aux standards du langage C, notamment celles empruntées à d’autres langages, sera sanctionné.

Un soin particulier sera également apporté à la gestion de la mémoire, à la bonne initialisation des structures ainsi qu’au contrôle systématique des allocations mémoires.

La gestion rigoureuse des erreurs sera valorisée (l’utilisation d’assert est recommandée), de même que la qualité, la simplicité et la lisibilité du code.

En conformité avec le programme officiel, il sera admis que certains en-têtes standards soient présupposés comme inclus dans le code : , , , , , , et .

Les tableaux associatifs

Les tableaux associatifs

sont des structures de données permettant un accès rapide à une valeur à partir d’une clef. Afin de simplifier l’écriture du code, nous considèrerons que les clefs sont toujours de type char* et les valeurs de type int.

1 – Implémentation par un arbre binaire de recherche Le but de cette section est d’étudier une implémentation d’un tableau associatif reposant sur un arbre binaire de recherche.

Nous adopterons une approche fonctionnelle pour l’implémentation des structures de données, en les considérant comme immuables. Ainsi, chaque fonction de manipulation renverra systématiquement une nouvelle version modifiée de la structure, sans altérer l’originale.

Cette méthode présente l’avantage d’éliminer les effets de bord lors des appels de fonction. Toutefois, elle implique une augmentation du nombre d’allocations mémoire, puisque chaque modification nécessite la création d’une copie de la structure de données.

Dans cette section nous ne nous occuperons pas de la récupération de la mémoire, car nous introduirons en section 2 un « ramasse miettes » pour gérer la mémoire automatiquement.

Arbre binaire de recherche

Définitions : Soit A un arbre binaire de recherche. On notera avec une lettre minuscule (par exemple x ou y) un nœud de A, et avec une lettre majuscule (par exemple {T_1,T_2} ou {T_3}) un sous-arbre de A.

Soit x un nœud, on notera {x_{\mathrm{gauche}}} et {x_{\mathrm{droit}}}, respectivement le sous-arbre gauche et le sous-arbre droit de x. On rappelle que la taille d’un arbre est égale au nombre de nœuds qu’il contient.

Pour un arbre de racine x, on notera h(x) sa hauteur, et on définit récursivement la hauteur d’un arbre par :

  • la hauteur d’un arbre vide est {-1},

  • {h(x)=\max(h(x_{\mathrm{gauche}}),h(x_{\mathrm{droit}}))+1}.

Pour un arbre de racine x, on définit la valeur d’équilibre par : {e(x)=h(x_{\mathrm{gauche}})-h(x_{\mathrm{droit}})} On qualifiera d’équilibré un arbre binaire de recherche A si pour tout nœud x de A, {-1\le e(x)\le1} Définition : On définit un nœud d’un arbre binaire de recherche par la structure suivante :

On utilisera la valeur du champ clef pour ordonner les nœuds de l’arbre, en utilisant l’ordre alphabétique.

1 –Nous nous intéressons aux valeurs du champ clef de la structure ci-dessus. Expliquer comment une chaîne de caractères est représentée en mémoire en C ? Combien d’octets sont nécessaires pour représenter la chaîne « arbre » par exemple ?
2 – Sachant que le code ASCII du caractère ‘a’ est 97, quelle est sa représentation en binaire ? Quelle est sa représentation en hexadécimal ?
3 – Écrire une fonction C copie_chaine qui renvoie une copie de la chaîne de caractères passée en paramètre.

La signature de la fonction est :

Indication C : On considèrera que la chaîne de caractères passée en paramètre (chaine) n’est jamais NULL.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :