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

Dans quel ordre un parcours préfixe (preorder) d'un arbre binaire visite-t-il les nœuds ?

  1. ANiveau par niveau en partant du haut
  2. BLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
  3. CLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  4. DLe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
2.Facile

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
3.Facile

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

  1. ALa lecture du dernier élément par son indice
  2. BL'accès au 5e élément
  3. CL'insertion au début
  4. DLe calcul de la longueur d'un tableau de taille fixe
4.Moyen

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

  1. ALes recherches par préfixe, comme l'autocomplétion
  2. BLa recherche des plus courts chemins
  3. CLe tri de nombres
  4. DLe stockage de matrices
5.Moyen

Combien de temps faut-il pour vérifier si l'arête (u, v) existe avec une matrice d'adjacence ?

  1. AO(1)
  2. BO(V)
  3. CO(E)
  4. DO(log V)
6.Moyen

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

  1. AUne table de hachage des fonctions
  2. BUn arbre binaire de recherche de cadres
  3. CLa pile d'appels
  4. DLa file de la mémoire du tas
7.Difficile

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

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

Dans un tampon circulaire, front == rear peut signifier vide ou plein. Quelle est une manière courante de les distinguer ?

  1. AToujours vider le tampon dès que front est égal à rear, si bien que l'état est vide
  2. BStocker front et rear dans la même variable
  3. CChoisir une taille de tampon égale à une puissance de deux
  4. DTenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée

Corrigé

  1. 1. C · Le nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  2. 2. A · Elle renvoie l'élément du sommet sans le retirer
  3. 3. C · L'insertion au début
  4. 4. A · Les recherches par préfixe, comme l'autocomplétion
  5. 5. A · O(1)
  6. 6. C · La pile d'appels
  7. 7. C · Leur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
  8. 8. D · Tenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée

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