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

Que fait l'opération peek (ou top) sur une pile ?

1. AElle renvoie l'élément du sommet sans le retirer
2. BElle renvoie l'élément du fond de la pile
3. CElle retire tous les éléments de la pile
4. DElle retire l'élément du sommet et le renvoie

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 nœud, puis le sous-arbre gauche, puis le sous-arbre droit
3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
4. DLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud

Quelle structure de données convient le mieux à la fonction « annuler » (undo) d'un éditeur de texte ?

1. AEnsemble haché (hash set)
2. BFile (queue)
3. CPile (stack)
4. DGraphe

Les arbres AVL et les arbres rouge-noir garantissent :

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

Comment fonctionne l'extraction du minimum (extract-min) dans un tas binaire min ?

1. AOn retire le dernier élément du tableau
2. BOn cherche le nouveau minimum parmi toutes les feuilles
3. COn déplace le dernier élément à la racine et on le fait descendre
4. DOn retire la racine et on décale tous les éléments d'une case vers la gauche

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. C2^h+1 − 1
4. D2h + 1

Quelle propriété maintient tout B-arbre parfaitement équilibré ?

1. AToutes les feuilles sont à la même profondeur
2. BChaque nœud a exactement deux enfants
3. CLes clés ne sont stockées que dans la racine
4. DChaque nœud stocke une seule clé

Pourquoi les bases de données utilisent-elles souvent des arbres B+ plutôt que de simples B-arbres pour leurs index ?

1. ALes arbres B+ ne stockent les données que dans la racine
2. BLes arbres B+ n'ont pas besoin d'être équilibrés
3. CTous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
4. DLes arbres B+ utilisent des nœuds internes binaires, ce qui réduit le nombre de lectures sur disque