Structure des données complexes
Travaux Dirigés : SDC
Dans tous les exercices, on écrira des fonctions ou procédures qui seront
utilisées dans un programme.
Exercice 0 : Fusion de 2 tableaux
Soient 2 tableaux A et B triés de longueur respective m et n. Ecrire une
fonction pour les fusionner en un tableau C trié de longueur m+n.
Exercice 1 :
Ecrire une fonction qui crée une liste chaînée d’un type caractère ou entier à
partir des éléments d’un tableau.
Exercice 2 :
Ecrire deux fonctions renvoyant le kième élément d’une liste. Une itérative et
l’autre récursive.
Exercice 3 :
Ecrire une fonction récursive qui recherche un élément de valeur x dans une liste
de chaînes de caractères.
Exercice 4 :
Ecrire les fonctions egal – sup – inf ou compare qui comparent 2 listes de
caractères.
Exercice 5 :
Ecrire une fonction pour insérer un élément x à la kième place dans une liste de
chaînes de caractères. Si la liste comporte moins de k éléments on insère x à la
fin.
Exercice 6 :
Ecrire les fonctions longueur – concatenation –inverse qui respectivement donne
la longueur d’une liste – concatène 2 listes – inverse une liste
Exercice 7 :
Professeur : ASSALE Adjé Louis 1/2 INP-HB
Structure des données complexes
Ecrire une fonction qui supprime toutes les occurrences d’une valeur dans une
liste
Exercice 8 :
Ecrire une fonction qui recherche une liste l1 dans une liste l. on pourra définir
une fonction préfixe qui renvoie vrai si une liste l1 est l’entête d’une liste l.
Exercice 9 :
Ecrire sous forme récursive et itérative une fonction vérifiant qu’un arbre binaire
est ordonné.
Exercice 10 :
Ecrire une fonction vérifiant qu’un arbre binaire est dégénéré.
Exercice 11 :
On donne une expression arithmétique en notation préfixée rangée dans une
chaine de caractères, et terminée par le caractère #. L’expression est supposée
syntaxiquement correcte. Donner un algorithme, sous forme récursive,
permettant de construire l’arbre représentant cette expression.
Professeur : ASSALE Adjé Louis 2/2 INP-HB
