Aller au contenu

Index des sujets 2023

Corrigé sujet 25 - Année : 2023

Sujet 25 - 2023

Exercice 1

1
2
3
4
5
6
7
8
def enumere(L):
    d = {}
    for i  in range(len(L)):
        if L[i] in d:
            d[L[i]].append(i)
        else:
            d[L[i]] = [i]
    return d

Commentaire

On parcourt la liste par indice, si on a déjà rencontré l'élément alors on met à jour sa liste d'indice sinon on crée une clé dans le dictionnaire dont la valeur est la liste contenant l'indice.

Exercice 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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

def insere(arbre, cle):
    """ arbre est une instance de la classe Arbre qui implémente
        un arbre binaire de recherche.
    """
    if cle < arbre.v: #(1)
        if arbre.fg != None: #(2)
            insere(arbre.fg, cle)
        else:
            arbre.fg = Arbre(cle)
    else:
        if arbre.fd != None: #(3)
            insere(arbre.fd, cle)
        else:
            arbre.fd = Arbre(cle)
  1. On teste si cle est inférieure à l'étiquete du noeud, dans ce cas il faut insérer à gauche
  2. Si le fils gauche est None on insère à cet endroit, sinon on insère dans l'arbre gauche
  3. Traitement identique pour le côté droit

Attention

  • La fonction insere devrait être une méthode de la classe ABR
  • Le sujet ne précise pas le comportement à adopter si on insère une clé existante