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

Qu'est-ce qu'un graphe orienté ?

1. AUn graphe dont les arêtes ont une direction d'un sommet vers un autre
2. BUn graphe qui n'a pas de cycle
3. CUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête
4. DUn graphe dont toutes les arêtes ont un poids

Dans quel ordre un parcours postfixe (postorder) 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. BLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
3. CLe sous-arbre droit, puis le nœud, puis le sous-arbre gauche
4. DLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit

Quelle est la principale différence entre un tableau statique et un tableau dynamique ?

1. AUn tableau statique ne peut stocker que des nombres
2. BUn tableau dynamique stocke ses éléments dans des nœuds chaînés, ce qui lui permet de grandir un élément à la fois
3. CUn tableau dynamique peut grandir en passant à un bloc de mémoire plus grand
4. DUn tableau statique offre un accès par indice plus lent

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

1. AUne file FIFO
2. BUn ensemble sans ordre
3. CUne pile
4. DUne file de priorité min

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

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

Comment insère-t-on un nouvel élément dans un tas binaire ?

1. AOn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands
2. BOn le place à la racine et on le fait descendre
3. COn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
4. DOn reconstruit entièrement le tas

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

1. AIl est stable et nécessite O(n) mémoire supplémentaire
2. BIl trie sur place en O(n log n) dans le pire cas, mais n'est pas stable
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

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

1. AUne rotation simple à gauche sur le nœud
2. BUne rotation simple à droite sur le nœud
3. CUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud
4. DUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud