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

Qu'est-ce que la propriété de tas max ?

1. ALa clé de chaque enfant gauche est supérieure ou égale à celle de son frère droit
2. BLa clé de chaque parent est supérieure ou égale aux clés de ses enfants
3. CLes clés sont triées de gauche à droite
4. DToutes les feuilles contiennent la clé maximale

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 dont toutes les arêtes ont un poids
4. DUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête

Dans un graphe, qu'est-ce qu'un cycle ?

1. AUne arête de poids nul
2. BUn sommet sans arête
3. CUn chemin qui commence et se termine au même sommet
4. DUn chemin qui passe par tous les sommets

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

1. AIl n'y a pas de maximum
2. B0,5
3. C1
4. D2

Quelle quantité de mémoire une matrice d'adjacence utilise-t-elle pour un graphe à V sommets ?

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

Dans un tas binaire stocké dans un tableau commençant à l'indice 0, où se trouve le parent du nœud d'indice i ?

1. AÀ l'indice ⌊i / 2⌋ + 1
2. BÀ l'indice ⌊(i − 1) / 2⌋
3. CÀ l'indice 2i + 1
4. DÀ l'indice i − 1

Un objet est stocké comme clé dans une table de hachage (hash map), puis un champ utilisé par sa fonction de hachage est modifié. Quel est le résultat probable ?

1. ALa table lève une erreur au moment où le champ change
2. BRien ne change, car le hachage d'une clé n'est calculé qu'une seule fois au démarrage du programme
3. CLa recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage
4. DLa table déplace automatiquement la clé dans son nouveau compartiment

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

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