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

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

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

Qu'est-ce qu'un deque (file à double extrémité) ?

1. AUne structure qui permet l'insertion et la suppression aux deux extrémités
2. BUne file triée par priorité
3. CUne file qui ne permet la suppression qu'à l'arrière
4. DDeux files distinctes partageant un même tableau

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

1. AIl ne permet l'accès qu'à une seule extrémité
2. BIl stocke des éléments dans l'ordre trié
3. CIl stocke des éléments sans doublons
4. DIl stocke des paires clé–valeur

Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?

1. Alog₂ n
2. Bn (il devient une liste chaînée)
3. C1
4. D√n

Pourquoi un tas binaire peut-il être stocké dans un tableau sans aucun pointeur ?

1. ALes tas ne contiennent jamais plus de 100 éléments
2. BLes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
3. CC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
4. DToutes les clés d'un tas sont égales

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

1. AO(n log n)
2. BO(1)
3. CO(n)
4. DO(log n)

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[3, 1, 8, 5]
2. B[1, 3, 5, 8]
3. C[1, 5, 8, 3]
4. D[1, 3, 8, 5]

Quel problème du sondage linéaire le double hachage réduit-il principalement ?

1. ALe coût en O(n) de la lecture de la valeur d'une clé
2. BLe besoin de stocker les clés dans la table
3. CLe besoin d'une fonction de hachage
4. DLe regroupement primaire (primary clustering), où se forment de longues suites de cases occupées