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

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

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

Dans un arbre, qu'est-ce qu'une feuille ?

1. ALe nœud de plus grande valeur
2. BUn nœud ayant exactement un enfant
3. CUn nœud sans parent
4. DUn nœud sans enfant

Qu'est-ce qu'un graphe orienté ?

1. AUn graphe dont les arêtes ont une direction d'un sommet vers un autre
2. BUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête
3. CUn graphe qui n'a pas de cycle
4. DUn graphe dont toutes les arêtes ont un poids

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

1. AUne file FIFO
2. BUn ensemble sans ordre
3. CUne file de priorité min
4. DUne pile

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

1. A2^h+1 − 1
2. Bh²
3. C2^h
4. D2h + 1

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

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

La complexité temporelle de decrease-key dans un tas binaire (la position de l'élément étant connue) est :

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

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

1. APour garantir que deux clés n'entrent jamais en collision, quelles que soient les clés envoyées par un attaquant
2. BPour que la table de hachage soit triée
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