Тест: Structures de Données et Types Abstraits — 9 въпроса

1. Quelle est la principale différence entre un type abstrait (AD) et une structure d'implémentation en programmation ?

A. Un type abstrait définit uniquement l'interface et le comportement, tandis qu'une structure d'implémentation concerne la manière dont il est concrètement réalisé en mémoire.

B. Un type abstrait concerne uniquement les langages de haut niveau, tandis qu'une structure d'implémentation concerne uniquement le langage C.

C. Un type abstrait ne peut pas être modifié après sa définition, alors qu'une structure d'implémentation peut l'être.

D. Un type abstrait est une structure concrète en mémoire, alors qu'une structure d'implémentation est une abstraction sans représentation physique.

Answer: (A)

Обяснение

Un type abstrait (AD) est défini par son domaine, ses opérations et ses axiomes, indépendamment de sa mise en œuvre concrète. La structure d'implémentation, en revanche, concerne la façon dont ce type est réalisé en mémoire ou en code, par exemple via des structures en C ou d'autres mécanismes.

2. Quelle est la principale caractéristique des types abstraits en programmation?

A. Ils sont définis par leur domaine, opérations et axiomes, indépendamment de leur implémentation.

B. Ils sont directement liés à une implémentation spécifique.

C. Ils sont uniquement utilisés pour la gestion mémoire.

D. Ils définissent exclusivement la structure des données.

Answer: (A)

Обяснение

Les types abstraits se concentrent sur leur domaine, opérations et axiomes, permettant une indépendance par rapport à l'implémentation, ce qui facilite la modularité et la généralisation.

3. Parmi les structures suivantes, laquelle est une structure arborescente utilisée pour représenter une hiérarchie ou un arbre binaire de recherche ?

A. Arbre binaire de recherche (ABR)

B. Tas (heap)

C. Tableau dynamique

D. Liste chaînée circulaire

Answer: (A)

Обяснение

L'arbre binaire de recherche (ABR) est une structure arborescente où chaque nœud possède au plus deux fils, et où la propriété de recherche permet une recherche efficace. Les autres options ne sont pas des structures arborescentes ou ne sont pas spécifiquement utilisées pour représenter une hiérarchie.

4. Quel mécanisme en C permet une gestion dynamique de la mémoire pour les structures de données?

A. malloc et free

B. new et delete

C. alloc et dealloc

D. reserve et release

Answer: (A)

Обяснение

En C, malloc permet d’allouer dynamiquement de la mémoire de taille donnée, et free libère cette mémoire, essentiels pour la gestion dynamique.

5. Quelle opération est essentielle pour maintenir la propriété d'un tas (heap) lors de l'insertion d'un nouvel élément ?

A. Recherche dichotomique

B. Heapify (réorganisation du tas)

C. Tri par fusion

D. Parcours en largeur (BFS)

Answer: (B)

Обяснение

L'opération heapify est utilisée pour réorganiser un tas après une insertion ou une extraction afin de maintenir la propriété du tas (par exemple, parent supérieur ou égal à ses enfants dans un tas max). Elle est essentielle pour assurer le bon fonctionnement des opérations sur le tas.

6. Parmi les structures fondamentales mentionnées, laquelle est une structure arborescente utilisée pour la recherche efficace?

A. L’arbre binaire de recherche (ABR)

B. La pile (LIFO)

C. La liste chaînée

D. Le tas (heap)

Answer: (A)

Обяснение

L’arbre binaire de recherche (ABR) permet une recherche efficace en organisant les données selon une hiérarchie, en respectant une propriété d’ordre.

7. Quels parcours d’arbre permettent d’explorer tous les nœuds en visitant d’abord la racine, ou ses sous-arbres dans un ordre spécifique?

A. DFS (préfixe, infixe, postfixe) pour DFS, BFS pour exploration niveau par niveau.

B. Seul le parcours BFS

C. Seul le parcours DFS

D. Les parcours ne permettent pas d'explorer tous les nœuds efficacement.

Answer: (A)

Обяснение

DFS (profondeur) et BFS (largeur) sont les deux principales méthodes pour parcourir tous les nœuds d’un arbre, chacune avec une stratégie différente d'exploration.

8. Quelle structure est utilisée dans le tri par tas (heap sort)?

A. Le tas (heap)

B. La liste chaînée

C. La table de hachage

D. L’arbre binaire de recherche

Answer: (A)

Обяснение

Le tri par tas utilise la propriété d’un tas pour organiser un tableau, puis trie en extrayant les éléments dans l’ordre correct.

9. Quelle caractéristique distingue le codage Huffman des autres méthodes de compression?

A. Il utilise un arbre de codage basé sur la fréquence des symboles, avec un codage préfixe.

B. Il est basé sur la permutation aléatoire des bits.

C. Il ne nécessite pas d’arbre de codage.

D. Il ne permet pas une compression sans perte.

Answer: (A)

Обяснение

Le codage Huffman construit un arbre basé sur la fréquence des symboles, assurant un codage préfixe sans perte et une compression efficace.