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

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

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

Qu'est-ce que la racine d'un arbre ?

1. AN'importe quel nœud au milieu
2. BLe nœud ayant la plus grande valeur
3. CLe nœud situé tout en haut, sans parent
4. DUn nœud sans enfant

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

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

Quelle condition d'équilibre un arbre AVL maintient-il en chaque nœud ?

1. ALes deux sous-arbres de chaque nœud contiennent exactement le même nombre de nœuds
2. BToutes les feuilles sont exactement à la même profondeur
3. CLes hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1
4. DChaque nœud est colorié en rouge ou en noir

Les clés 50, 30, 70, 20, 40 sont insérées dans cet ordre dans un arbre binaire de recherche vide. Quel est l'enfant gauche de 30 ?

1. A40
2. B50
3. C20
4. D70

Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?

1. AO(1), car l'indice est connu
2. BO(log n), grâce à la recherche dichotomique
3. CO(n), car les éléments suivants doivent être décalés
4. DO(n²), car chaque élément se déplace n fois

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

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

Quelle paire de parcours détermine toujours un arbre binaire unique à clés distinctes ?

1. APréfixe seul
2. BPréfixe et infixe
3. CPar niveaux seul
4. DPréfixe et postfixe