Structures de données

Question 1

Pile (implémentation avec liste)

Answer 1

type 'a pile = {mutable contenu : 'a list};;
exception Empty ;;
let creerPile () = {contenu = []} ;;
let estVide s = s.contenu = [];;
let push x s = s.contenu ← x::(s.contenu);;
let pop s = match s.contenu with
	|[] -> raise Empty
	|t::q -> s.contenu ← q; t;;

let a = creerPile ();;

Question 2

File (implémentation par vecteurs circulaires)

Answer 2

let tmax = 50;;
exception Empty;;
type 'a file = {mutable contenu : 'a array; mutable deb : int ;
mutable fin : int} ;;
let creerFile elt = {contenu = Array.make tmax elt; deb = 0; fin = 0};;
let estVide f = f.fin = f.deb;;
let push f x = f.contenu.(f.fin) ← x; f.fin ← f.fin + 1 ;;
let pop f = if estVide f then raise Empty else f.deb ← f.deb + 1; f.contenu.(f.deb - 1);;

let f = creerFile 0;;

Question 3

Arité d’un sommet, profondeur d’un sommet et hauteur d’un arbre

Answer 3

Arité : nombre de fils d’un sommet
Profondeur : nombre d’arcs le séparant de la racine
Hauteur : plus grande profondeur atteinte

Question 4

1) Nombre de branches d’un arbre à n sommets
2) Nombre de feuilles d’un arbre binaire à n nœuds
3) Nombre de feuilles d’un arbre d’arité k à n nœuds

Answer 4

1) n-1 branches
2) n+1 feuilles
3) n(k-1) + 1 feuilles

Question 5

1) Hauteur h d’un arbre dont les n nœuds sont de degré ≤ 2
2) Hauteur h d’un arbre dont les n nœuds sont de degré ≤ k
3) Relation entre le nombre f de feuilles et la hauteur h d’un arbre binaire

Answer 5

1) ln (n+1) ≤ h ≤ n <=> h ≤ n ≤ 2^h - 1
2) h ≤ n ≤ (k^h - 1) / k-1
3) h < f ≤ 2^h <=> ln f ≤ h < f

Question 6

Définition d’un arbre binaire :

1) strictement équilibré
2) complet
3) équilibré

Answer 6

1) Strictement équilibré : toutes ses feuilles ont pour profondeur sa hauteur h ou h-1 (tous les étages sont complets sauf le dernier)
2) Complet : toutes ses feuilles sont à la profondeur h (tous les étages sont complets)
3) Équilibré : les hauteurs des arbres fils gauche et fils droit de tout sommet diffèrent au plus de 1

Question 7

Lien entre le nombre de nœuds n et la hauteur h dans un arbre binaire strictement équilibré. Cas de l’arbre complet.

Answer 7

2^(h-1) ≤ n ≤ 2^h - 1
Donc h ∽ ln n
Pour un arbre complet : n = 2^h - 1

Question 8

Lien entre le nombre de nœuds n et la hauteur h dans un arbre binaire équilibré.

Answer 8

Φ^h - 2 ≤ n ≤ 2^h - 1

où Φ = (1 + √5) / 2

Question 9

Nombre d’arbres binaires squelettiques à n nœuds

Answer 9

(n parmi 2n) / (n+1)

Question 10

Parcours en profondeur d’un arbre

Conventions possibles pour le traitement des nœuds et des feuilles

Answer 10

On démarre de la racine, puis on visite entièrement chaque sous-arbre le plus à gauche restant, puis entièrement le droit.
Ordre préfixe : père avant fils (pgd pour arbre binaire)
Ordre postfixe : père après fils (gdp pour arbre binaire)
Ordre infixe (pour arbre binaire) : gpd

Question 11

Parcours en largeur d’un arbre

Answer 11

Visite des sommets par ordre croissant de profondeur, de gauche à droite à profondeur égale.