Ep 25

▶ Télécharger le sujet en pdf.

EXERCICE 1

Écrire une fonction enumere qui prend en paramètre une liste L et renvoie un dictionnaire d dont les clés sont les éléments de L avec pour valeur associée la liste des indices de l’élément dans la liste L.

Exemple :

🐍 Script Python

    >>> enumere([1, 1, 2, 3, 2, 1])
    {1: [0, 1, 5], 2: [2, 4], 3: [3]}

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

# Mettez votre code icibksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def enumere(L):bksl-nl d = {}bksl-nl for i in range(len(L)):bksl-nl if L[i] in d:bksl-nl d[L[i]].append(i)bksl-nl else:bksl-nl d[L[i]] = [i]bksl-nl return dbksl-nlbksl-nl

---

---

EXERCICE 2

Un arbre binaire est implémenté par la classe Arbre donnée ci-dessous.

Les attributs fg et fd prennent pour valeurs des instances de la classe Arbre ou None.

    class Arbre:
        def __init__(self, etiquette):
            self.v = etiquette
            self.fg = None
            self.fd = None

    def parcours(arbre, liste):
        if arbre != None:
            parcours(arbre.fg, liste)
            liste.append(arbre.v)
            parcours(arbre.fd, liste)
        return liste

La fonction récursive parcours renvoie la liste des étiquettes des nœuds de l’arbre implémenté par l’instance arbre dans l’ordre du parcours en profondeur infixe à partir d’une liste vide passée en argument.

Compléter le code de la fonction insere qui insère un nœud d’étiquette cle en feuille de l’arbre implémenté par l’instance arbre selon la spécification indiquée et de façon que l’arbre ainsi complété soit encore un arbre binaire de recherche.

Tester ensuite ce code en utilisant la fonction parcours et en insérant successivement des nœuds d’étiquette 1, 4, 6 et 8 dans l’arbre binaire de recherche représenté ci- dessous :

Réponse

Complétez le code ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def insere(arbre, cle):bksl-nl """ arbre est une instance de la classe Arbre qui implémentebksl-nl un arbre binaire de recherche.bksl-nl """bksl-nl if ...:bksl-nl if ...:bksl-nl insere(arbre.fg, cle)bksl-nl else:bksl-nl arbre.fg = Arbre(cle)bksl-nl else:bksl-nl if ...:bksl-nl insere(arbre.fd, cle)bksl-nl else:bksl-nl arbre.fd = Arbre(cle)bksl-nlbksl-nl

---

---

Solution

###

Lancer Télécharger Téléverser Recharger Sauvegarder

def insere(arbre, cle):bksl-nl """ arbre est une instance de la classe Arbre qui implémentebksl-nl un arbre binaire de recherche.bksl-nl """bksl-nl if cle < arbre.v:bksl-nl if arbre.fg is not None:bksl-nl insere(arbre.fg, cle)bksl-nl else:bksl-nl arbre.fg = Arbre(cle)bksl-nl else:bksl-nl if arbre.fd is not None:bksl-nl insere(arbre.fd, cle)bksl-nl else:bksl-nl arbre.fd = Arbre(cle)bksl-nlbksl-nl

---

---

Exemple :

🐍 Script Python

    >>> a = Arbre(5)
    >>> insere(a, 2)
    >>> insere(a, 7)
    >>> insere(a, 3)
    >>> parcours(a, [])
    [2, 3, 5, 7]
    >>> insere(a, 1)
    >>> insere(a, 4)
    >>> insere(a, 6)
    >>> insere(a, 8)
    >>> parcours(a, [])
    [1, 2, 3, 4, 5, 6, 7, 8]