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

Quelle structure de données fonctionne selon le principe « dernier entré, premier sorti » (LIFO) ?

1. AListe chaînée
2. BFile (queue)
3. CTable de hachage
4. DPile (stack)

Quelle structure de données fonctionne selon le principe « premier entré, premier sorti » (FIFO) ?

1. ATas (heap)
2. BPile (stack)
3. CFile (queue)
4. DArbre binaire

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

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

Dans une table de hachage à adressage ouvert, quel est le facteur de charge maximal possible ?

1. A2
2. B0,5
3. C1
4. DIl n'y a pas de maximum

Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?

1. AElle est toujours triangulaire supérieure
2. BElle est symétrique par rapport à la diagonale principale
3. CChaque ligne contient exactement un 1
4. DSa diagonale principale contient toujours des 1

Une table de hachage de taille 7 utilise h(k) = k mod 7 et le sondage linéaire. Après l'insertion de 10, où est stocké 17 ?

1. AÀ l'indice 3
2. BÀ l'indice 4
3. CÀ l'indice 0
4. DÀ l'indice 6

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

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

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

1. AAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
2. BCompter les nœuds jusqu'à dépasser le champ de longueur de la liste
3. CTrier la liste et chercher des doublons
4. DStocker chaque nœud visité dans un ensemble haché