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

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

1. ALe plus court chemin vers tous les autres sommets
2. BLa liste de ses sommets voisins
3. CUne ligne de V valeurs booléennes
4. DLe nombre total d'arêtes du graphe

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

1. APush (empiler)
2. BEnqueue (enfiler)
3. CPeek (consulter)
4. DPop (dépiler)

La hauteur d'un arbre est couramment définie comme :

1. ALe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille
2. BLe nombre d'arêtes du plus long chemin de la racine à une feuille
3. CLe nombre d'enfants de la racine
4. DLe nombre de feuilles de l'arbre

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

1. A1
2. B2
3. C0,5
4. DIl n'y a pas de maximum

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

1. AO(E²)
2. BO(V + E)
3. CO(V × E)
4. DO(V²)

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

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

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

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

En quoi un arbre radix (trie compressé) améliore-t-il un trie simple ?

1. AIl stocke chaque mot dans une table de hachage à la racine au lieu de nœuds distincts
2. BIl fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne
3. CIl ne garde que la première lettre de chaque mot
4. DIl trie les enfants de chaque nœud par fréquence