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

Une table de hachage stocke les données sous forme de :

1. AArbre à clés ordonnées
2. BChaîne de longueur fixe
3. CPaires clé–valeur localisées par une fonction de hachage
4. DListe triée uniquement

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

1. ALe plus court chemin vers tous les autres sommets
2. BLa liste de ses sommets voisins
3. CLe nombre total d'arêtes du graphe
4. DUne ligne de V valeurs booléennes

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

1. ALa lecture du dernier élément par son indice
2. BL'insertion au début
3. CLe calcul de la longueur d'un tableau de taille fixe
4. DL'accès au 5e élément

Comment fonctionne l'extraction du minimum (extract-min) dans un tas binaire min ?

1. AOn cherche le nouveau minimum parmi toutes les feuilles
2. BOn retire la racine et on décale tous les éléments d'une case vers la gauche
3. COn retire le dernier élément du tableau
4. DOn déplace le dernier élément à la racine et on le fait descendre

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

1. Alog₂ n
2. B1
3. Cn (il devient une liste chaînée)
4. D√n

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

1. A10
2. B14
3. C24
4. D11

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

1. AO(E log V)
2. BO(V)
3. CO(V + E)
4. DO(V²)

Pour chaque élément d'un tableau, vous voulez le prochain élément plus grand à sa droite, en O(n) au total. Quelle structure aide ?

1. AUne file contenant toutes les paires d'éléments
2. BUne pile qui conserve les éléments en attente de leur réponse
3. CUne table de hachage de tous les éléments
4. DUn arbre binaire de recherche reconstruit pour chaque élément