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

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

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

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

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

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

1. AÉgales à la valeur du nœud
2. BDans un ordre aléatoire
3. CInférieures à la valeur du nœud
4. DSupérieures à la valeur du nœud

Comment insère-t-on un nouvel élément dans un tas binaire ?

1. AOn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
2. BOn le place à la racine et on le fait descendre
3. COn reconstruit entièrement le tas
4. DOn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands

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

1. AOn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus
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 regarde uniquement la racine

Une table de hachage de taille 7 utilise h(k) = k mod 7 et le sondage linéaire. Après l'insertion de 10, où est stocké 17 ?

1. AÀ l'indice 4
2. BÀ l'indice 0
3. CÀ l'indice 3
4. DÀ l'indice 6

Pourquoi un serveur pourrait-il choisir sa fonction de hachage au hasard dans une famille universelle ?

1. APour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision
2. BPour supprimer le besoin de redimensionner la table
3. CPour que la table de hachage soit triée
4. DPour garantir que deux clés n'entrent jamais en collision, quelles que soient les clés envoyées par un attaquant

Quel problème du sondage linéaire le double hachage réduit-il principalement ?

1. ALe regroupement primaire (primary clustering), où se forment de longues suites de cases occupées
2. BLe coût en O(n) de la lecture de la valeur d'une clé
3. CLe besoin d'une fonction de hachage
4. DLe besoin de stocker les clés dans la table