EnglishCommencer

Les ensembles, structure de données

L'ensemble comme type abstrait (appartenance, ajout, retrait, union, intersection, différence ; ni doublon ni ordre) et ses trois réalisations : table de hachage, arbre trié, vecteur de bits, avec le coût de chaque opération.

  • 22 cartes
  • 5 thèmes
  • Gratuit
Réviser ce deck

Le programme, thème par thème

Le poids de chaque thème suit celui que lui donne l'examen.

  1. Notions
  2. Questions
  3. Ranger et relier
  4. Mises en situation
  5. Comprendre

Quelques cartes du deck

  • Ensemble : de quoi s'agit-il ?

    Voir la réponse

    Collection de valeurs distinctes où l'on ne demande que : une valeur y est-elle, ajouter, retirer. Aucune valeur n'y figure deux fois et aucun rang n'est garanti.

    Ajouter une valeur déjà présente ne change rien. C'est un type abstrait : table, arbre ou vecteur de bits le réalisent.

  • Qu'affiche ce programme ?

    ```python
    a = {1, 2, 2, 3}
    b = {3, 4}
    print(len(a), a & b, a - b)
    `

    • 3 {3} {1, 2}
    • 4 {3} {1, 2}
    • 3 {3, 4} {1, 2, 2}
    • 3 {1, 2} {3}
    Voir la réponse

    3 {3} {1, 2}

    Les doublons disparaissent à la construction : a vaut {1, 2, 3}, de taille 3. L'intersection garde ce qui est commun (3), la différence ce qui est dans a seul (1 et 2).

  • Un ensemble ne contient pas de … : y ajouter deux fois la même valeur laisse sa taille inchangée à la seconde fois.

    Voir la réponse

    Un ensemble ne contient pas de doublon : y ajouter deux fois la même valeur laisse sa taille inchangée à la seconde fois.

    len({1, 2, 2, 3}) vaut 3. C'est l'usage le plus courant : dédoublonner une liste avec set(liste).

  • Union, intersection, différence : de quoi s'agit-il ?

    Voir la réponse

    Les trois combinaisons de deux ensembles : tous les éléments de l'un ou de l'autre, ceux des deux à la fois, ceux du premier qui ne sont pas dans le second.

    En Python : a | b, a & b et a - b. La différence n'est pas symétrique : a - b et b - a diffèrent en général.

  • Une application garde les identifiants de commandes traitées et doit, à chaque demande, afficher les identifiants dans l'ordre croissant. Quelle réalisation d'ensemble choisir ?

    • Un ensemble arbre, qui se parcourt dans l'ordre
    • Un ensemble haché : l'ordre d'insertion est conservé
    • Un vecteur de bits, quelle que soit la plage des identifiants
    • Un ensemble haché trié à chaque demande, pour un coût en O(1)
    Voir la réponse

    Un ensemble arbre, qui se parcourt dans l'ordre

    Un arbre trié rend les éléments dans l'ordre sans effort. Un ensemble haché n'offre aucun ordre à garantir, et le trier à chaque demande coûte O(n log n). Un vecteur de bits ne convient qu'à une plage d'entiers petite et bornée.

Réviser ce deck