DS2 2023 2024
Télécharger le DS2 2023 2024 en pdf
Page 1 : Pré-ING2Semestre 1 - 2023/2024DS n° 2 Informatique IIICalculatrice et documents non autorisésLorsqu’aucune consigne n’est précisée, les réponses peuvent être données en langage C ou en pseudo-code.Vous pouvez définir autant de fonctions que vous le souhaitez dans chaque exercice. Il n’y a pas nécessairement l’équiva-lence : une question = une fonction.Le barême est donné à titre indicatif mais peut être sujet à changement.Exercice 1 Gestion d’arbres ternaires9 pts1. Déclarer une structure Arbre pour représenter un nœud d’arbre ternaire au maximum trois fils stockant un entier.2. Écrire une fonction initialiserNoeud qui prend en paramètre un entier et retourne un pointeur vers un nouveaunœud initialisé avec la valeur passée en argument.3. Écrire une fonction compterEnfants qui retourne le nombre d’enfants d’un nœud passé en paramètre cette valeurpouvant être 0, 1, 2 ou 3.4. Pour un arbre ternaire, un parcours préfixe fonctionne ainsi :— affichage de la racine— affichage du fils de gauche— affichage du fils du milieu— affichage du fils de droiteÉcrire une fonction/procédure parcoursPrefixe qui prend en paramètre un pointeur vers la racine de l’arbre et affichesimplement les valeurs des nœuds en utilisant un tel parcours préfixe.5. Nous allons implémenter un parcours en largeur pour un tel type d’arbre :a Ecrire la/les structures nécessaires pour implémenter ce parcours.b On suppose que les fonctions empiler et depiler pour une pile ainsi que enfiler et defiler pourune file ont déjà été écrites.Si ces fonctions doivent être utilisées, indiquer leurs prototypes pour qu’elles correspondent aux structures déclaréesà la question précédente.c Ecrire la fonction parcoursLargeur qui prend en paramètre un pointeur vers la racine de l’arbre et affiche lesvaleurs des nœuds en utilisant un parcours en largeur.Exercice 2 Fusion d’ABR4 ptsDans cet exercice, on suppose que chaque noeud d’un ABR ne contient qu’un entier et les deux pointeurs vers les fils.On suppose aussi que la fonction/procédure de création de noeud existe également. Enfin on suppose que la fonction pourajouter un entier dans un ABR existe également.1. Définir la structure d’un noeud d’un arbre ABR pour bien préciser les noms des champs à utiliser.2. Définir le prototype de la fonction/procédure de création de noeud pour bien préciser les paramètres et/ou la valeurde retour.3. Définir le prototype de la fonction/procédure d’ajout d’un entier dans un ABR pour bien préciser les paramètres et/oula valeur de retour.4. Écrire une fonction/procédure fusionABR. Cette fonction/procédure va effectuer les tâches suivantes :— prendre deux Arbres Binaires de Recherche ABR en paramètre— créer un troisième arbre contenant toutes les valeurs des deux premiers les éléments peuvent être ajoutés dansn’importe quel ordre tant que l’arbre final contient bien toutes les valeurs des deux arbres d’origine. Les doublonsne seront pas ajoutés dans l’arbre final.— retourner l’adresse de la racine du troisième arbre créé.1
Page 2 : Exercice 3 Arbres et sécurité sociale7 ptsOn souhaite stocker dans un système les données personnelles d’un grand groupe de personnes. Chaque usager estidentifié par son numéro de sécurité sociale unique. Dans le but d’optimiser les recherches de ces personnes, nous utiliseronsune structure de type ABR Arbre de Recherche Binaire qui prendra comme élément de référence ce numéro unique dechaque personne l’ABR est donc rangé en fonction des numéros de sécurité sociale.1. Justifier le choix d’utilisation de l’ABR, par rapport à d’autres types de structures, pour pouvoir stocker les informationsdes personnes.2. Quel type de parcours d’arbre faudrait-il effectuer si on voulait afficher tous les numéros des usagers présents dansl’arbre par ordre décroissant ? Justifier.3. Définir la structure Personne contenant au moins son nom, son prénom, son âge nombre positif stocké sur pas plusde 3 chiffres en base 10, ainsi que son numéro de sécurité sociale nombre positif toujours sur 15 chiffres en base 10.4. Définir la structure Arbre qui contient une structure Personne allouée dynamiquement, ainsi que 2 pointeurs vers desstructures Arbre. Définir également un type Parbre qui pointera vers un nœud de l’ABR, donc vers une structureArbre.5. Écrire une fonction Parbre creationnoeudPersonne p1 qui permet de créer un nœud de l’arbre contenant lesdonnées d’une personne passée en paramètre. Cette fonction retourne un pointeur vers le nœud créé. Attention, cettefonction doit copier les données provenant de l’adresse en paramètre vers la structure allouée. Il faut partir du principeque la structure pointée par p1 va être libérée par la fonction appelante après l’appel à creationnoeud. En d’autrestermes, une copie de la personne passée en paramètre doit être effectuée dans le noeud qui va être créé ici.6. Écrire une fonction Parbre insertionParbre arbreSecu, Personne p1 permettant d’ajouter à l’ABR arbreSecuun nouveau nœud contenant la personne passée en paramètre attention, le nœud doit être correctement placé. Si cettepersonne ajoutée est déjà existante, alors le programme devra afficher un message d’erreur mais ne devra pas s’arrêter.7. Écrire une fonction/procédure recherche... qui permet de rechercher une personne à partir d’un numéro de sécuritésociale, et de retourner l’ensemble de ses informations si elle est présente dans l’ABR, ou renvoyer une valeur particulièrepour indiquer qu’elle n’existe pas sinon.8. Écrire une procédure void afficheSecuParbre arbreSecu qui va afficher les numéros de sécurité sociale des usagersprésents dans l’arbre pointé par arbreSecu en faisant un parcours suffixe.2
