Remerciez-le!

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

Examen 1516 session1z Universit ?e Paris Diderot L Informatique Ann ?ee ?? Examen d ? algorithmique jeudi janvier h ?? h Aucun document autoris ?e Le bareme est donn ?ea titre indicatif Mode d ? emploi La qualit ?e de la r ?edaction des algorithmes et des

Universit ?e Paris Diderot L Informatique Ann ?ee ?? Examen d ? algorithmique jeudi janvier h ?? h Aucun document autoris ?e Le bareme est donn ?ea titre indicatif Mode d ? emploi La qualit ?e de la r ?edaction des algorithmes et des explications sera fortement prise en compte pour la On peut toujours supposer une question r ?esolue et passer a la suite note Exercice D ?erouler des algorithmes points On considere l ? algorithme P ci-dessous Def P entier x Si x Alors Retourner Sinon a b i tant que i x faire aux b b a b a aux i i Retourner b D ?ecrire ce que fait l ? algorithme P appel ?e avec le parametre On d ?ecrira pr ?ecis ?ement l ? ?etat des variables a et b au cours de l ? algorithme On considere l ? algorithme P ci-dessous Def P x Si x ou x Alors Retourner x Sinon Retourner P x- P x- D ?ecrire ce que fait l ? algorithme P appel ?e avec le parametre On d ?ecrira pr ?ecis ?ement tous les appels de fonctions Comparer ces deux algorithmes Exercice Tri pour deux valeurs - points On veut d ?e ?nir un algorithme de tri pour des tableaux de taille ne contenant que n deux valeurs distinctes On cherche a trier dans l ? ordre croissant Par exemple pour le tableau suivant de taille on veut obtenir Ecrire un algorithme de tri bas ?e sur une m ?ethode de comptage Ecrire un algorithme qui trie le tableau en ne faisant qu ? un seul parcours du tableau CUniversit ?e Paris Diderot L Informatique Ann ?ee ?? Exercice Algorithmes sur les arbres - points On considere des arbre binaires contenant des valeurs entieres dans les noeuds comme dans l ? exemple ci-dessous On suppose que ces arbres sont repr ?esent ?es par des structures cha n ?ees comme en cours Un noeud de l ? arbre type noeud sera repr ?esent ?e par une structure ayant les champs de valeurs suivants ?? un champ de nom val et de type entier contenant la valeur stock ?ee ?? un champ de nom fg et de type arbre contenant l ? adresse du ?ls gauche ?? un champ de nom fd et de type arbre contenant l ? adresse du ?ls droit Et un arbre est un pointeur adresse vers un noeud l ? adresse d ?esigne un arbre vide Lorsqu ? un noeud n ? a pas de ?ls gauche son champ fg vaut et c ? est pareil pour le ?ls droit avec fd Un noeud qui n ? a ni ?ls gauche ni ?ls droit est une feuille Si a est un arbre non vide a- val d ?esigne la valeur stock ?ee a sa racine le premier noeud de l ? arbre a- fg d ?esigne l ? adresse du ?ls gauche donc un arbre et a- fg d ?esigne l ? adresse du ?ls