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

Qu'est-ce qu'un graphe orienté ?

  1. AUn graphe dont toutes les arêtes ont un poids
  2. BUn graphe qui n'a pas de cycle
  3. CUn graphe dans lequel chaque paire de sommets distincts est reliée par une arête
  4. DUn graphe dont les arêtes ont une direction d'un sommet vers un autre
2.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 sous-arbre droit, puis le nœud
  3. CLe sous-arbre gauche, puis le nœud, puis le sous-arbre droit
  4. DLe nœud, puis le sous-arbre gauche, puis le sous-arbre droit
3.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 retire l'élément du sommet et le renvoie
  3. CElle renvoie l'élément du fond de la pile
  4. DElle retire tous les éléments de la pile
4.Moyen

À quoi sert un nœud sentinelle (factice) dans une liste chaînée ?

  1. AÀ simplifier le code en supprimant les cas particuliers en tête ou en queue
  2. BÀ rendre la liste triée
  3. CÀ empêcher la liste de dépasser un nombre maximal fixe de nœuds
  4. DÀ stocker le nombre d'éléments
5.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⌋
  2. BÀ l'indice i − 1
  3. CÀ l'indice 2i + 1
  4. DÀ l'indice ⌊i / 2⌋ + 1
6.Moyen

Un réseau routier compte 100,000 carrefours, chacun relié à environ 4 autres. Quelle représentation est la plus adaptée ?

  1. AUn unique tableau trié de sommets
  2. BUne matrice d'adjacence
  3. CUn tas binaire d'arêtes
  4. DUne liste d'adjacence
7.Difficile

La complexité temporelle de decrease-key dans un tas binaire (la position de l'élément étant connue) est :

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

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+ utilisent des nœuds internes binaires, ce qui réduit le nombre de lectures sur disque
  2. BTous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces
  3. CLes arbres B+ ne stockent les données que dans la racine
  4. DLes arbres B+ n'ont pas besoin d'être équilibrés

Corrigé

  1. 1. D · Un graphe dont les arêtes ont une direction d'un sommet vers un autre
  2. 2. D · Le nœud, puis le sous-arbre gauche, puis le sous-arbre droit
  3. 3. A · Elle renvoie l'élément du sommet sans le retirer
  4. 4. A · À simplifier le code en supprimant les cas particuliers en tête ou en queue
  5. 5. A · À l'indice ⌊(i − 1) / 2⌋
  6. 6. D · Une liste d'adjacence
  7. 7. A · O(log n)
  8. 8. B · Tous les enregistrements sont dans des feuilles chaînées, ce qui rend les parcours d'intervalle efficaces

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