DS2 2023 2024 V2
Télécharger le DS2 2023 2024 V2 en pdf
Page 1 : Pré-ING2Semestre 1 - 2023/2024DS n° 2 Informatique IIIdoubles-diplômesCalculatrice 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.Exercice 1 Conversion ABR - LISTEDans cet exercice on souhaite coder une fonction qui va transformer un arbre de type ABR en liste chainée. La listechainée qui sera créée devra être triée dans l’ordre croissant.1. Déclarer la structure ABR qui va contenir un entier comme valeur, et 2 pointeurs vers d’autres structures ABR.2. Déclarer la structure Chainon d’une liste, qui va contenir un entier comme valeur et un pointeur vers le prochainchainon de la liste.3. — Ecrire une fonction conversion... qui prend en paramètre simplement l’ABR que l’on souhaite parcourir etrien d’autre !, et qui va retourner la liste chainée remplie.— Cette fonction devra s’exécuter avec une complexité temporelle linéaire !— Si la fonction conversion rencontre un problème, elle stoppera le programme.Exercice 2 Transformation inhabituelleDans cet exercice on souhaite coder une fonction qui va modifier le contenu d’un ABR. Après transformation, chaquenoeud contiendra comme valeur la somme de tous les noeuds dont les valeurs sont strictement inférieures à la sienne on partdu principe qu’il n’y a pas de doublons.Ci-dessous, un exemple d’un ABR avant et après transformation :— En utilisant la structure ABR déclarée dans l’exercice précédente, écrire une fonction transformation... qui prenden entrée un ABR et rien d’autre ! et qui va le modifier comme indiqué dans l’énoncé. La fonction retourneral’arbre modifié.— BONUS La complexité temporelle de cette fonction doit être linéaire !— Si la fonction transformation rencontre un problème, on stoppera le programme.Exercice 3 Intersection de deux ABRDans cet exercice, nous souhaitons créer un ABR à partir de 2 autres ABR deja existants. Le contenu du troisième arbresera l’intersection des 2 premiers, c’est à dire les valeurs qui se trouvent à la fois dans le premier arbre et le deuxième.— A l’aide de la structure ABR déclarée dans le premier exercice, Ecrire la fonction intersection... qui prendra2 ABR en paramètre et qui retournera le troisième arbre. Ce troisième arbre contiendra alors toutes les valeurscommunes aux 2 premiers.— Si la fonction intersection rencontre un problème, le programme doit s’arrêter.1
Page 2 : Exercice 4 Arbre ModulobinaireL’objectif de cet exercice est de mettre en œuvre un arbre binaire particulier, respectant des règles de placement spéci-fiques. Chaque noeud de l’arbre doit contenir une valeur entière.Règles de placement :— Si l’arbre est vide, le premier noeud devient la racine.— Si la racine n’a pas d’enfant, placez un nouveau noeud à gauche si sa valeur est un multiple de 2, sinon à droite.— À chaque changement de profondeur, incrémentez le diviseur. Pour la valeur à ajouter, à cette profondeur, placez-laà gauche si c’est une valeur multiple du diviseur, sinon à droite.ETAPE 1 ajout de 5ETAPE 2 ajout de 6l'arbre est vide, on créé la racinedivisible par 2, donc on créé le fils gauche.55/\/\6/\ETAPE 3 ajout de 8ETAPE 4 ajout de 12divisible par 2, on parcourt le fils gauche,divisible par 2, on parcourt le fils gauchepuis non divisible par 3,on créé le filspuis divisible par 3 : on créé le fils gauchedroit55/\/\66/\/\8128/\/\/\ETAPE 5 ajout de 7ETAPE 6 ajout de 9non divisible par 2 :non divisible par 2, on parcourt le fils droiton créé le fils droitdivisible par 3, on créé le fils gauche55/\/\6767/\/\/\/\1281289/\/\/\/\/\ETAPE 7 ajout de 25ETAPE 8 ajout de 16non divisible par 2, on parcourt le fils droitdivisible par 2, on parcourt le fils gauchenon divisible par 3, on créé le fils droitnon divisible par 3, on parcourt le fils droitdivisible par 4, on créé le fils gauche55/\/\6767/\/\/\/\128 925128 925/\161. Ecrire la fonction CreationArbrevaleur qui crée un noeud d’un arbre contenant une valeur passée en paramètre etrenvoie son adresse.2. Ecrire la fonction AjoutNoeudarbre, valeur qui prend en paramètre l’adresse d’un noeud de l’arbre, ainsi qu’unevaleur entière à ajouter dans cet arbre. Elle va ajouter un noeud dans l’arbre contenant cet entier en respectant lesrègles de placement de l’arbre Modulobinaire3. Où se trouvera un noeud contenant un nombre premier dans un tel arbre ?2
