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

Que fait l'opération peek (ou top) sur une pile ?

1. AElle renvoie l'élément du fond de la pile
2. BElle retire tous les éléments de la pile
3. CElle retire l'élément du sommet et le renvoie
4. DElle renvoie l'élément du sommet sans le retirer

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

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

Qu'est-ce que le facteur de charge d'une table de hachage ?

1. ALe nombre de collisions survenues jusqu'ici
2. BLe temps nécessaire pour charger la table depuis le disque
3. CLe nombre d'éléments stockés divisé par le nombre de compartiments
4. DLe nombre de compartiments divisé par la longueur moyenne des clés stockées

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

1. AO(n), où n est le nombre de mots
2. BO(log n), où n est le nombre de mots
3. CO(L), quel que soit le nombre de mots stockés
4. DO(L × n)

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 préfixe ?

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

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

Sous l'hypothèse de hachage uniforme simple, quel est le temps attendu d'une recherche dans une table de hachage à chaînage contenant n clés et m compartiments ?

1. AO(log n)
2. BO(n)
3. CO(m)
4. DO(1 + α), où α = n / m

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(V + E)
2. BO(V²)
3. CO(E log V)
4. DO(V)