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. BListe triée uniquement
3. CPaires clé–valeur localisées par une fonction de hachage
4. DArbre à clés ordonnées

Qu'est-ce qui définit un arbre binaire ?

1. AChaque nœud stocke un nombre binaire
2. BChaque nœud a au plus deux enfants
3. CL'arbre a exactement deux niveaux
4. DChaque nœud a exactement deux enfants

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

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

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

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

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

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

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

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

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

Combien de temps faut-il pour rechercher une clé quelconque dans un tas binaire min de n éléments ?

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(log log n)