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

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

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

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

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

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

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

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

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

Un arbre binaire a pour racine 1, avec 2 comme enfant gauche et 3 comme enfant droit ; le nœud 2 a pour enfants 4 (gauche) et 5 (droit). Quel est le parcours postfixe ?

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

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. AUne table plus grande est allouée et chaque clé y est réinsérée
2. BLes clés existantes sont triées sur place
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

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

1. ACompter les nœuds jusqu'à dépasser le champ de longueur de la liste
2. BTrier la liste et chercher des doublons
3. CStocker chaque nœud visité dans un ensemble haché
4. DAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent

L'insertion d'une clé dans un arbre AVL rend le sous-arbre gauche d'un nœud trop haut, et la nouvelle clé est allée dans le sous-arbre gauche de son enfant gauche (cas gauche-gauche). Quelle correction applique-t-on ?

1. AUn recoloriage du nœud et de son enfant
2. BUne rotation simple à droite sur le nœud déséquilibré
3. CUne rotation simple à gauche sur le nœud déséquilibré
4. DUne rotation à gauche sur l'enfant, puis une rotation à droite sur le nœud