Exercices: Piles, files et arbres binaires

On considère une pile initialement vide. On effectue successivement les opérations suivantes : empiler(4), empiler(7), empiler(2), depiler(), empiler(9), depiler().

1. a) Donner le contenu de la pile après chaque opération (le sommet étant indiqué).

1. b) Donner la valeur renvoyée par chacun des deux appels à depiler().

1. c) Indiquer le principe (LIFO ou FIFO) suivi par une pile.

On considère une file initialement vide. On effectue successivement : enfiler("Anna"), enfiler("Hugo"), enfiler("Léa"), defiler(), enfiler("Paul"), defiler().

1. a) Donner le contenu de la file après chaque opération (en précisant la tête et la queue).

1. b) Donner les valeurs renvoyées par les deux appels à defiler().

1. c) Indiquer le principe (LIFO ou FIFO) suivi par une file.

On considère l'arbre binaire suivant : la racine est A ; A a pour fils gauche B et pour fils droit C ; B a pour fils gauche D et pour fils droit E ; C a pour unique fils droit F ; D, E et F sont des feuilles.

1. a) Donner la taille de cet arbre.

1. b) Donner sa hauteur (en convenant que la racine seule a une hauteur de 1).

1. c) Donner la liste des feuilles.

On souhaite vérifier qu'une expression contenant des parenthèses, par exemple ((3+2)*(4-1)), est bien parenthésée, à l'aide d'une pile.

1. a) Décrire l'algorithme : que fait-on à la lecture d'une parenthèse ouvrante, puis d'une parenthèse fermante ? Quelle condition finale garantit que l'expression est bien parenthésée ?

1. b) Appliquer l'algorithme à ((3+2)*(4-1)) en donnant la taille de la pile après la lecture de chaque parenthèse.

1. c) Appliquer l'algorithme à (5*(2+1))*3) et indiquer à quel moment l'erreur est détectée.

Dans un service d'urgences de l'hôpital de Lille, les patients sont pris en charge dans l'ordre d'arrivée. On modélise la salle d'attente par une file. Arrivent dans l'ordre : Martin, Dubois, Petit, Roux. Martin est pris en charge, puis Lemaire arrive, puis deux patients sont pris en charge.

1. a) Donner l'état de la file à la fin.

1. b) Indiquer quels patients ont été pris en charge, dans l'ordre.

1. c) Écrire en Python une classe File avec les méthodes enfiler, defiler et est_vide, en utilisant une liste Python comme attribut.

Un arbre binaire a pour racine 10. Le fils gauche de 10 est 6, son fils droit est 14. Le fils gauche de 6 est 3 ; le fils droit de 6 est 8. Le fils gauche de 14 est 12 ; 14 n'a pas de fils droit.

1. a) Dessiner (décrire) l'arbre et donner sa taille et sa hauteur (on convient qu'un arbre réduit à sa seule racine a pour hauteur 1).

1. b) Donner les parcours préfixe, infixe et suffixe.

1. c) Donner le parcours en largeur.

1. d) Montrer que cet arbre est un arbre binaire de recherche.

Un arbre binaire de hauteur $h$ (la racine seule ayant pour hauteur 1) a une taille $n$.

1. a) Montrer que $h \le n \le 2^h - 1$.

1. b) En déduire un encadrement de $h$ en fonction de $n$ et justifier que $h \ge \lceil \log_2(n+1) \rceil$.

1. c) Un arbre binaire de recherche de 1 000 nœuds a au minimum quelle hauteur ? Donner la hauteur maximale et expliquer dans quel cas elle est atteinte.

On représente un arbre binaire de recherche par une classe Noeud possédant les attributs valeur, gauche et droit (ces deux derniers valant None en l'absence de fils).

1. a) Écrire une fonction récursive inserer(arbre, v) qui insère la valeur v dans l'arbre et renvoie la racine.

1. b) Dessiner l'arbre obtenu en insérant successivement 8, 3, 10, 1, 6, 14, 4, puis donner son parcours infixe.

1. c) Justifier que le parcours infixe d'un arbre binaire de recherche fournit les valeurs triées dans l'ordre croissant.

1. d) Donner la hauteur de l'arbre obtenu si l'on insère 1, 2, 3, 4, 5, 6, 7 dans cet ordre et commenter le coût d'une recherche.

On implémente une file à l'aide de deux piles entree et sortie. Pour enfiler, on empile dans entree. Pour défiler, si sortie est vide, on transfère tous les éléments de entree vers sortie (en dépilant puis empilant), puis on dépile sortie.

1. a) Exécuter la séquence : enfiler 1, 2, 3 ; défiler ; enfiler 4 ; défiler ; défiler. Donner l'état des deux piles après chaque opération.

1. b) Montrer que l'ordre FIFO est bien respecté.

1. c) Un défilement peut coûter $n$ opérations élémentaires. Montrer néanmoins que, pour $n$ éléments enfilés puis tous défilés, le coût total est en $O(n)$.