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. ALe sous-arbre gauche, puis le sous-arbre droit, puis le nœud
  2. BLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
  3. CNiveau par niveau en partant du haut
  4. DLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
2.Facile

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

  1. APeek (consulter)
  2. BPop (dépiler)
  3. CEnqueue (enfiler)
  4. DPush (empiler)
3.Facile

Dans un graphe, qu'est-ce qu'un cycle ?

  1. AUn sommet sans arête
  2. BUn chemin qui passe par tous les sommets
  3. CUn chemin qui commence et se termine au même sommet
  4. DUne arête de poids nul
4.Moyen

Dans un tas binaire stocké dans un tableau commençant à l'indice 0, où se trouve le parent du nœud d'indice i ?

  1. AÀ l'indice i − 1
  2. BÀ l'indice ⌊i / 2⌋ + 1
  3. CÀ l'indice ⌊(i − 1) / 2⌋
  4. DÀ l'indice 2i + 1
5.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. A1 2 4 5 3
  2. B4 5 2 3 1
  3. C4 2 5 1 3
  4. D5 4 3 2 1
6.Moyen

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

  1. ALe chaînage séparé (separate chaining)
  2. BLe sondage quadratique (quadratic probing)
  3. CLe sondage linéaire (linear probing)
  4. DLe double hachage (double hashing)
7.Difficile

Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?

  1. AO(V²)
  2. BO(V)
  3. CO(V + E)
  4. DO(E log V)
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. AIls utilisent moins de mémoire que n'importe quel tableau, si bien que tout l'index tient toujours en mémoire centrale
  2. BLeur facteur de branchement élevé maintient l'arbre peu profond, ce qui réduit les lectures disque lentes
  3. CIls n'ont pas besoin de rééquilibrage
  4. DIls stockent les données sans les trier

Corrigé

  1. 1. D · Le nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  2. 2. D · Push (empiler)
  3. 3. C · Un chemin qui commence et se termine au même sommet
  4. 4. C · À l'indice ⌊(i − 1) / 2⌋
  5. 5. B · 4 5 2 3 1
  6. 6. A · Le chaînage séparé (separate chaining)
  7. 7. A · O(V²)
  8. 8. B · 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.