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

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AGraphe
2. BEnsemble haché (hash set)
3. CFile (queue)
4. DPile (stack)

Qu'est-ce qui définit un arbre binaire ?

1. AChaque nœud stocke un nombre binaire
2. BL'arbre a exactement deux niveaux
3. CChaque nœud a exactement deux enfants
4. DChaque nœud a au plus deux enfants

Qu'est-ce qu'un graphe pondéré ?

1. AUn graphe ayant plus d'arêtes que de sommets
2. BUn graphe stocké sur disque
3. CUn graphe dans lequel chaque arête a une valeur numérique, comme un coût ou une distance
4. DUn graphe dans lequel certains sommets sont plus lourds que d'autres parce qu'ils ont plus d'arêtes

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

1. AUne liste d'adjacence
2. BUn tas binaire d'arêtes
3. CUne matrice d'adjacence
4. DUn unique tableau trié de sommets

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. AUn arbre binaire de recherche de cadres
2. BLa pile d'appels
3. CUne table de hachage des fonctions
4. DLa file de la mémoire du tas

Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?

1. AO(1), car l'indice est connu
2. BO(n²), car chaque élément se déplace n fois
3. CO(log n), grâce à la recherche dichotomique
4. DO(n), car les éléments suivants doivent être décalés

Pourquoi un serveur pourrait-il choisir sa fonction de hachage au hasard dans une famille universelle ?

1. APour que la table de hachage soit triée
2. BPour garantir que deux clés n'entrent jamais en collision, quelles que soient les clés envoyées par un attaquant
3. CPour supprimer le besoin de redimensionner la table
4. DPour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision

Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?

1. APour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
2. BParce que diviser par deux à la moitié ferait perdre des éléments
3. CParce que l'allocateur de mémoire ne peut libérer la mémoire que par quarts de bloc
4. DPour garder le tableau trié