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

Dans un arbre, que sont des nœuds frères ?

1. ADes nœuds qui ont le même parent
2. BDes nœuds qui n'ont pas d'enfant
3. CUn nœud et son parent
4. DDes nœuds de même profondeur dans des sous-arbres différents

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
2. BLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
3. CLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
4. DLe sous-arbre droit, puis le nœud, puis le sous-arbre gauche

Dans un graphe non orienté, qu'est-ce que le degré d'un sommet ?

1. ALe nombre de sommets du graphe
2. BSa position dans la liste d'adjacence
3. CLa longueur du plus long chemin partant de lui
4. DLe nombre d'arêtes qui lui sont reliées

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 4
3. CÀ l'indice 6
4. DÀ l'indice 3

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. ASeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
2. BLes clés les plus anciennes sont supprimées pour faire de la place
3. CUne table plus grande est allouée et chaque clé y est réinsérée
4. DLes clés existantes sont triées sur place

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

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

Quelle propriété un arbre rouge-noir doit-il respecter ?

1. ATout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
2. BLa racine doit être rouge
3. CTout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
4. DChaque nœud doit être rouge

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

1. AIls stockent les données sans les trier
2. BLeur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
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