Aller au contenu

Index des sujets 2023

Corrigé sujet 29 - Année : 2023

Sujet 29 - 2023

Exercice 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Arbre:
    def __init__(self, etiquette):
        self.v = etiquette
        self.fg = None
        self.fd = None

def taille(arbre):
    if arbre == None:
        return 0
    else:
        return 1 + taille(arbre.fg) + taille(arbre.fd)

def hauteur(arbre):
    if arbre == None:
        return 0
    else:
        return 1 + max(hauteur(arbre.fg), hauteur(arbre.fd))

Remarques

Les fonctions taille et hauteur devraient être des méthodes de la classe Arbre

Exercice 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def ajoute(indice, element, liste):
    nbre_elts = len(liste)
    L = [0 for i in range(nbre_elts + 1)]
    if indice < len(liste): #(1)
        for i in range(indice):
            L[i] = liste[i] #(2)
        L[indice] = element
        for i in range(indice + 1, nbre_elts + 1):
            L[i] = liste[i-1] #(3)
    else:
        for i in range(nbre_elts): #(4)
            L[i] = liste[i]
        L[nbre_elts] = element
    return L
  1. On teste si on doit insérer l'élément tout en fin de liste ou entre le début et la fin
  2. On recopie le début de la liste (jusqu'à la position d'insertion)
  3. On recopie le reste de la liste après la position d'insertion, les élément sont alors décalés d'une position puisqu'on a inséré un élément avant
  4. Ici on traite le cas où on insère tout à la fin, donc on recopie toute la liste.