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

Que fait une fonction de hachage dans une table de hachage ?

1. AElle trie les clés de la table
2. BElle chiffre les valeurs de la table
3. CElle associe une clé à un indice de la table
4. DElle compte le nombre de clés stockées

Quelle structure de données utilise-t-on pour effectuer un parcours en largeur (par niveaux) d'un arbre ?

1. AUne pile
2. BUne file
3. CUne table de hachage
4. DUne file de priorité

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

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

Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?

1. AUne liste doublement chaînée
2. BUne liste simplement chaînée
3. CUn tableau trié
4. DUn tableau dynamique

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 postfixe ?

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D5 4 3 2 1

Pourquoi le parcours d'un tableau est-il souvent bien plus rapide en pratique que celui d'une liste chaînée de même longueur ?

1. ALes éléments d'un tableau sont contigus, ce qui exploite bien le cache du processeur
2. BLes tableaux utilisent moins d'instructions pour comparer les valeurs
3. CLe parcours d'un tableau est en O(1) au total, alors que celui d'une liste chaînée est en O(n)
4. DLes listes chaînées stockent toujours leurs éléments sur disque

Combien de temps faut-il pour rechercher une clé quelconque dans un tas binaire min de n éléments ?

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

Quelle structure de données permet un cache LRU (least recently used) avec get et put en O(1) ?

1. AUne table de hachage combinée à une liste doublement chaînée
2. BUn unique tableau trié
3. CUniquement un arbre binaire de recherche
4. DUniquement une pile