Structures de données — Listes, piles, files

Distinguer pile et file

Réponds à chaque question.

1. 1.Que signifie LIFO, et quelle structure suit ce principe ?

   1 pt
   Voir la correction

   Last in, first out : le dernier entré est le premier sorti ; c’est la pile.

   Ses deux opérations, empiler et dépiler, portent sur le sommet.

2. 2.Que signifie FIFO, et comment y entre-t-on et en sort-on ?

   1 pt
   Voir la correction

   First in, first out : le premier entré est le premier sorti ; on enfile à une extrémité et on défile à l’autre.

   C’est le fonctionnement de la file.

3. 3.Sur quoi le choix entre les deux se fait-il ?

   1 pt
   Voir la correction

   Sur l’ordre de sortie attendu, jamais sur le contenu.

   Les deux structures peuvent contenir exactement les mêmes objets.

4. 4.Cite trois usages de la pile.

   1 pt
   Voir la correction

   L’annulation d’actions, l’historique de navigation, l’évaluation d’expressions parenthésées — la pile d’appels d’un programme convient aussi.

   Tous supposent de revenir en arrière dans l’ordre inverse.

5. 5.Cite trois usages de la file.

   1 pt
   Voir la correction

   La file d’impression, la gestion de requêtes, le parcours en largeur d’un graphe.

   Tous supposent un traitement dans l’ordre d’arrivée.

Comparer tableau et liste chaînée

Réponds à chaque question.

1. 1.Qu’est-ce qu’une liste chaînée ?

   1 pt
   Voir la correction

   Une suite de cellules dont chacune contient une valeur et une référence vers la suivante.

   Ses éléments ne sont pas contigus en mémoire.

2. 2.Quel est le coût d’un accès au i-ième élément dans un tableau, et dans une liste chaînée ?

   1 pt
   Voir la correction

   O(1) dans un tableau, où l’adresse se calcule ; O(n) dans une liste chaînée, où il faut suivre les références.

   C’est la contiguïté en mémoire qui fait la différence.

3. 3.Que produit une boucle qui accède par indice à chaque tour dans une liste chaînée ?

   1 pt
   Voir la correction

   Elle transforme un parcours en O(n) en un parcours en O(n²).

   Rien dans le code ne le signale.

4. 4.Énonce le compromis entre les deux structures.

   1 pt
   Voir la correction

   Le tableau donne un accès direct et une insertion coûteuse ; la liste chaînée une insertion locale bon marché et un accès coûteux.

   Aucune n’est meilleure : tout dépend de l’opération la plus fréquente.

Analyser le dictionnaire

Réponds à chaque question.

1. 1.Sur quoi repose un dictionnaire ?

   1 pt
   Voir la correction

   Sur une table de hachage : une fonction transforme la clé en un indice dans un tableau interne.

   C’est ce qui permet d’accéder à la valeur sans parcourir la structure.

2. 2.Quel est le coût de l’accès, et avec quelle réserve ?

   1 pt
   Voir la correction

   O(1) en moyenne, et non dans tous les cas.

   Si plusieurs clés produisent le même indice, il y a collision.

3. 3.Pourquoi une clé doit-elle être immuable ?

   1 pt
   Voir la correction

   Parce que si l’objet servant de clé changeait, son hachage changerait et la valeur deviendrait introuvable.

   C’est pourquoi une liste ne peut pas servir de clé.

4. 4.Que provoque une fonction de hachage mal choisie ?

   1 pt
   Voir la correction

   Elle concentre les collisions et fait retomber l’accès vers O(n).

   La performance annoncée dépend donc de la qualité du hachage.

Analyser un arbre binaire

Réponds à chaque question.

1. 1.Qu’est-ce qu’un arbre binaire ?

   1 pt
   Voir la correction

   Une structure hiérarchique où chaque nœud possède au plus deux enfants.

   Le nœud sans parent est la racine, ceux sans enfant sont les feuilles.

2. 2.Qu’est-ce que la profondeur d’un nœud et la hauteur de l’arbre ?

   1 pt
   Voir la correction

   La profondeur d’un nœud est sa distance à la racine ; la hauteur de l’arbre est la profondeur maximale.

   Les deux notions se mesurent le long des mêmes chemins.

3. 3.Quelle hauteur a un arbre équilibré de n nœuds, et qu’est-ce que cela explique ?

   1 pt
   Voir la correction

   Une hauteur de l’ordre de log n, ce qui explique l’efficacité des recherches qu’on y mène.

   Chaque descente écarte environ la moitié des nœuds restants.

4. 4.Qu’est-ce qu’un arbre dégénéré, et quelle hauteur a-t-il ?

   1 pt
   Voir la correction

   Un arbre où chaque nœud n’a qu’un seul enfant ; sa hauteur vaut n.

   Ce n’est rien d’autre qu’une liste chaînée déguisée.

Repérer une erreur et la corriger

Chaque affirmation est fausse. Écris ce qu’il fallait dire.

1. 1.« J’utilise une liste comme clé de mon dictionnaire. »

   1 pt
   Voir la correction

   Une clé doit être immuable : le hachage d’une liste modifiée changerait et la valeur deviendrait introuvable.

   C’est la raison pour laquelle le langage refuse ce type de clé.

2. 2.« L’accès à un dictionnaire est en O(1) : la performance est garantie. »

   1 pt
   Voir la correction

   Elle est en O(1) en moyenne : les collisions peuvent faire retomber l’accès vers O(n).

   Une fonction de hachage mal choisie les concentre.

3. 3.« Cet arbre binaire a n nœuds : sa hauteur est donc de l’ordre de log n. »

   1 pt
   Voir la correction

   Cela suppose qu’il soit équilibré ; un arbre dégénéré a une hauteur de n.

   Les structures d’arbres utilisées en pratique maintiennent leur équilibre pour cette raison.