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

Combien d'arêtes possède un arbre à n nœuds ?

1. An − 1
2. B2n
3. Cn
4. Dn + 1

Dans un arbre, qu'est-ce qu'une feuille ?

1. AUn nœud sans parent
2. BUn nœud sans enfant
3. CLe nœud de plus grande valeur
4. DUn nœud ayant exactement un enfant

Qu'est-ce que la racine d'un arbre ?

1. ALe nœud ayant la plus grande valeur
2. BN'importe quel nœud au milieu
3. CLe nœud situé tout en haut, sans parent
4. DUn nœud sans enfant

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

1. AUne liste doublement chaînée
2. BUn tableau trié
3. CUn tableau dynamique
4. DUne liste simplement chaînée

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

1. AUne table de hachage
2. BUn arbre binaire de recherche
3. CUne pile
4. DUne file

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

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

Un objet est stocké comme clé dans une table de hachage (hash map), puis un champ utilisé par sa fonction de hachage est modifié. Quel est le résultat probable ?

1. ALa recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage
2. BLa table déplace automatiquement la clé dans son nouveau compartiment
3. CLa table lève une erreur au moment où le champ change
4. DRien ne change, car le hachage d'une clé n'est calculé qu'une seule fois au démarrage du programme

L'algorithme de Kahn pour le tri topologique retire répétitivement les sommets de degré entrant 0. Quelle structure contient ces sommets ?

1. AUn tas max ordonné par degré sortant
2. BUne pile de toutes les arêtes visitées
3. CUne file (ou toute collection) des sommets de degré entrant 0
4. DUne matrice d'adjacence indiquant quels sommets ont déjà été retirés