Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ENSA de Marrakech ALGORITHMIQUE AVANCEE M. Zrikem 3ième année 2009-2010 Examen

ENSA de Marrakech ALGORITHMIQUE AVANCEE M. Zrikem 3ième année 2009-2010 Examen d’Avril Exercice 1 On considère l’algorithme suivant: Algo(int n){ Int i; for(i=0; i*i<n; i++){ Algo1(n); Algo2(n); } Algo3(n); } Sachant que Algo1(n) s’eﬀectue en temps O(√n), Algo2(n) en temps O(√n log n) et Algo3(n) en temps O(n), quelle est la complexité de Algo(n)? Justiﬁez vos réponses. Exercice 2 Écrire un algorithme qui, étant donné un tableau d’entiers tab, recherche la position de la première case contenant 0 (soit k l’indice de cette case), et qui affiche le contenu des cases de k à 1 à rebours. Quelle est la complexité dans le meilleur cas ? et dans le pire cas ? Exercice 3 Nous souhaitons manipuler des listes doublement chainées d’entiers et qui sont triées. 1 – Donner une implémentation pour les listes doublement chaînées. 2 – Donner une procédure qui permet d’insérer un élément en tête d’une liste doublement chaînée. 3 – Donner un algorithme itératif qui permet d’insérer un entier à sa place dans une liste triée dans l’ordre croissant. 4 – Quelle est sa complexité ? 5 – Donner une version récursive de cet algorithme (utiliser la procédure de la question 2). Exercice 4 : Déﬁnir un algorithme parenthèse qui renvoie Vrai si une expression est bien parenthésée (chaque parenthèse ouverte ’(’ est refermée ’)’), et Faux sinon. Cet algorithme prend en argument une chaîne de caractères, regarde les caractères un par un et utilise une pile pour vériﬁer le parenthésage. Dans quels cas doit-on : – empiler le caractère lu ? – dépiler ? – retourner false ? – retourner true ? Exercice 5 1. Donner une structure de données représentant un arbre binaire. 2. Donner une structure de données représentant un arbre quelconque. 3. Ecrire une fonction calculant la taille d’un arbre binaire. 4. Donner un arbre de hauteur n (n étant le nombre de feuilles). Exercice 6 Soit la liste d’entiers l = [11; 15; 5; 2; 3; 9; 17; 21; 22; 13; 19; 4; 12]. 1. Construire un arbre binaire de recherche associé à l (en prenant les éléments dans l’ordre). 2. Détailler l’insertion du nœud de valeur 3 dans l’arbre. 3. Dessiner le chemin de recherche des nombres 5, 19 et 8 dans l’arbre. 4. Détailler l’opération de suppression de la racine, du nœud d’étiquette 15 et du nœud d’étiquette 17. 5. Quel parcours de cet arbre permet de trier les nombres dans l’ordre croissant ?dans l’ordre décroissant ? uploads/Science et Technologie/ controle-1-algo.pdf