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

La profondeur d'un nœud dans un arbre est :

1. ALe nombre de nœuds de son sous-arbre
2. BLe nombre d'enfants de ce nœud
3. CLe nombre d'arêtes de la racine jusqu'à ce nœud
4. DLe nombre d'arêtes de ce nœud jusqu'à la feuille la plus profonde

Qu'est-ce qu'un graphe pondéré ?

1. AUn graphe ayant plus d'arêtes que de sommets
2. BUn graphe stocké sur disque
3. CUn graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
4. DUn graphe dans lequel certains sommets sont plus lourds que d'autres parce qu'ils ont plus d'arêtes

Que fait une fonction de hachage dans une table de hachage ?

1. AElle chiffre les valeurs de la table
2. BElle trie les clés de la table
3. CElle compte le nombre de clés stockées
4. DElle associe une clé à un indice de la table

Un nœud d'un arbre binaire de recherche possède un sous-arbre droit. Où se trouve son successeur dans l'ordre infixe ?

1. AAu nœud le plus à droite de son sous-arbre gauche
2. BÀ son enfant droit, toujours
3. CÀ son parent, toujours
4. DAu nœud le plus à gauche de son sous-arbre droit

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

1. ALes clés existantes sont triées sur place
2. BUne table plus grande est allouée et chaque clé y est réinsérée
3. CLes clés les plus anciennes sont supprimées pour faire de la place
4. DSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

1. AUne table de hachage
2. BUn arbre binaire de recherche équilibré
3. CUne liste chaînée non triée
4. DUne pile

Dans l'algorithme de Kruskal pour l'arbre couvrant de poids minimal, à quoi sert la structure union-find ?

1. AÀ stocker la distance actuelle de chaque sommet depuis la source pendant le parcours
2. BÀ vérifier si les deux extrémités d'une arête sont déjà reliées
3. CÀ trier les arêtes par poids
4. DÀ choisir le sommet de départ

Sans union par rang ni compression de chemin, quel est le coût dans le pire cas d'une seule opération find dans une structure union-find à n éléments ?

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