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

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

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

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

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

Dans un graphe, qu'est-ce qu'un cycle ?

1. AUn sommet sans arête
2. BUne arête de poids nul
3. CUn chemin qui passe par tous les sommets
4. DUn chemin qui commence et se termine au même sommet

Comment trouve-t-on la clé minimale dans un arbre binaire de recherche ?

1. AOn regarde uniquement la racine
2. BOn visite toutes les feuilles et on les compare
3. COn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
4. DOn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AToujours l'ordre décroissant
2. BL'ordre d'insertion
3. CL'ordre par niveaux
4. DL'ordre croissant

Les arbres AVL et les arbres rouge-noir garantissent :

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

En quoi un arbre radix (trie compressé) améliore-t-il un trie simple ?

1. AIl trie les enfants de chaque nœud par fréquence
2. BIl stocke chaque mot dans une table de hachage à la racine au lieu de nœuds distincts
3. CIl ne garde que la première lettre de chaque mot
4. DIl fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne

Dans une table de hachage à adressage ouvert, pourquoi la suppression se fait-elle souvent avec un marqueur « pierre tombale » (tombstone) ?

1. ALes clés supprimées doivent être conservées pour toujours pour des raisons de sécurité, si bien que les emplacements ne peuvent jamais être réutilisés
2. BCela rend la table triée
3. CVider l'emplacement pourrait interrompre la séquence de sondage d'autres clés
4. DLes pierres tombales accélèrent le hachage