Français
Menu

Structures de données et algorithmes

Par rapport à un tableau, quelle description d'une liste chaînée (liste dont chaque élément contient un pointeur vers l'élément suivant) est correcte ?

  1. ASi l'élément situé juste avant le point d'insertion est connu, on peut insérer un nouvel élément en modifiant seulement des pointeurs, sans déplacer les autres éléments ; en revanche, lire le i-ème élément oblige à parcourir la liste depuis le début
  2. BLa position du i-ème élément se calcule, si bien que n'importe quel élément se lit en temps constant, O(1)
  3. CLes éléments sont rangés de façon contiguë en mémoire, si bien que le cache et le préchargement fonctionnent bien lors d'une lecture dans l'ordre
Afficher la réponse et l'explication

Réponse : A. Si l'élément situé juste avant le point d'insertion est connu, on peut insérer un nouvel élément en modifiant seulement des pointeurs, sans déplacer les autres éléments ; en revanche, lire le i-ème élément oblige à parcourir la liste depuis le début

Dans une liste chaînée, une fois la position connue, l'insertion et la suppression ne demandent que la réécriture des pointeurs voisins, en O(1). Lire le i-ème élément oblige en revanche à suivre i pointeurs depuis le début, en O(n). Un tableau calcule l'adresse du i-ème élément à partir de son adresse de départ et de la taille d'un élément, et lit donc n'importe quel élément en O(1), mais une insertion au milieu coûte O(n) pour décaler les éléments suivants. De plus, les éléments d'un tableau étant contigus, le cache et le préchargement fonctionnent bien, alors que les nœuds d'une liste chaînée ont tendance à être dispersés en mémoire, si bien que même un parcours en O(n) peut être beaucoup plus lent.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. Sur une pile vide, on effectue dans cet ordre les opérations push 1, push 2, pop, push 3, push 4, pop, pop. Dans quel ordre les valeurs sont-elles retirées par pop ?
  2. On ajoute dans cet ordre les éléments A, B et C à une file d'attente vide. Ensuite, on retire un élément, on ajoute D et on retire un élément, puis on ajoute E et on retire un élément. Dans quel ordre les éléments sont-ils retirés ?
  3. On évalue l'expression « 3 4 + 2 * 5 − » écrite en notation polonaise inverse (notation postfixée) en empilant chaque nombre sur une pile et, pour chaque opérateur, en retirant deux valeurs, en calculant le résultat et en l'empilant à nouveau. Quel est le résultat ? L'opérande gauche d'un opérateur est la valeur empilée la première.
  4. Quelle description d'une collision dans une table de hachage est correcte ?
  5. On range dans cet ordre les clés 10, 17, 24 et 3 dans une table de hachage de taille 7 (positions 0 à 6) avec la fonction de hachage h(k) = k mod 7. Les collisions sont résolues par sondage linéaire, qui avance d'une position à la fois (en revenant de 6 à 0) pour trouver un emplacement libre. À quelle position la clé 3 est-elle rangée ?