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

Qu'est-ce que le facteur de charge d'une table de hachage ?

1. ALe nombre d'éléments stockés divisé par le nombre de compartiments
2. BLe nombre de collisions survenues jusqu'ici
3. CLe nombre de compartiments divisé par la longueur moyenne des clés stockées
4. DLe temps nécessaire pour charger la table depuis le disque

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

1. AIl stocke des éléments sans doublons
2. BIl stocke des paires clé–valeur
3. CIl ne permet l'accès qu'à une seule extrémité
4. DIl stocke des éléments dans l'ordre trié

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

1. APeek (consulter)
2. BPop (dépiler)
3. CEnqueue (enfiler)
4. DPush (empiler)

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

1. Ai + 1
2. B(i + 1) mod n
3. C(i − 1) mod n
4. D2i + 1

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

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

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

1. AÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
2. BÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds
3. CÀ rendre la liste triée
4. DÀ stocker le nombre d'éléments

Quelle propriété maintient tout B-arbre parfaitement équilibré ?

1. ALes clés ne sont stockées que dans la racine
2. BChaque nœud stocke une seule clé
3. CChaque nœud a exactement deux enfants
4. DToutes les feuilles sont à la même profondeur

Dans un tampon circulaire, front == rear peut signifier vide ou plein. Quelle est une manière courante de les distinguer ?

1. AToujours vider le tampon dès que front est égal à rear, si bien que l'état est vide
2. BTenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée
3. CStocker front et rear dans la même variable
4. DChoisir une taille de tampon égale à une puissance de deux