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

Quelle opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

1. ALa suppression de l'élément de tête
2. BLa lecture du premier élément
3. CL'accès à l'élément d'indice i
4. DL'insertion en tête

Une table de hachage stocke les données sous forme de :

1. AListe triée uniquement
2. BChaîne de longueur fixe
3. CPaires clé–valeur localisées par une fonction de hachage
4. DArbre à clés ordonnées

Combien d'arêtes possède un arbre à n nœuds ?

1. A2n
2. Bn − 1
3. Cn + 1
4. Dn

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

1. A1
2. B2
3. CIl n'y a pas de maximum
4. D0,5

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

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

Comment fonctionne l'extraction du minimum (extract-min) dans un tas binaire min ?

1. AOn cherche le nouveau minimum parmi toutes les feuilles
2. BOn retire le dernier élément du tableau
3. COn déplace le dernier élément à la racine et on le fait descendre
4. DOn retire la racine et on décale tous les éléments d'une case vers la gauche

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

1. AUne rotation simple à droite sur le nœud
2. BUne rotation simple à gauche sur le nœud
3. CUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
4. DUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud

Dans le BST de racine 50, avec le sous-arbre gauche 30 (enfants 20, 40) et le sous-arbre droit 70 (enfants 60, 80), on supprime la racine en utilisant le successeur infixe. Quelle clé devient la nouvelle racine ?

1. A40
2. B80
3. C60
4. D70