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

Dans quel ordre un parcours postfixe (postorder) d'un arbre binaire visite-t-il les nœuds ?

1. ALe sous-arbre droit, puis le nœud, puis le sous-arbre gauche
2. BLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
4. DLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit

Combien d'arêtes possède un arbre à n nœuds ?

1. An + 1
2. Bn
3. Cn − 1
4. D2n

Qu'est-ce qui définit un arbre binaire ?

1. AChaque nœud stocke un nombre binaire
2. BL'arbre a exactement deux niveaux
3. CChaque nœud a au plus deux enfants
4. DChaque nœud a exactement deux enfants

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 5 2 3 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D5 4 3 2 1

Les arbres AVL et les arbres rouge-noir garantissent :

1. AQue les clés sont stockées dans l'ordre d'insertion
2. BUne recherche en temps constant dans tous les cas
3. CQu'aucun nœud n'a deux enfants
4. DUne hauteur en O(log n) grâce au rééquilibrage

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

1. AÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
2. BÀ stocker le nombre d'éléments
3. CÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds
4. DÀ rendre la liste triée

La structure union-find (ensembles disjoints) avec union par rang et compression de chemin a un coût amorti par opération de :

1. AO(n)
2. BExactement O(log n)
3. CO(n²)
4. DO(α(n)), l'inverse de la fonction d'Ackermann, pratiquement constant

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