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

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

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

Où se trouve le plus petit élément d'un tas binaire min ?

1. ADans la feuille la plus à gauche
2. BÀ la racine
3. CÀ la dernière position du tableau
4. DDans une feuille quelconque, qu'il faut chercher

Un graphe est constitué de :

1. ASommets (nœuds) reliés par des arêtes
2. BLignes et colonnes
3. CUniquement une racine et des feuilles
4. DUniquement des clés et des hachages

Quelle structure de données utilise-t-on pour vérifier si les parenthèses de "{[()]}" sont équilibrées ?

1. AUn arbre binaire de recherche
2. BUne pile
3. CUne table de hachage
4. DUne file

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

1. ALes clés existantes sont triées sur place
2. BSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
3. CLes clés les plus anciennes sont supprimées pour faire de la place
4. DUne table plus grande est allouée et chaque clé y est réinsérée

Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?

1. AO(1), car l'indice est connu
2. BO(log n), grâce à la recherche dichotomique
3. CO(n²), car chaque élément se déplace n fois
4. DO(n), car les éléments suivants doivent être décalés

Quel est le principal avantage d'une liste à enjambements (skip list) par rapport à une liste chaînée triée ?

1. AElle stocke les clés sans ordre
2. BUne recherche en O(log n) en moyenne grâce à plusieurs niveaux de pointeurs avant
3. CElle n'utilise aucune mémoire supplémentaire
4. DUne recherche en O(1) garantie, car chaque nœud stocke un pointeur vers tous les autres nœuds

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

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