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

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

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

Que fait une fonction de hachage dans une table de hachage ?

1. AElle associe une clé à un indice de la table
2. BElle trie les clés de la table
3. CElle compte le nombre de clés stockées
4. DElle chiffre les valeurs de la table

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

1. An + 1
2. Bn − 1
3. C2n
4. Dn

Quelle structure de données est utilisée par le parcours en profondeur (DFS) dans sa version itérative ?

1. AUn tas
2. BUniquement une table de hachage
3. CUne pile
4. DUne file

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

1. AUn tas binaire d'arêtes
2. BUn unique tableau trié de sommets
3. CUne matrice d'adjacence
4. DUne liste d'adjacence

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

1. AUne liste doublement chaînée
2. BUn tableau dynamique
3. CUne liste simplement chaînée
4. DUn tableau trié

L'algorithme de Kahn pour le tri topologique retire répétitivement les sommets de degré entrant 0. Quelle structure contient ces sommets ?

1. AUne file (ou toute collection) des sommets de degré entrant 0
2. BUne pile de toutes les arêtes visitées
3. CUn tas max ordonné par degré sortant
4. DUne matrice d'adjacence indiquant quels sommets ont déjà été retirés

L'insertion d'une clé dans un arbre AVL rend le sous-arbre gauche d'un nœud trop haut, et la nouvelle clé est allée dans le sous-arbre gauche de son enfant gauche (cas gauche-gauche). Quelle correction applique-t-on ?

1. AUne rotation à gauche sur l'enfant, puis une rotation à droite sur le nœud
2. BUne rotation simple à gauche sur le nœud déséquilibré
3. CUn recoloriage du nœud et de son enfant
4. DUne rotation simple à droite sur le nœud déséquilibré