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

Que contient chaque nœud d'une liste doublement chaînée ?

1. ADes données et uniquement un pointeur vers le nœud suivant
2. BDes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
3. CDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après
4. DDeux copies des données et un pointeur

Dans un arbre, que sont des nœuds frères ?

1. ADes nœuds de même profondeur dans des sous-arbres différents
2. BDes nœuds qui ont le même parent
3. CDes nœuds qui n'ont pas d'enfant
4. DUn nœud et son parent

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

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

Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?

1. AUne table de hachage
2. BUn arbre binaire de recherche équilibré
3. CUne pile
4. DUne liste chaînée non triée

Les clés 50, 30, 70, 20, 40 sont insérées dans cet ordre dans un arbre binaire de recherche vide. Quel est l'enfant gauche de 30 ?

1. A70
2. B40
3. C20
4. D50

Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :

1. Ai/2 et i/2 + 1
2. B2i et 2i + 1
3. Ci + 1 et i + 2
4. D2i + 1 et 2i + 2

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 supprimer le besoin de redimensionner la table
3. CPour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision
4. DPour que la table de hachage soit triée

Un arbre de segments (segment tree) est généralement utilisé pour :

1. AStocker les arêtes d'un graphe
2. BRépondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)
3. CTrier des chaînes par ordre alphabétique en stockant chaque préfixe dans un nœud distinct de l'arbre
4. DImplémenter une pile