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

Un graphe est constitué de :

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

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

1. AUn tas (heap)
2. BUne liste simplement chaînée non ordonnée
3. CUne chaîne de caractères
4. DUne pile (stack)

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

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

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

1. AUn arbre binaire de recherche de cadres
2. BLa pile d'appels
3. CUne table de hachage des fonctions
4. DLa file de la mémoire du tas

Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :

1. AUn arbre binaire de recherche
2. BUne fonction de hachage
3. CUne file de taille fixe
4. DUn parcours de graphe

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

1. AO(L), quel que soit le nombre de mots stockés
2. BO(log n), où n est le nombre de mots
3. CO(n), où n est le nombre de mots
4. DO(L × n)

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

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

Les clés 5, 3, 8, 1 sont insérées dans cet ordre dans un tas binaire min vide stocké dans un tableau. Quel est le tableau final ?

1. A[1, 3, 5, 8]
2. B[1, 5, 8, 3]
3. C[1, 3, 8, 5]
4. D[3, 1, 8, 5]