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

Dans un arbre, que sont des nœuds frères ?

1. ADes nœuds qui ont le même parent
2. BDes nœuds qui n'ont pas d'enfant
3. CUn nœud et son parent
4. DDes nœuds de même profondeur dans des sous-arbres différents

Où se trouve le plus petit élément d'un tas binaire min ?

1. AÀ la dernière position du tableau
2. BDans la feuille la plus à gauche
3. CDans une feuille quelconque, qu'il faut chercher
4. DÀ la racine

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

1. ALe calcul de la longueur d'un tableau de taille fixe
2. BL'insertion au début
3. CL'accès au 5e élément
4. DLa lecture du dernier élément par son indice

Pourquoi un tas binaire peut-il être stocké dans un tableau sans aucun pointeur ?

1. AC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
2. BLes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
3. CToutes les clés d'un tas sont égales
4. DLes tas ne contiennent jamais plus de 100 éléments

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

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

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 sondage linéaire (linear probing)
2. BLe double hachage (double hashing)
3. CLe sondage quadratique (quadratic probing)
4. DLe chaînage séparé (separate chaining)

Un filtre de Bloom peut répondre à la question « cet élément appartient-il à l'ensemble ? » avec :

1. ADes faux négatifs possibles mais aucun faux positif
2. BDes faux positifs possibles mais aucun faux négatif
3. CDes réponses toujours exactes
4. DDes réponses uniquement pour des nombres

Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?

1. AParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
2. BParce que diviser par deux à la moitié ferait perdre des éléments
3. CPour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
4. DPour garder le tableau trié