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

Une table de hachage stocke les données sous forme de :

1. AChaîne de longueur fixe
2. BArbre à clés ordonnées
3. CListe triée uniquement
4. DPaires clé–valeur localisées par une fonction de hachage

Que stocke un dictionnaire (map) ?

1. AUniquement des valeurs dans l'ordre d'insertion
2. BDes paires de clés égales
3. CDes valeurs triées par taille
4. DDes paires clé–valeur à clés uniques

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

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

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 d'insertion
4. DL'ordre par niveaux

Les clés 50, 30, 70, 20, 40 sont insérées dans cet ordre dans un arbre binaire de recherche vide. Quel est l'enfant gauche de 30 ?

1. A20
2. B40
3. C70
4. D50

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

1. Ah²
2. B2^h+1 − 1
3. C2^h
4. D2h + 1

Pourquoi les arbres B (B-trees) sont-ils utilisés dans les bases de données et les systèmes de fichiers ?

1. ALeur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
2. BIls stockent les données sans les trier
3. CIls n'ont pas besoin de rééquilibrage
4. DIls utilisent moins de mémoire que n'importe quel tableau, si bien que tout l'index tient toujours en mémoire centrale

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 stocke chaque mot dans une table de hachage à la racine au lieu de nœuds distincts
4. DIl fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne