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

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

1. ADe façon dispersée, reliés par des pointeurs
2. BDans un seul bloc contigu, les uns à la suite des autres
3. CDans un arbre de pages mémoire
4. DÀ des emplacements aléatoires choisis par un hachage

Dans un arbre, qu'est-ce qu'une feuille ?

1. ALe nœud de plus grande valeur
2. BUn nœud sans enfant
3. CUn nœud ayant exactement un enfant
4. DUn nœud sans parent

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

1. AUn tableau statique offre un accès par indice plus lent
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 ne peut stocker que des nombres

Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?

1. AO(log n), grâce à la recherche dichotomique
2. BO(n²), car chaque élément se déplace n fois
3. CO(1), car l'indice est connu
4. DO(n), car les éléments suivants doivent être décalés

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

1. AUn tas
2. BUne pile
3. CUne file
4. DUniquement une table de hachage

Une table de hachage de taille 7 utilise h(k) = k mod 7 et le sondage linéaire. Après l'insertion de 10, où est stocké 17 ?

1. AÀ l'indice 0
2. BÀ l'indice 6
3. CÀ l'indice 4
4. DÀ l'indice 3

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

1. AIl s'exécute en O(n) sur toute entrée
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 trie sur place en O(n log n) dans le pire cas, mais n'est pas stable

Dans le BST de racine 50, avec le sous-arbre gauche 30 (enfants 20, 40) et le sous-arbre droit 70 (enfants 60, 80), on supprime la racine en utilisant le successeur infixe. Quelle clé devient la nouvelle racine ?

1. A60
2. B40
3. C70
4. D80