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

Dans un graphe non orienté, qu'est-ce que le degré d'un sommet ?

1. ALe nombre de sommets du graphe
2. BSa position dans la liste d'adjacence
3. CLa longueur du plus long chemin partant de lui
4. DLe nombre d'arêtes qui lui sont reliées

Que fait une fonction de hachage dans une table de hachage ?

1. AElle trie les clés de la table
2. BElle associe une clé à un indice de la table
3. CElle compte le nombre de clés stockées
4. DElle chiffre les valeurs de la table

Quelle opération est en O(1) pour un tableau mais en O(n) pour une liste simplement chaînée ?

1. ALa suppression de l'élément de tête
2. BLa lecture du premier élément
3. CL'insertion en tête
4. DL'accès à l'élément d'indice i

Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?

1. AElle est toujours triangulaire supérieure
2. BSa diagonale principale contient toujours des 1
3. CChaque ligne contient exactement un 1
4. DElle est symétrique par rapport à la diagonale principale

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

1. AUn tas binaire d'arêtes
2. BUne liste d'adjacence
3. CUne matrice d'adjacence
4. DUn unique tableau trié de sommets

Comment insère-t-on un nouvel élément dans un tas binaire ?

1. AOn le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
2. BOn le place à la racine et on le fait descendre
3. COn l'insère à sa position triée en décalant d'un cran vers la droite tous les éléments plus grands
4. DOn reconstruit entièrement le tas

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

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

Quel problème du sondage linéaire le double hachage réduit-il principalement ?

1. ALe coût en O(n) de la lecture de la valeur d'une clé
2. BLe besoin de stocker les clés dans la table
3. CLe regroupement primaire (primary clustering), où se forment de longues suites de cases occupées
4. DLe besoin d'une fonction de hachage