Exercices: Structures de données et programmation orientée objet

On utilise une liste Python p comme une pile, le sommet de la pile étant la fin de la liste. On exécute les instructions suivantes.

p = []

p.append(4)

p.append(7)

a = p.pop()

p.append(2)

p.append(9)

b = p.pop()

c = p.pop()

1. Donner le contenu de la liste p après chacune des instructions p.append(...) et p.pop().

2. Donner les valeurs de a, b et c, puis le contenu final de p.

3. Indiquer si une pile obéit à la règle FIFO ou à la règle LIFO.

4. Citer une opération dont on a besoin pour savoir si une pile est vide avant d'effectuer un dépilement.

On considère la classe suivante.

class Rectangle:

    def __init__(self, largeur, longueur):

        self.largeur = largeur

        self.longueur = longueur

    def aire(self):

        return self.largeur * self.longueur

1. Indiquer les attributs de la classe Rectangle.

2. On exécute r = Rectangle(5, 3). Donner la valeur de r.aire().

3. Écrire une méthode perimetre(self) qui renvoie le périmètre du rectangle, puis donner sa valeur pour r.

4. Écrire une instruction qui crée un carré de côté 4 à l'aide de la classe Rectangle, et donner son aire.

Un professeur enregistre les notes de quatre élèves dans un dictionnaire Python.

notes = {"Léa": 14, "Hugo": 11, "Inès": 16}

notes["Hugo"] = 13

notes["Tom"] = 9

1. Donner le contenu du dictionnaire notes après exécution de ces instructions.

2. Donner la valeur de len(notes) et celle de notes["Inès"].

3. Écrire une boucle qui calcule la moyenne des notes du dictionnaire, puis donner sa valeur.

4. Indiquer ce que produit l'instruction notes["Zoé"] et proposer une façon de l'éviter.

On implémente une file à l'aide de la classe suivante.

class File:

    def __init__(self):

        self.contenu = []

    def enfiler(self, x):

        self.contenu.append(x)

    def defiler(self):

        return self.contenu.pop(0)

    def est_vide(self):

        return len(self.contenu) == 0

On exécute les instructions suivantes.

f = File()

f.enfiler(5)

f.enfiler(8)

f.enfiler(3)

a = f.defiler()

f.enfiler(1)

b = f.defiler()

1. Donner les valeurs de a et b, puis le contenu de f.contenu à la fin.

2. Justifier que cette structure respecte la règle FIFO.

3. Écrire une fonction somme(f) qui renvoie la somme des éléments d'une file f de nombres, en n'utilisant que les méthodes enfiler, defiler et est_vide, et telle que la file retrouve son contenu initial à la fin de l'appel.

4. Expliquer pourquoi on distingue l'interface d'une file de son implémentation.

On considère l'arbre binaire dont les nœuds portent des entiers, décrit ainsi.

• La racine porte la clé 8.

• Son fils gauche porte 3 et son fils droit porte 10.

• Le nœud 3 a pour fils gauche 1 et pour fils droit 6.

• Le nœud 6 a pour fils gauche 4 et pour fils droit 7.

• Le nœud 10 n'a pas de fils gauche et a pour fils droit 14.

• Le nœud 14 a pour fils gauche 13 et n'a pas de fils droit.

• Les nœuds 1, 4, 7 et 13 n'ont aucun fils.

On convient que la hauteur d'un arbre réduit à sa racine est égale à 1.

1. Déterminer la taille de l'arbre, sa hauteur et le nombre de ses feuilles.

2. Donner la liste des clés obtenues par un parcours infixe, puis par un parcours suffixe.

3. Donner la liste des clés obtenues par un parcours en largeur.

4. Justifier que cet arbre est un arbre binaire de recherche.

5. Pour un arbre binaire de taille $n = 9$, donner un encadrement de la hauteur $h$ de la forme $a \leqslant h \leqslant b$, puis vérifier que l'arbre étudié le respecte.

On considère le graphe orienté à cinq sommets numérotés de 0 à 4, représenté par ses listes de successeurs.

g = {0: [1, 2], 1: [3], 2: [3], 3: [4], 4: [1]}

1. Écrire la matrice d'adjacence de ce graphe, les sommets étant rangés dans l'ordre 0, 1, 2, 3, 4.

2. Donner la liste des prédécesseurs du sommet 3.

3. Montrer que ce graphe contient un cycle et le préciser.

4. Donner l'ordre de visite des sommets lors d'un parcours en largeur depuis le sommet 0, puis lors d'un parcours en profondeur depuis le sommet 0. On visite les successeurs d'un sommet par ordre croissant.

5. Écrire une fonction vers_matrice(g, n) qui prend en paramètres un dictionnaire de listes de successeurs et le nombre de sommets, et renvoie la matrice d'adjacence sous forme de liste de listes.

On représente un arbre binaire de recherche par des objets de la classe Noeud. L'arbre vide est représenté par None.

class Noeud:

    def __init__(self, cle):

        self.cle = cle

        self.gauche = None

        self.droit = None

def inserer(a, cle):

    if a is None:

        return ...

    if cle < a.cle:

        a.gauche = ...

    elif cle > a.cle:

        a.droit = ...

    return a

1. Compléter la fonction inserer, qui insère une clé dans un arbre binaire de recherche et renvoie la racine. Une clé déjà présente n'est pas insérée de nouveau.

2. On insère successivement, dans un arbre initialement vide, les clés 12, 5, 18, 3, 9, 15, 20.

   a) Décrire l'arbre obtenu (fils gauche et fils droit de chaque nœud) et donner sa hauteur, avec la convention qu'un arbre réduit à sa racine a pour hauteur 1.

   b) On insère ensuite 7, puis 10. Donner la nouvelle hauteur et la liste des clés obtenue par un parcours infixe.

3. On insère les mêmes sept clés dans l'ordre 3, 5, 9, 12, 15, 18, 20. Donner la hauteur de l'arbre obtenu et expliquer l'effet de l'ordre d'insertion sur le coût d'une recherche.

4. Écrire une fonction récursive hauteur(a) qui renvoie la hauteur d'un arbre (0 pour l'arbre vide).

On dispose d'une structure de pile dont l'interface est la suivante : Pile() crée une pile vide, empiler(x), depiler() (qui renvoie le sommet et le retire) et est_vide().

class Pile:

    def __init__(self):

        self.contenu = []

    def empiler(self, x):

        self.contenu.append(x)

    def depiler(self):

        return self.contenu.pop()

    def est_vide(self):

        return len(self.contenu) == 0

On évalue une expression en notation polonaise inversée, donnée sous forme de liste de chaînes. Un nombre est empilé ; un opérateur parmi "+", "-", "*" dépile deux valeurs b puis a (dans cet ordre) et empile le résultat de a opérateur b.

1. Évaluer à la main ["8", "3", "-", "4", "*"] en indiquant le contenu de la pile après chaque élément lu.

2. Évaluer de même ["5", "1", "2", "+", "4", "*", "+", "3", "-"].

3. Écrire une fonction evaluer(expr) qui renvoie la valeur d'une expression valide, en n'utilisant que l'interface de Pile.

4. On remplace l'implémentation de Pile par la suivante, fondée sur des cellules chaînées.

class Cellule:

    def __init__(self, valeur, suivante):

        self.valeur = valeur

        self.suivante = suivante

class Pile:

    def __init__(self):

        self.sommet = None

    ...

a) Écrire les méthodes `empiler`, `depiler` et `est_vide` de cette nouvelle implémentation.

b) Justifier que la fonction `evaluer` n'a pas besoin d'être modifiée.

Un graphe non orienté est représenté par le dictionnaire suivant.

g = {"A": ["B", "C"],

     "B": ["A", "D"],

     "C": ["A", "D"],

     "D": ["B", "C", "E"],

     "E": ["D"]}

1. Écrire la matrice d'adjacence de ce graphe, les sommets étant rangés dans l'ordre A, B, C, D, E.

2. Donner le degré de chaque sommet. Vérifier que la somme des degrés est égale à deux fois le nombre d'arêtes.

3. Donner un chemin de A à E comportant un nombre minimal d'arêtes, ainsi que l'ordre de visite d'un parcours en largeur depuis A (voisins pris dans l'ordre de la liste).

4. On considère la fonction suivante.

def a_cycle(g, s, parent, vus):

    vus.add(s)

    for v in g[s]:

        if v not in vus:

            if a_cycle(g, v, s, vus):

                return True

        elif v != parent:

            return True

    return False

a) Dérouler l'appel `a_cycle(g, "A", None, set())` et donner la valeur renvoyée.

b) On supprime l'arête entre C et D. Donner la nouvelle valeur renvoyée par l'appel précédent.

c) Expliquer le rôle du paramètre `parent`.