Exercice 2 - Arbres (Q3-Q15) · Bac Numérique et Sciences Informatiques Centres étrangers (Afrique) 2024 (jour 2)

Cet exercice porte sur la programmation objet, la récursivité, les arbres binaires et les systèmes d'exploitation.

Dans cet exercice, on travaille dans un environnement Linux. On considère l'arborescence de fichiers de la figure 1.

On considère le code suivant:

class Arbre:

def __init__(self, nom, g, d):

self.nom = nom

self.gauche = g

self.droit = d

def est_vide(self):

return self.gauche is None and self.droit is None

def parcours(self):

print(self.nom)

if self.gauche != None:

self.gauche.parcours()

if self.droit != None:

self.droit.parcours()

3.

Donner une raison qui justifie que le code précédent ne permet pas de modéliser l'arborescence de fichiers de la figure 1.

4.

Donner le nom du parcours réalisé par le code précédent.

5.

Donner la liste des dossiers dans l'ordre d'un parcours en largeur de l'arborescence. On ne demande pas d'écrire ce parcours en Python.

Partie B

Pour pouvoir modéliser l'arborescence de fichiers de la figure 1, on propose l'implémentation suivante. L'attribut fils est une variable de type list contenant tous les dossiers fils. Cette liste est vide dans le cas où le dossier est vide.

class Dossier:

def __init__(self, nom, liste):

self.nom = nom

self.fils = liste # liste d'objets de la classe Dossier

6.

Écrire le code Python d'une méthode est_vide qui renvoie True lorsque le dossier est vide et False sinon.

7.

Écrire le code Python permettant d'instancier une variable var_multimedia de la classe Dossier représentant le dossier multimedia de la figure 1. Attention: cela nécessite d'instancier tous les nœuds du sous-arbre de racine multimedia.

8.

Recopier et compléter sur votre copie le code Python de la méthode parcours suivante qui affiche les noms de tous les descendants d'un dossier en utilisant l'ordre préfixe.

def parcours(self):

print(...)

for f in...:

...

9.

Justifier que cette méthode parcours termine toujours sur une arborescence de fichiers.

10.

Proposer une modification de la méthode parcours pour que celle-ci effectue plutôt un parcours suffixe (ou postfixe).

11.

Expliquer la différence de comportement entre un appel à la méthode parcours de la classe Dossier et une exécution de la commande UNIX ls.

On considère la variable var_videos de type Dossier représentant le dossier videos de la figure 1. On souhaite que le code Python var_videos.mkdir("documentaires") crée un dossier documentaires vide dans le dossier var_videos.

12.

Écrire le code Python de la méthode mkdir.

13.

Écrire en Python une méthode contient(self, nom_dossier) qui renvoie True si l'arborescence de racine self contient au moins un dossier de nom nom_dossier et False sinon.

14.

Avec l'implémentation de la classe Dossier de cette partie, expliquer comment il serait possible de déterminer le dossier parent d'un dossier donné dans une arborescence donnée. On attend ici l'idée principale de l'algorithme décrite en français. On ne demande pas d'implémenter cet algorithme en Python.

15.

Proposer une modification dans la méthode __init__ de la classe Dossier qui permettrait de répondre à la question précédente beaucoup plus efficacement et expliquer votre choix.