Dictionnaires et tables de hachage : exercices de Terminale NSI

Un professeur range les notes de trois élèves dans un dictionnaire Python :

notes = {"Léa": 14, "Tom": 9, "Inès": 16}

1. Quelles sont les clés ? Quelles sont les valeurs ?
2. Que renvoie notes["Tom"] ?
3. Calcule la moyenne des trois notes.

On exécute ce programme :

mot = "banane"
compteur = {}
for lettre in mot:
    if lettre in compteur:
        compteur[lettre] = compteur[lettre] + 1
    else:
        compteur[lettre] = 1

1. Donne le contenu final de compteur.
2. Quelle est la somme de toutes les valeurs du dictionnaire ?

Une fonction de hachage associe à une donnée sa position dans une table ². On définit ici une fonction très simple pour des mots en majuscules : $h(\text{mot})$ est le reste de la division par 7 de la somme des rangs des lettres dans l'alphabet (A = 1, B = 2, ..., Z = 26). La table possède 7 cases, numérotées de 0 à 6.

Rappel de quelques rangs : A = 1, C = 3, E = 5, H = 8, L = 12, N = 14, O = 15, R = 18, S = 19, T = 20, U = 21.

Calcule la position de la clé "CHAT".

On reprend la fonction de l'exercice précédent (somme des rangs, puis reste de la division par 7). On insère dans l'ordre les clés "CHAT", "LUNE", "TOUR" et "ROSE" dans la table de 7 cases.

1. Calcule la position de chaque clé.
2. Deux clés sont-elles envoyées dans la même case ? Si oui, combien de clés contient cette case ?

Pour vérifier qu'un document n'a pas été modifié, on utilise une fonction de hachage qui calcule une empreinte du document ². La fonction MD5 produit des empreintes de 128 bits, et SHA-1 des empreintes de 160 bits ². Un octet vaut 8 bits.

De combien d'octets l'empreinte SHA-1 est-elle plus longue que l'empreinte MD5 ?

Un arbre équilibré et une table de hachage peuvent représenter un tableau associatif de $n$ éléments. Dans le pire des cas, la recherche dans un arbre équilibré est en O($\log n$), alors que la table de hachage est en O(1) en moyenne ³. On suppose qu'un arbre équilibré contient $n = 1024$ éléments et que le nombre de comparaisons dans le pire des cas est de l'ordre de $\log_2 n$.

1. Estime ce nombre de comparaisons.
2. Pour quel besoin choisirais-tu l'arbre plutôt que la table de hachage ?

Un magasin range son stock dans un dictionnaire : la clé est le nom du fruit, la valeur est un couple (quantité, prix unitaire en euros).

stock = {"pomme": (12, 0.50), "poire": (10, 0.80), "kiwi": (20, 0.25)}

def valeur_totale(d):
    total = 0
    for fruit in d:
        quantite, prix = d[fruit]
        total = total + quantite * prix
    return total

1. Que contient la variable quantite lors du passage sur "poire" ?
2. Quelle valeur renvoie valeur_totale(stock) ?
3. Quelle instruction ajoute 5 bananes à 0,40 euro ?

Un dictionnaire associe chaque élève à son groupe :

groupes = {"Léa": "A", "Tom": "B", "Inès": "A"}

Écris une fonction inverser(d) qui renvoie un nouveau dictionnaire dont les clés sont les groupes et les valeurs sont les listes des élèves de ce groupe. Pour groupes, le résultat attendu est {"A": ["Léa", "Inès"], "B": ["Tom"]}.

def inverser(d):
    resultat = {}
    for eleve in d:
        g = d[eleve]
        if g not in resultat:
            resultat[g] = []
        resultat[g].append(eleve)
    return resultat