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

Un graphe est constitué de :

1. ASommets (nœuds) reliés par des arêtes
2. BUniquement des clés et des hachages
3. CLignes et colonnes
4. DUniquement une racine et des feuilles

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

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

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

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

Un trie (arbre de préfixes) est particulièrement efficace pour :

1. ALes recherches par préfixe, comme l'autocomplétion
2. BLa recherche des plus courts chemins
3. CLe tri de nombres
4. DLe stockage de matrices

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

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

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

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. A70
2. B40
3. C60
4. D80

Quelle affirmation sur le tri par tas (heapsort) est correcte ?

1. AIl s'exécute en O(n) sur toute entrée
2. BIl trie sur place en O(n log n) dans le pire cas, mais n'est pas stable
3. CIl est stable et nécessite O(n) mémoire supplémentaire
4. DIl nécessite un arbre binaire de recherche comme stockage supplémentaire, donc il utilise O(n) de mémoire en plus