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

Dans un arbre binaire de recherche, les valeurs du sous-arbre gauche d'un nœud sont :

1. ADans un ordre aléatoire
2. BÉgales à la valeur du nœud
3. CSupérieures à la valeur du nœud
4. DInférieures à la valeur du nœud

Dans un graphe non orienté, qu'est-ce que le degré d'un sommet ?

1. ALa longueur du plus long chemin partant de lui
2. BSa position dans la liste d'adjacence
3. CLe nombre d'arêtes qui lui sont reliées
4. DLe nombre de sommets du graphe

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

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

Un arbre binaire a pour racine 1, avec 2 comme enfant gauche et 3 comme enfant droit ; le nœud 2 a pour enfants 4 (gauche) et 5 (droit). Quel est le parcours postfixe ?

1. A4 2 5 1 3
2. B4 5 2 3 1
3. C5 4 3 2 1
4. D1 2 4 5 3

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

1. ALe chaînage séparé (separate chaining)
2. BLe sondage linéaire (linear probing)
3. CLe sondage quadratique (quadratic probing)
4. DLe double hachage (double hashing)

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 droits depuis la racine jusqu'à ce qu'il n'y en ait plus
4. DOn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus

Pourquoi les bases de données utilisent-elles souvent des arbres B+ plutôt que de simples B-arbres pour leurs index ?

1. ALes arbres B+ ne stockent les données que dans la racine
2. BTous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
3. CLes arbres B+ utilisent des nœuds internes binaires, ce qui réduit le nombre de lectures sur disque
4. DLes arbres B+ n'ont pas besoin d'être équilibrés

La complexité temporelle de decrease-key dans un tas binaire (la position de l'élément étant connue) est :

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