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

Fiche d’exercices de Structures de données gratuite et imprimable : 8 exercices, du niveau facile au niveau examen, avec corrigé. Imprimez-la ou enregistrez-la en PDF.

Nouvelle ficheS’entraîner en ligne avec indices

Pour les enseignants : gratuite à imprimer, copier et utiliser en classe. Chaque nouvelle fiche a de nouvelles valeurs et son propre corrigé. Un lien vers ExamProblems sur la page de votre cours est apprécié.

Nom: ____________________   Date: ____________

1.Facile

La hauteur d'un arbre est couramment définie comme :

  1. ALe nombre d'arêtes du plus long chemin de la racine à une feuille
  2. BLe nombre de feuilles de l'arbre
  3. CLe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille
  4. DLe nombre d'enfants de la racine
2.Facile

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

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

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 sans doublons
  3. CIl stocke des éléments dans l'ordre trié
  4. DIl stocke des paires clé–valeur
4.Moyen

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

  1. ALes clés les plus anciennes sont supprimées pour faire de la place
  2. BLes clés existantes sont triées sur place
  3. CUne table plus grande est allouée et chaque clé y est réinsérée
  4. DSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
5.Moyen

Un trie (arbre de préfixes) est particulièrement efficace pour :

  1. ALa recherche des plus courts chemins
  2. BLe tri de nombres
  3. CLes recherches par préfixe, comme l'autocomplétion
  4. DLe stockage de matrices
6.Moyen

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

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

Pourquoi les arbres B (B-trees) sont-ils utilisés dans les bases de données et les systèmes de fichiers ?

  1. ALeur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
  2. BIls n'ont pas besoin de rééquilibrage
  3. CIls utilisent moins de mémoire que n'importe quel tableau, si bien que tout l'index tient toujours en mémoire centrale
  4. DIls stockent les données sans les trier

Corrigé

  1. 1. A · Le nombre d'arêtes du plus long chemin de la racine à une feuille
  2. 2. D · Elle renvoie l'élément du sommet sans le retirer
  3. 3. B · Il stocke des éléments sans doublons
  4. 4. C · Une table plus grande est allouée et chaque clé y est réinsérée
  5. 5. C · Les recherches par préfixe, comme l'autocomplétion
  6. 6. A · 4 5 2 3 1
  7. 7. B · [1, 3, 8, 5]
  8. 8. A · Leur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes

Corrigés complets pas à pas : entraînez-vous sur ce thème sur examproblems.com.