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

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

1. ADans un seul bloc contigu, les uns à la suite des autres
2. BDans un arbre de pages mémoire
3. CDe façon dispersée, reliés par des pointeurs
4. DÀ des emplacements aléatoires choisis par un hachage

Quelle structure est généralement utilisée pour implémenter une file de priorité ?

1. AUne liste simplement chaînée non ordonnée
2. BUne chaîne de caractères
3. CUn tas (heap)
4. DUne pile (stack)

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

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

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

1. ALes tas ne contiennent jamais plus de 100 éléments
2. BToutes les clés d'un tas sont égales
3. CLes tableaux maintiennent automatiquement les clés triées, donc aucun pointeur n'est nécessaire
4. DC'est un arbre binaire complet, donc les positions suivent des formules d'indice simples

Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :

1. AUn parcours de graphe
2. BUne fonction de hachage
3. CUne file de taille fixe
4. DUn arbre binaire de recherche

Comment fonctionne l'extraction du minimum (extract-min) dans un tas binaire min ?

1. AOn déplace le dernier élément à la racine et on le fait descendre
2. BOn cherche le nouveau minimum parmi toutes les feuilles
3. COn retire le dernier élément du tableau
4. DOn retire la racine et on décale tous les éléments d'une case vers la gauche

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

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

Un nœud AVL est déséquilibré parce que le sous-arbre droit de son enfant gauche est devenu trop haut (cas gauche-droite). Quelle correction applique-t-on ?

1. AUne rotation simple à droite sur le nœud
2. BUne rotation à droite sur l'enfant gauche, puis une rotation à gauche sur le nœud
3. CUne rotation à gauche sur l'enfant gauche, puis une rotation à droite sur le nœud
4. DUne rotation simple à gauche sur le nœud