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

Que stocke un dictionnaire (map) ?

1. ADes paires de clés égales
2. BDes paires clé–valeur à clés uniques
3. CUniquement des valeurs dans l'ordre d'insertion
4. DDes valeurs triées par taille

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

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

Dans quel ordre un parcours préfixe (preorder) 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. BNiveau par niveau en partant du haut
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

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. Ah²
2. B2h + 1
3. C2^h
4. D2^h+1 − 1

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AL'ordre croissant
2. BL'ordre d'insertion
3. CToujours l'ordre décroissant
4. DL'ordre par niveaux

Comment trouve-t-on la clé minimale dans un arbre binaire de recherche ?

1. AOn suit les enfants gauches depuis la racine jusqu'à ce qu'il n'y en ait plus
2. BOn visite toutes les feuilles et on les compare
3. COn suit les enfants droits depuis la racine jusqu'à ce qu'il n'y en ait plus
4. DOn regarde uniquement la racine

Dans une table de hachage à adressage ouvert, pourquoi la suppression se fait-elle souvent avec un marqueur « pierre tombale » (tombstone) ?

1. ALes clés supprimées doivent être conservées pour toujours pour des raisons de sécurité, si bien que les emplacements ne peuvent jamais être réutilisés
2. BLes pierres tombales accélèrent le hachage
3. CCela rend la table triée
4. DVider l'emplacement pourrait interrompre la séquence de sondage d'autres clés

Quels sont les coûts en temps et en espace supplémentaire de l'inversion sur place d'une liste simplement chaînée ?

1. AO(n log n) en temps et O(1) en espace supplémentaire
2. BO(1) en temps et O(1) en espace supplémentaire
3. CO(n) en temps et O(1) en espace supplémentaire
4. DO(n) en temps et O(n) en espace supplémentaire