CPGE-Agadir Mars 2016
DEVOIR SURVEILLE N°2
INFORMATIQUE
MP-PSI
2H
-Correction-
Exercice1 : Tri
Exercice 1 :
Soit la fonction de tri suivante :
from copy import copy
def trier(t):
p=copy(t) #p est une copie de t
for i in range(len(p)):
for j in range(len(p)-i-1):
if (p[j+1]<p[j]):
p[j],p[j+1]=p[j+1],p[j]
print(i,j,p)
return p
#programme principal
exemple=[3,1,4,2]
resultat=trier(exemple)
1- De quelle version de méthode de tri s’agit-elle ? Tri à bulles
2- Quelles sont les informations affichées lors de son exécution?
0 0 [1, 3, 4, 2]
0 1 [1, 3, 4, 2]
0 2 [1, 3, 2, 4]
1 0 [1, 3, 2, 4]
1 1 [1, 2, 3, 4]
2 0 [1, 2, 3, 4]
3- Que contient la variable resultat après son exécution? [1, 2, 3, 4]
4- Que contient la variable exemple après son exécution? [3, 1, 4, 2]
5- Que se passe-t-il si nous remplaçons l’instruction p=copy(t) par l’instruction p=t ?
La liste exemple sera elle aussi triée.
2
6- Quelle est sa complexité : O(n )
[Link] Page 1/7
7- Réécrire la fonction récursive trier qui utilise le même algorithme que la fonction trier du programme
Python ci-dessus sans afficher les valeurs intermédiaires. L’appel trier(s) sur une liste d’entiers s
doit donc renvoyer une liste d’entiers triée r qui contient les mêmes éléments que la liste s.
def trier(s):
if len(s)==0 : return []
if len(s)==1 : return [s[0]]
p=copy(s)
for j in range(len(p)-1):
if (p[j+1] < p[j]) :
p[j], p[j+1] = p[j+1], p[j]
return trier(p[:-1]) + [p[-1]]
Exercice 2 :
Arbre binaire d’entiers
Un arbre binaire d’entiers a est une structure qui peut, soit être vide (notée ∅), soit être un nœud qui
contient une étiquette entière (notée E(a)), un sous-arbre gauche (noté G(a)) et un sous-arbre droit (noté
D(a)) qui sont tous deux des arbres binaires d’entiers.
Exemples :
Implémentation en python
Un arbre binaire peut être représenté par une liste :
Un arbre vide : a = [ ]
Un arbre non vide : a = [ étiquette_racine, fils_Gauche , fils_Droit]
Exemple :
Le deuxième arbre de l’exemple ci-dessus est représenté par la liste :
A=[14,[ 11,[5,[],[]],[8,[],[]] ],[13,[9,[],[]],[4,[],[]]]]
Numérotation hiérarchique des nœuds d’un arbre binaire
La numérotation hiérarchique des nœuds d’un arbre binaire a consiste à associer à chaque nœud un numéro
compris entre 0 et n-1 (n nombre de nœuds) par un parcours en largeur partant de la racine (numéro 0) et en
parcourant chaque niveau de gauche à droite jusqu’au dernier nœud : le plus profond et le plus à droite
(numéro n-1|).
Dans les exemples suivants, le numéro de chaque nœud sera noté en-dessous de son étiquette.
[Link] Page 2/7
Question 1 :
Ecrire les fonctions de base vues au cours : vide(a) ; vide(a) ; filsGauche(a) ;
filsDroit(a)
def vide(a): def val(a): def filsGauche(a):
return a==[] if a!=[]: if not vide(a):
return a[0] return a[1]
else: else:
return None return []
def filsDroit(a):
if not vide(a):
return a[2]
else:
return []
Question2:
Ecrire une fonction parcourir(a) qui parcoure un arbre par niveau et retourne une liste simple contenant les
valeurs des nœuds parcourus :
Exemple :
>>>A=[14,[ 11,[5,[],[]],[8,[],[]] ],[13,[9,[],[]],[4,[],[]]]]
>>>parcourir(A)
[14, 11, 13, 5, 8, 9, 4]
def parcourLargeur(a):
L=[]
F=[] #File FIFO
[Link](a) #enfiler a dans la file F
while F!=[]:
n=[Link](0) #défiler F
L+=[val(n)]
if not vide(filsGauche(n)): [Link](filsGauche(n))
if not vide(filsDroit(n)) : [Link](filsDroit(n))
return L
[Link] Page 3/7
Arbres binaires complets (ABC)
Un arbre binaire complet est un arbre binaire dont tous les niveaux sont complets, c’est-à-dire que tous les
nœuds d’un même niveau ont deux fils non vides sauf les nœuds du niveau le plus profond qui n’ont aucun fils
(c’est-à-dire deux fils vides).
Le deuxième arbre de l’exemple ci-dessus est complet.
Question 3 : calculer la hauteur d’un ABC
Ecrire la fonction non récursive hauteur(a) qui retourne la
hauteur d’un arbre binaire complet.
def hauteur(a):
n=0
if vide(a) : return 0
while not vide(filsDroit(a)):
n+=1
a=filsDroit(a)
return (n)
Question 4 :
Ecrire la fonction nombreNiveaux(a) qui retourne le nombre de niveaux d’un arbre a.
Exemple :
>>> nombreNiveaux(a)
3
def nombreNiveaux(a):
if vide(a):
return (0)
else:
return (hauteur(a)+1)
Question 5 :
Ecrire la fonction indiceNiveau(n) qui retourne le numéro du nœud le plus à gauche d’un niveau n d’un
arbre binaire complet.
Aide : Liste retournée par la
fonction parcourir(a)
Indices 0 1 2 3 4 5 6
étiquettes 14 11 13 5 8 9 4
Indices niveaux : 0 1 2
Exemple :
>>> for i in range(4) : print (i , indiceNiveau(i))
...
0 0
1 1
2 3
3 7
[Link] Page 4/7
def indiceNiveau(n):
return (2**n)-1
Question 6 :
Ecrire la fonction indiceDernierNiveau(a): qui retourne l’indice du dernier niveau de l’arbre a :
Exemple :
>>> indiceDernierNiveau(A)
3
def indiceDernierNiveau(a):
if not vide(a):
n=nombreNiveaux(a)
return indiceNiveau(n-1)
Question 7 :
Donner une expression qui permet de calculer le nombre de nœuds par niveau ;
Ecrire la fonction nombreNoeudNiveau(n) qui retourne le nombre de nœuds du niveau n d’un arbre binaire
complet.
Exemple :
>>> for i in range(4) : print (i , nombreNoeudNiveau(i))
...
0 1
1 2
2 4
3 8
def nombreNoeudNiveau(n):
if not vide(a):
return 2**n
Question 8 :
Ecrire la fonction niveaux(a) qui affiche les numéros des niveaux et la liste des nœuds correspondants :
Exemple :
>>> niveaux(A)
0 : [14]
1 : [11, 13]
2 : [5, 8, 9, 4]
def niveaux2(a):
L=parcourLargeur(a)
for i in range(nombreNiveaux(a)) :
j = indiceNiveau(i)
print(i,":", L[j:j+2**i])
[Link] Page 5/7
Question 9 :
Ecrire la fonction estArbreComplet(a) qui retourne True si a est un arbre binaire complet, False sinon.
def estArbreComplet(a):
L=parcourLargeur(a)
i=indiceDernierNiveau(a)
return len(L[i:])==2**(i-1)
Arbres binaires parfait (ABP)
Un arbre binaire parfait est un arbre binaire dont tous les niveaux sont complets sauf le niveau le plus profond qui
peut être incomplet auquel cas ses nœuds sont alignés à gauche de l’arbre.
Le troisième et le quatrième arbre de l’exemple ci-dessus, sont parfaits. Le deuxième est également parfait car il
est complet.
L’arbre B ci-contre peut être représenté :
Par une liste : [racine, filsGauche, filsDroits]
B=[11,[ 5,[14,[],[]],[8,[],[]] ],[9,[13,[],[]],[]]]
Ou par une liste simple : B=[11, 5, 9, 14, 8, 13]
Un élément d'indice i de la liste (0 à n (exclu)) est considéré
comme un nœud de l'arbre ;
son fils gauche s'il existe se trouve à l'indice 2*i+1
son fils droit s'il existe se trouve à l'indice 2*i+2.
Ce nœud est une feuille si 2*i+1 est supérieur ou égal à n.
Question 10 :
Ecrire la fonction filsD(i) qui retourne l’indice du fils droit d’un nœud d’indice i.
def filsG(i) :
return 2*i+1
Question 11:
Ecrire la fonction pere(i) qui retourne l’indice du père d’un nœud d’indice i.
def filsD(i) :
return 2*(i+1)
Question 12 :
Ecrire la fonction filsG(i) qui retourne l’indice du fils gauche d’un nœud d’indice i.
def pere(i) :
return (i - 1)//2
[Link] Page 6/7
Arbres binaires parfait (ABP)
Un arbre en tas est un arbre binaire parfait tel que l’information contenue dans tout nœud est supérieure à
celle contenue dans ses fils.
Les deux arbres suivant sont en tas :
Question 13 :
Ecrire la fonction estUnTas(T) qui retourne True si le tableau T est un tas, False sinon.
def estunTas(T) :
for i in range(1,len(T)):
if T[pere(i)]<T[i]:
return False
return True
Question 14 :
Si l’on désire ajouter le nœud ayant la valeur 5 au 2ème tas de l’exemple ci-dessus expliquer sans écrire de
programme comment le faire puis dessiner l’arbre après insertion et la liste correspondante :
Avant insertion Insertion à la fin du tas
Permutation du nœud 5 avec 3 Permutation du nœud 5 avec 4
[Link] Page 7/7
