Scribd
Importer
21 vues2 pages

DS Tsi

Le document présente un devoir surveillé en informatique pour la classe 2TSI1, portant sur les arbres binaires de recherche et les graphes. Il contient des exercices demandant de tracer des arbres et des graphes, de démontrer des propriétés mathématiques, et d'écrire des fonctions spécifiques en programmation. Les questions incluent des concepts tels que les rotations d'arbres, les parcours infixes, et l'algorithme de Dijkstra pour les graphes.

Transféré par

Hiba Allah El Ahnaf
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
21 vues2 pages

DS Tsi

Le document présente un devoir surveillé en informatique pour la classe 2TSI1, portant sur les arbres binaires de recherche et les graphes. Il contient des exercices demandant de tracer des arbres et des graphes, de démontrer des propriétés mathématiques, et d'écrire des fonctions spécifiques en programmation. Les questions incluent des concepts tels que les rotations d'arbres, les parcours infixes, et l'algorithme de Dijkstra pour les graphes.

Transféré par

Hiba Allah El Ahnaf
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Classe 2TSI1 ✍ Informatique

CPGE Salmane Al farissi Salé. ✍ Devoir surveillé N°2 El Hadiq

EXERCICE 1 Les Arbres Binaires de recherche

— Question 1 : Tracez tous les arbres binaires de recherche contenant les


clés 1, 2, 3 et 4.

— Question 2 : Démontrez par récurrence sur la hauteur de l’arbre que le


parcours infixe d’un arbre binaire de recherche A visite les nœuds de A
dans l’ordre croissant (du plus petit au plus grand).

— Question 3 : Écrire une fonction est ABR(A) qui renvoie True si et seule-
ment si l’arbre binaire passé en paramètre est un arbre binaire de re-
cherche, et calculer sa complexité en fonction du nombre de nœuds de A.

Remarque : on pourra écrire une fonction auxiliaire min max(A) qui


prend comme argument un arbre binaire (non vide) A et qui détermine
les valeurs minimales et maximales contenues dans cet arbre binaire,
c’est-à-dire retourne un tuple (minVal, maxVal).

Dans cette partie, nous définissons deux opérations de rotation d’un arbre
binaire : la rotation gauche et la rotation droite (cette dernière se déduit aisément
de la rotation gauche par symétrie). La figure ci-après illustre l’effet d’une ro-
tation (gauche ou droite) sur un arbre binaire :

— Question 4 : Écrire deux fonctions rotationGauche(A) et rotationDroite(A)


prenant en entrée un arbre binaire A non vide, et qui réalisent ces trans-
formations.

— Question 5 : Démontrer que toute rotation préserve la propriété d’être


un arbre binaire de recherche.

Page 1
— Question 6 : Étant donné un arbre binaire de recherche A et deux nombres
k1 et k2 (avec k1 < k2 ), écrire une fonction interval(A, k1, k2) qui affiche
tous les nœuds de A dont les valeurs appartiennent à l’intervalle [k1 , k2 ].

— Question 7 : Donner l’algorithme de parcours infixe (parcours itératif).


Indication : utiliser une pile.

EXERCICE 2 Les Graphes

Question
 1 :
Tracer le graphe orienté correspondant à la matrice d’adjacence
0 1 1 1
0 0 1 0
 
1 1 0 0
1 0 1 0
Question
 2 : Tracer le graphe non-orienté correspondant à la matrice d’ad-
0 1 1 1
1 0 1 0
jacence 
1 1 0 0

1 0 0 0
Question 3 : Tracer
 le graphe pondéré correspondant à la matrice de pondération
∞ 4 2 1

 3 ∞ 1 1 
∞ 2 ∞ ∞
 

3 ∞ ∞ ∞
Question 4 : Considérant le graphe pondéré suivant,

a) Decrire sa matrice de pondération (sommets pris dans l’ordre alphabétique)


b) Determine à l’aide de the algorithm of Dijkstra, la chaı̂ne minimale de A à
F.
Question 5 : Définir une fonction connexe (G : list or dict) − > bool, qui
précise si le graphe défini par sa matrice d’adjacence ou un dictionnaire de
listes est connexe.
Un graphe connexe est un graphe non orienté dans lequel il existe un chemin
entre chaque paire de sommets. Autrement dit, on peut parcourir le graphe
d’un sommet quelconque à un autre en suivant ses arêtes.

Page 2

Vous aimerez peut-être aussi