Dictionnaires et tables de hachage : quiz de Terminale NSI

Quiz

15 questions · correction immédiate · ton score reste sur ton appareil.

1. Que contient un dictionnaire, au sens du programme de NSI ?

   Une suite d'éléments rangés par indice et accessibles uniquement par leur positionDes couples associant une clé à une valeurUniquement des valeurs numériques triéesDes éléments accessibles seulement par le dernier entré
   Valider

2. Dans un tableau associatif, une même clé peut être associée à deux valeurs différentes en même temps.

   VraiFaux
   Valider

3. Un annuaire téléphonique est vu comme un tableau associatif. Que représentent les noms et les numéros ?

   Les noms sont les valeurs et les numéros sont les clésLes noms sont les clés et les numéros sont les valeursLes noms et les numéros sont tous deux des clésLes noms sont des fonctions de hachage
   Valider

4. Quels termes désignent le même type de données qu'un dictionnaire ? (plusieurs réponses)

   Plusieurs réponses possibles.

   Tableau associatifTable d'associationFileListe chaînée
   Valider

5. Dans une table de hachage, à quoi sert la fonction de hachage h ?

   À trier les clés par ordre croissantÀ calculer, pour une donnée d, la position de d dans la tableÀ compter le nombre d'éléments déjà stockésÀ supprimer les clés en double
   Valider

6. On utilise la fonction de hachage $h(k) = k \bmod 7$ (reste de la division euclidienne de $k$ par 7). Quelle est la position de la clé $k = 25$ dans la table ?

   Ta réponse
   Valider

7. Une table de hachage conserve l'ordre dans lequel les clés sont rangées, ce qui permet de les parcourir dans l'ordre croissant.

   VraiFaux
   Valider

8. Quelle complexité décrit la recherche d'une clé dans un dictionnaire implémenté par une table de hachage, dans le cas moyen ?

   O(n)O(log n)O(1)O(n²)
   Valider

9. Un dictionnaire contient 10 éléments, puis 10 000 éléments. Comment évolue la durée moyenne d'une recherche avec une table de hachage ?

   Elle est multipliée par 1000Elle reste du même ordre de grandeurElle est divisée par 1000Elle double à chaque nouvel élément
   Valider

10. On exécute :

    d = {"a": 1, "b": 2}
    d["a"] = 5
    d["c"] = 3
    

    Combien le dictionnaire d contient-il d'entrées à la fin ?

    Ta réponse entrées
    Valider

11. Avec $h(k) = k \bmod 7$, les clés 11 et 25 sont rangées dans la même case (position 4). Quel est le problème posé ?

    Aucun : deux clés peuvent occuper la même case sans rien prévoirDeux clés différentes demandent la même position, il faut un moyen de les stocker toutes les deuxLa table est forcément trop petite pour toute cléLa fonction h ne peut plus être utilisée
    Valider

12. Dans le pire des cas, quelle structure offre la meilleure complexité pour un tableau associatif de n éléments ?

    La table de hachage, toujours en O(1)L'arbre équilibré, en O(log n)Les deux sont strictement identiquesAucune des deux, toujours en O(n)
    Valider

13. Quels sont des avantages des arbres équilibrés par rapport aux tables de hachage ? (plusieurs réponses)

    Plusieurs réponses possibles.

    Ils préservent l'ordre des clésIls ont une meilleure complexité dans le pire des casIls ont toujours une recherche en O(1) en moyenneIls permettent de localiser efficacement une clé proche d'une valeur donnée
    Valider

14. Quel avantage les tables de hachage ont-elles en général sur l'occupation de la mémoire ?

    Leur représentation en mémoire est généralement plus compacteElles consomment toujours plus de mémoire que les arbresElles ne stockent jamais les valeursLa mémoire utilisée dépend uniquement de la fonction h
    Valider

15. À quoi servent les fonctions de hachage en cryptographie, pour un document ?

    À compresser le document pour gagner de la placeÀ associer au document une empreinte qui permet de détecter une modificationÀ traduire le document dans une autre langueÀ trier les mots du document
    Valider