24-NSIJ2G11-2

  Énoncé   Sujet

1. La commandels documents affiche le contenu du répertoire documents depuis le répertoire courant home.

2. La commande déplace le répertoire multimedia (avec tout son contenu) dans le répertoire documents. Dans l'arborescence, cela revient à détacher le sous-arbre de racine multimedia, pour le rattacher ensuite sous le nœud cours.

3. La classe Arbre modèlise ici un arbre binaire, or un répertoire peut contenir plus de deux répertoires, comme documents qui en contient trois.

4. Le parcours réalisé ici est un parcours préfixe, la racine est traitée avant les sous-arbres.

5. Un parcours un largeur pourrait parcourir dans l'ordre : home documents multimedia cours administratif personnel images video films.

6. Quelques alternatives :

   def est_vide(self):
       return not self.fils
       # ou return len(self.fils) == 0
       # ou return self.fils == []
   

7. var_multimedia = Dossier(
       'multimedia', [
           Dossier('images', []),
           Dossier('videos', [Dossier('films', [])])
       ]
   )
   

8. def parcours(self):
       print(self.nom)
       for f in self.fils:
           f.parcours()
   

9. Lors des différents appels récursifs, lorqu'on atteint une feuille de l'arbre, un dossier vide, sa liste fils est aussi vide, donc cela termine la récursion.

10. def parcours(self):
        for f in self.fils:
            f.parcours() 
        print(self.nom)
    

11. La commande ls n'est par défaut récursive et liste aussi les fichiers présents.

12. def mkdir(self, nom):
        self.fils.append(Dossier(nom, []))
    

13. def contient(self, nom_dossier):
        for f in self.fils:
            if f.nom == nom_dossier or f.contient(nom_dossier):
                return True
        return False
    

14. Puisqu'un dossier de classe Dossier n'a pas un accès direct à son dossier parent, on doit explorer toute l'arborescence depuis la racine pour le retrouver, avec un parcours en profondeur par exemple. Dès qu'on découvre le dossier fils dans la descendance d'un dossier, on renvoie alors le nom de ce dernier. La méthode précédente peut donc être adaptée :

    def parent(self, nom_dossier):
        for f in self.fils:
            if f.nom == nom_dossier or f.contient(nom_dossier):
                return self.nom
        return None
    

    En conclusion, cet algorithme visite une seule fois chacun des \(n\) dossiers ainsi que chacun des \(m\) liens (ou arcs) de l'arborescence. Son coût est donc en \(O(n + m)\) dans le pire des cas.

15. Il suffirait de stocker une référence vers le dossier parent pour y accéder en temps constant \(O(1)\) :

    def __init__(self, nom, liste, parent):
        self.nom = nom
        self.fils = liste
        self.parent = parent