QCM : Structures de données linéaires (18 questions)

Explication

Un type abstrait définit les données et leurs opérations sans imposer leur implémentation, tout en précisant les propriétés de ces opérations. Une organisation physique en mémoire décrit plutôt une implémentation concrète.

Explication

L’interface regroupe les routines permettant d’ajouter, d’effacer et d’accéder aux données. La disposition en mémoire relève de l’implémentation, et non de l’interface.

Explication

Dans CRUD, Delete désigne la suppression d’une donnée. Update correspond à sa modification, tandis que Read sert à la lire.

Explication

Une liste regroupe des éléments ordonnés, repérés par un indice, avec un accès séquentiel. Le stockage contigu et l’accès direct caractérisent une représentation particulière, pas la définition générale d’une liste.

Explication

Le type abstrait liste décrit une structure de données sans imposer sa représentation, alors que les listes Python sont des tableaux dynamiques. Les confondre revient à attribuer au type abstrait une implémentation particulière.

Explication

La lecture à l’indice $i$ est définie lorsque $0 \leq i < \operatorname{longueur}(liste)$ ; pour une longueur de 6, les indices vont donc de 0 à 5. L’indice 6 est accepté pour une insertion, mais pas pour une lecture.

Explication

L’insertion est définie lorsque $0 \leq i \leq \operatorname{longueur}(liste)$, donc l’indice 6 est valide pour une liste de longueur 6. Contrairement à l’insertion, la lecture à cet indice n’est pas définie.

Explication

Dans une implémentation par tableau, l’accès à une valeur prend un temps constant, alors que les insertions et suppressions prennent un temps linéaire. Le temps constant pour ces modifications est plutôt associé à une liste chaînée.

Explication

Une liste chaînée est organisée linéairement, sans exiger que ses éléments soient contigus en mémoire, et ses cellules contiennent des informations et des liens. La contiguïté des valeurs de même type décrit plutôt un tableau.

Explication

L’accès à une valeur dans une liste chaînée prend un temps linéaire, tandis que l’insertion et la suppression prennent un temps constant. Les coûts d’accès constant et de modification linéaire correspondent plutôt à l’implémentation par tableau.

Explication

Une pile suit le principe LIFO : le dernier élément empilé est celui qui est accessible en premier. Le principe FIFO décrit plutôt l’ordre d’accès d’une file.

Explication

Empiler ajoute un élément au sommet et requiert une pile non pleine, tandis que dépiler retire l’élément du sommet et requiert une pile non vide. Confondre ces conditions revient à inverser les prérequis des deux opérations.

Explication

Une file suit le principe FIFO : le premier élément ajouté est le premier à être retiré, donc A est prioritaire. C serait prioritaire dans une structure LIFO telle qu’une pile.

Explication

Défiler retire et retourne l’élément en tête, ce qui exige que la file ne soit pas vide. Une file non pleine est la condition requise pour enfiler un nouvel élément.

Explication

Un dictionnaire contient des entrées formées de couples clé-valeur, et la clé sert à accéder à la valeur associée. L’accès par position correspond plutôt à l’organisation d’une liste.

Explication

Contrairement à une liste, un dictionnaire ne comporte pas d’ordre et l’accès à une valeur se fait par clé. L’accès par rang ou position décrit une organisation séquentielle plutôt que l’accès propre aux dictionnaires.

Explication

Les tables de hachage et les fonctions de hachage permettent l’accès aux valeurs d’un dictionnaire en temps constant. Un parcours séquentiel de toutes les entrées ne correspond pas à ce mécanisme d’accès.

Explication

La lecture d’une valeur et la suppression de son entrée sont définies si la recherche confirme que la clé existe. La recherche vérifie cette existence, mais l’absence de la clé ne suffit pas à autoriser la lecture ou la suppression.