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

Dans une liste simplement chaînée, chaque nœud contient :

1. ADes données et une référence vers le nœud suivant
2. BDes données et des références vers tous les autres nœuds
3. CUniquement des données
4. DDes données et un indice

Dans un graphe non orienté, qu'est-ce que le degré d'un sommet ?

1. ASa position dans la liste d'adjacence
2. BLe nombre de sommets du graphe
3. CLe nombre d'arêtes qui lui sont reliées
4. DLa longueur du plus long chemin partant de lui

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

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

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

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

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. B5 4 3 2 1
3. C4 5 2 3 1
4. D1 2 4 5 3

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

1. A2^h
2. Bh²
3. C2h + 1
4. D2^h+1 − 1

Les clés 5, 3, 8, 1 sont insérées dans cet ordre dans un tas binaire min vide stocké dans un tableau. Quel est le tableau final ?

1. A[1, 3, 5, 8]
2. B[1, 5, 8, 3]
3. C[1, 3, 8, 5]
4. D[3, 1, 8, 5]

Un arbre de Fenwick (binary indexed tree) sur un tableau de n nombres permet quelles opérations en O(log n) ?

1. ALes requêtes de sommes préfixes et les mises à jour d'un seul élément
2. BLe tri du tableau et la recherche dichotomique
3. CL'insertion d'éléments à n'importe quelle position
4. DLa recherche de la médiane en O(1)