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

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
2. BNiveau par niveau en partant du haut
3. CLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
4. DLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AGraphe
2. BFile (queue)
3. CPile (stack)
4. DEnsemble haché (hash set)

Un graphe est constitué de :

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

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AToujours l'ordre décroissant
2. BL'ordre croissant
3. CL'ordre par niveaux
4. DL'ordre d'insertion

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. A2h + 1
2. Bh²
3. C2^h+1 − 1
4. D2^h

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 simplement chaînée
2. BUn tableau trié
3. CUne liste doublement chaînée
4. DUn tableau dynamique

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

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

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 pile de toutes les arêtes visitées
2. BUne matrice d'adjacence indiquant quels sommets ont déjà été retirés
3. CUne file (ou toute collection) des sommets de degré entrant 0
4. DUn tas max ordonné par degré sortant