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

Qu'est-ce qu'un deque (file à double extrémité) ?

1. AUne structure qui permet l'insertion et la suppression aux deux extrémités
2. BDeux files distinctes partageant un même tableau
3. CUne file qui ne permet la suppression qu'à l'arrière
4. DUne file triée par priorité

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

1. ADans un seul bloc contigu, les uns à la suite des autres
2. BDe façon dispersée, reliés par des pointeurs
3. CDans un arbre de pages mémoire
4. DÀ des emplacements aléatoires choisis par un hachage

Où se trouve le plus petit élément d'un tas binaire min ?

1. AÀ la dernière position du tableau
2. BDans la feuille la plus à gauche
3. CDans une feuille quelconque, qu'il faut chercher
4. DÀ la racine

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

1. ALa file de la mémoire du tas
2. BUn arbre binaire de recherche de cadres
3. CLa pile d'appels
4. DUne table de hachage des fonctions

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

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

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

1. AO(log n)
2. BO(1)
3. CO(n²)
4. DO(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(n)
2. BO(log n)
3. CO(1 + α), où α = n / m
4. DO(m)

Les clés 5, 3, 8, 1 sont insérées dans cet ordre dans un tas binaire min vide stocké dans un tableau. Quel est le tableau final ?

1. A[1, 3, 5, 8]
2. B[1, 3, 8, 5]
3. C[1, 5, 8, 3]
4. D[3, 1, 8, 5]