Cuestionario: Structures de données et algorithmes essentiels — 12 preguntas

1. Qu'est-ce qu'un arbre binaire dans le contexte des structures de données complexes?

A. Une organisation hiérarchique où chaque nœud possède au plus deux sous-arbres, formant une structure hiérarchique.

B. Une structure de données statique avec une taille fixe, utilisée pour stocker des matrices.

C. Une structure de données qui relie des nœuds par des arêtes sans ordre précis, comme un réseau.

D. Une structure de données linéaire composée d'éléments homogènes stockés séquentiellement.

Answer: (A)

Explicación

Un arbre binaire est une structure hiérarchique où chaque nœud a au plus deux sous-arbres, permettant une organisation hiérarchique efficace et une gestion optimale des opérations de recherche, insertion et suppression.

2. Quel auteur est mentionné comme ayant décrit la structure des tableaux à une dimension comme une organisation séquentielle dans le contenu ?

A. Lacone Degahy YAO

B. YAO

C. Lacone YAO

D. Degahy YAO

Answer: (B)

Explicación

L'auteur mentionné dans le contenu comme ayant décrit la structure des tableaux à une dimension est YAO, ce qui correspond à l'option 1.

3. Quel est le rôle principal des opérations fondamentales sur une structure de données ?

A. Elles servent uniquement à initialiser la structure et à la supprimer une fois utilisée

B. Elles permettent uniquement de visualiser la structure sans la modifier

C. Elles permettent de manipuler, d'organiser et d'explorer la structure pour en assurer l'efficacité et la cohérence

D. Elles servent à copier la structure dans une autre zone mémoire

Answer: (C)

Explicación

Les opérations fondamentales telles que la création, l'insertion, la suppression, la recherche, le parcours et la mise à jour ont pour rôle principal de manipuler, organiser et explorer la structure de données pour garantir son efficacité, sa cohérence et son adaptation aux besoins du programme.

4. Quand la notion de complexité algorithmique a-t-elle été formellement établie dans la littérature informatique ?

A. Années 1960

B. Années 1950

C. Années 1970

D. Années 1980

Answer: (A)

Explicación

La notion de complexité algorithmique, notamment la notation Big O, a été formellement établie dans la littérature informatique dans les années 1960, avec les travaux de Donald Knuth.

5. En quoi les tableaux et les listes chaînées diffèrent-ils principalement dans leur organisation et leur gestion de la mémoire?

A. Les listes chaînées ont une taille fixe et sont stockées dans une mémoire contiguë, tandis que les tableaux sont dynamiques et reliés par des pointeurs.

B. Les tableaux ont une taille fixe et sont stockés dans une mémoire contiguë, tandis que les listes chaînées sont dynamiques et reliées par des pointeurs.

C. Les tableaux permettent une insertion et une suppression efficaces en milieu de structure, contrairement aux listes chaînées.

D. Les listes chaînées ne permettent pas de gestion dynamique de la mémoire, contrairement aux tableaux.

Answer: (B)

Explicación

Les tableaux sont des structures statiques avec une taille fixe, stockés dans une mémoire contiguë, offrant un accès direct par indice. Les listes chaînées sont des structures dynamiques, où chaque nœud est relié par des pointeurs, permettant une gestion flexible de la mémoire, notamment pour l'insertion et la suppression.

6. Qui est crédité d'avoir formulé ou proposé le concept de structures non linéaires, notamment les arbres et graphes ?

A. Alan Turing

B. John von Neumann

C. Edsger Dijkstra

D. Lacone Degahy YAO

Answer: (D)

Explicación

YAO est crédité dans le contenu pour avoir décrit et proposé la notion de structures non linéaires, notamment les arbres et graphes, en tant qu'auteurs ou référents dans ce domaine.

7. Quelle est la conséquence principale de la structure d’un tableau à une dimension sur l’accès à ses éléments?

A. La taille du tableau doit être connue à l’avance.

B. L’accès à un élément est en temps constant grâce à l’indexation.

C. L’accès à un élément nécessite un parcours séquentiel.

D. Les opérations d’insertion en milieu sont très rapides.

Answer: (B)

Explicación

La structure d’un tableau à une dimension permet un accès direct à ses éléments via leur indice, ce qui garantit une opération en temps constant (O(1)).

8. Comment accéder à un élément spécifique dans un tableau à deux dimensions en programmation ?

A. En utilisant une seule boucle pour parcourir toutes les lignes.

B. En utilisant un seul indice correspondant à la ligne.

C. En utilisant la fonction de recherche binaire.

D. En utilisant deux indices, un pour la ligne et un pour la colonne.

Answer: (D)

Explicación

Pour accéder à un élément précis dans un tableau à deux dimensions, on utilise deux indices : un pour la ligne et un pour la colonne, par exemple Note[i, j]. Les autres options sont incorrectes : un seul indice ne suffit pas pour une structure à deux dimensions, une boucle seule ne permet pas un accès direct, et la recherche binaire n'est pas directement liée à l'accès par indices.

9. Quelle est la caractéristique principale des tableaux dynamiques ?

A. Ils ont une taille fixe lors de leur déclaration.

B. Ils gèrent automatiquement la mémoire sans intervention.

C. Ils ne peuvent contenir qu’un seul type d’éléments.

D. Ils permettent de redimensionner la taille lors de l'exécution.

Answer: (D)

Explicación

Les tableaux dynamiques se caractérisent par leur capacité à changer de taille lors de l'exécution du programme, grâce à l'opération 'Redimensionner', ce qui leur confère une grande flexibilité dans la gestion de collections de données de taille variable.

10. Qu'est-ce qu'une liste chaînée en informatique?

A. Une structure hiérarchique où chaque nœud peut avoir plusieurs enfants, comme dans un arbre.

B. Une structure de données où les éléments sont organisés en une file d'attente, suivant le principe FIFO.

C. Une structure de données où tous les éléments sont stockés dans un tableau contigu en mémoire.

D. Une structure de données composée d'éléments reliés par des pointeurs, permettant une gestion dynamique.

Answer: (D)

Explicación

Une liste chaînée est une structure composée de nœuds reliés par des pointeurs, où chaque nœud contient une donnée et un pointeur vers le nœud suivant, permettant une gestion dynamique efficace pour l'insertion et la suppression.

11. Selon YAO, quelle est la caractéristique principale d’un arbre binaire ?

A. Chaque nœud peut avoir un nombre illimité de sous-arbres.

B. Les nœuds n’ont pas de sous-arbres, c’est une structure plate.

C. Un nœud peut avoir un seul sous-arbre ou aucun.

D. Chaque nœud possède au plus deux sous-arbres.

Answer: (D)

Explicación

La définition de YAO indique qu’un arbre binaire est une structure hiérarchique où chaque nœud possède au plus deux sous-arbres, ce qui est la propriété essentielle qui le distingue des autres structures.

12. Quel est le rôle principal des primitives telles que création, insertion, suppression et parcours dans la gestion d’un arbre binaire?

A. Elles servent uniquement à équilibrer l’arbre pour améliorer la recherche.

B. Elles permettent de convertir l’arbre en une structure linéaire pour faciliter le traitement.

C. Elles permettent d’optimiser la mémoire de l’arbre en réduisant sa taille.

D. Elles assurent la construction, la modification, l’exploration et la destruction de la structure arbre.

Answer: (D)

Explicación

Les primitives sur arbres — création, insertion, suppression et parcours — ont pour rôle principal de construire, modifier, explorer et détruire la structure hiérarchique, permettant une gestion efficace et cohérente de l’arbre.