EXAMEN DE STRUCTURES DE DONNEES

Examen de structures de données Session de juin 2000 Complexité des algorithmes (12 points) Tous les calculs de complexité que vous effectuerez devront porter sur la
complexité en pire cas. 1 Ecriture d'un algorithme itératif (1 point) Ecrire un sous-programme itératif (c'est à dire non récursif) qui renvoie
la somme des n premiers entiers.
Par exemple pour n = 4, le sous-programme doit renvoyer 10 (0+1+2+3+4) 2 Calcul de complexité d'un sous-programme itératif (1 point) Calculer la complexité temporelle du sous-programme précédent et donner son
ordre. 3 Méthode (1 point) Citer les trois étapes par lesquelles il faut passer pour construire un
sous-programme récursif 4 Ecriture d'un sous-programme récursif (1,5 points) Ecrire un sous-programme récursif effectuant le même traitement que celui
du I.1 5 Calcul de complexité d'un sous-programme récursif (2 points) Calculer la complexité du sous-programme récursif précédent et donner son
ordre. 6 Construction d'arbre d'appel (1,5 points) Construire l'arbre d'appel du sous-programme précédent pour n = 4. 7 Lecture d'arbre d'appel (1 point) Lire le résultat sur l'arbre précédent en indiquant les résultats
intermédiaires sur les feuilles concernées afin de faire apparaître la
démarche suivie. 8 Modification d'un algorithme (1 point) On voudrait maintenant obtenir la somme des n premières factorielles, et
non plus des n premiers entiers.
Le résultat avec n = 4 est donc 34
(fact(0) + fact(1) + fact(2) + fact(3) + fact(4) = 1+1+2+6+24 = 34)
Choisissez, soit la version récursive, soit la version itérative du sous-
programme précédent et adaptez la à ce nouveau calcul.
Attention : Ne réécrivez pas la fonction factorielle, considérez fact comme
une fonction prédéfinie et utilisez-la comme telle. 9 Calcul de complexité (2 points) Sachant que l'opération fact(n) a un coût de 5n+3, calculer la complexité
du sous-programme précédent (I.8) et donner son ordre. Arbres binaires de recherche (8 points)
1 Construction simple d'un arbre binaire de recherche (1 point) En utilisant une procédure « insérer » simple, ne prenant pas en compte
l'équilibre de l'arbre, construisez l'arbre binaire de recherche
correspondant à l'ajout successif des éléments suivant :
5, 6, 8, 4, 3, 7, 1, 2, 10, 9 2 Parcours préfixé d'un arbre binaire de recherche (1 point) Donner le résultat (sous forme de liste) du parcours de l'arbre précédent
selon un parcours préfixé. 3 Evaluation de performance d'un arbre binaire de recherche (1 point) Calculer le nombre moyen de n?uds traversés lors de la recherche d'un
élément appartenant à l'arbre (Un n?ud est considéré comme traversé si au
moins une comparaison est effectuée sur son contenu). 4 Construction intelligente d'un arbre binaire de recherche (3 points) Construire l'arbre binaire de recherche obtenu grâce aux même éléments que
dans le II.1, mais en utilisant cette fois une procédure « insérer » gérant
l'équilibre de l'arbre.
Pour cela vous utiliserez la notation vue en cours mettant en valeur les
étapes de rééquilibrage.
Comme en cours, vous détaillerez celles-ci en indiquant le sens des
rotations par des flèches et en entourant le sous-arbre concerné par chaque
rotation. Vous indiquerez les double rotations sur un seul schéma, et
signalerez clairement les étapes intermédiaires si vous y avez recours. 5 Parcours infixé d'un arbre binaire de recherche (1 point) Un moyen de vérifier l'arbre construit est d'effectuer un parcours infixé
de celui-ci, expliquer brièvement pourquoi, et donner le résultat de ce
parcours infixé sur l'arbre que vous venez de construire. 6 Evaluation de performance d'un arbre binaire de recherche (1 point) Calculer le nombre moyen de n?uds traversés pour rechercher un élément
présent dans le nouvel arbre construit en II.4.
Préciser quel arbre (II.1 ou II.4) est le plus performant.