Fiche d’exercices de Structures de données avec corrigé

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

1. ALa lecture du dernier élément par son indice
2. BL'insertion au début
3. CL'accès au 5e élément
4. DLe calcul de la longueur d'un tableau de taille fixe

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
2. BLe sous-arbre droit, puis le nœud, puis le sous-arbre gauche
3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
4. DLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit

La profondeur d'un nœud dans un arbre est :

1. ALe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde
2. BLe nombre d'arêtes de la racine jusqu'à ce nœud
3. CLe nombre de nœuds de son sous-arbre
4. DLe nombre d'enfants de ce nœud

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

1. AUne liste chaînée non triée
2. BUne pile
3. CUn arbre binaire de recherche équilibré
4. DUne table de hachage

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

1. AÀ rendre la liste triée
2. BÀ stocker le nombre d'éléments
3. CÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
4. DÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds

Un trie (arbre de préfixes) est particulièrement efficace pour :

1. ALe tri de nombres
2. BLa recherche des plus courts chemins
3. CLes recherches par préfixe, comme l'autocomplétion
4. DLe stockage de matrices

La suppression d'un nœud ayant deux enfants dans un arbre binaire de recherche se fait généralement en :

1. AL'échangeant avec la racine
2. BReconstruisant de zéro le sous-arbre situé en dessous et en réinsérant toutes les clés qu'il contenait
3. CSupprimant tout le sous-arbre
4. DLe remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud

Quelle affirmation sur le tri par tas (heapsort) est correcte ?

1. AIl trie sur place en O(n log n) dans le pire cas, mais n'est pas stable
2. BIl est stable et nécessite O(n) mémoire supplémentaire
3. CIl s'exécute en O(n) sur toute entrée
4. DIl nécessite un arbre binaire de recherche comme stockage supplémentaire, donc il utilise O(n) de mémoire en plus