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'enfants de la racine
  2. BLe nombre total de nœuds de l'arbre, en comptant la racine et chaque feuille
  3. CLe nombre de feuilles de l'arbre
  4. DLe nombre d'arêtes du plus long chemin de la racine à une feuille
2.Facile

Quelle structure de données utilise-t-on pour effectuer un parcours en largeur (par niveaux) d'un arbre ?

  1. AUne file de priorité
  2. BUne table de hachage
  3. CUne file
  4. DUne pile
3.Facile

Dans une représentation d'un graphe par listes d'adjacence, que stocke-t-on pour chaque sommet ?

  1. ALa liste de ses sommets voisins
  2. BUne ligne de V valeurs booléennes
  3. CLe plus court chemin vers tous les autres sommets
  4. DLe nombre total d'arêtes du graphe
4.Moyen

Quelle est la valeur de l'expression postfixée 3 4 + 2 * ?

  1. A11
  2. B10
  3. C14
  4. D24
5.Moyen

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

  1. ALes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
  2. BLes tas ne contiennent jamais plus de 100 éléments
  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
6.Moyen

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

  1. A(i − 1) mod n
  2. B2i + 1
  3. C(i + 1) mod n
  4. Di + 1
7.Difficile

Pourquoi un serveur pourrait-il choisir sa fonction de hachage au hasard dans une famille universelle ?

  1. APour supprimer le besoin de redimensionner la table
  2. BPour garantir que deux clés n'entrent jamais en collision, quelles que soient les clés envoyées par un attaquant
  3. CPour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision
  4. DPour que la table de hachage soit triée
8.Difficile

Quelle propriété un arbre rouge-noir doit-il respecter ?

  1. ATout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
  2. BLa racine doit être rouge
  3. CChaque nœud doit être rouge
  4. DTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs

Corrigé

  1. 1. D · Le nombre d'arêtes du plus long chemin de la racine à une feuille
  2. 2. C · Une file
  3. 3. A · La liste de ses sommets voisins
  4. 4. C · 14
  5. 5. C · C'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
  6. 6. C · (i + 1) mod n
  7. 7. C · Pour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision
  8. 8. D · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs

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