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

Dans un arbre, qu'est-ce qu'une feuille ?

1. AUn nœud sans enfant
2. BUn nœud sans parent
3. CLe nœud de plus grande valeur
4. DUn nœud ayant exactement un enfant

Dans un arbre, que sont des nœuds frères ?

1. ADes nœuds qui n'ont pas d'enfant
2. BUn nœud et son parent
3. CDes nœuds de même profondeur dans des sous-arbres différents
4. DDes nœuds qui ont le même parent

Que contient chaque nœud d'une liste doublement chaînée ?

1. ADes données et uniquement un pointeur vers le nœud suivant
2. BDes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
3. CDeux copies des données et un pointeur
4. DDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après

Comment insère-t-on un nouvel élément dans un tas binaire ?

1. AOn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands
2. BOn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
3. COn reconstruit entièrement le tas
4. DOn le place à la racine et on le fait descendre

Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :

1. AUn parcours de graphe
2. BUne file de taille fixe
3. CUn arbre binaire de recherche
4. DUne fonction de hachage

Les arbres AVL et les arbres rouge-noir garantissent :

1. AQu'aucun nœud n'a deux enfants
2. BUne recherche en temps constant dans tous les cas
3. CQue les clés sont stockées dans l'ordre d'insertion
4. DUne hauteur en O(log n) grâce au rééquilibrage

Un arbre de segments (segment tree) est généralement utilisé pour :

1. ATrier des chaînes par ordre alphabétique en stockant chaque préfixe dans un nœud distinct de l'arbre
2. BRépondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)
3. CStocker les arêtes d'un graphe
4. DImplémenter une pile

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

1. AO(V + E)
2. BO(V²)
3. CO(E log V)
4. DO(V)