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

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

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

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. CLe calcul de la longueur d'un tableau de taille fixe
4. DL'accès au 5e élément

Quelle structure de données utilise-t-on pour effectuer un parcours en largeur (par niveaux) d'un arbre ?

1. AUne file de priorité
2. BUne file
3. CUne table de hachage
4. DUne pile

Combien de temps faut-il pour vérifier si l'arête (u, v) existe avec une matrice d'adjacence ?

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

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. A2^h
2. B2^h+1 − 1
3. C2h + 1
4. Dh²

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

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

Quelle garantie les règles des arbres rouge-noir donnent-elles sur la hauteur d'un arbre à n clés ?

1. ALa hauteur est au plus 2 log₂(n + 1)
2. BLa hauteur est au plus n / 2
3. CLa hauteur vaut exactement log₂ n
4. DLa hauteur est au plus log₂ n + 1

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

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