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

Quelle opération est lente dans un tableau mais rapide en tête d'une liste chaînée ?

1. AL'insertion au début
2. BLa lecture du dernier élément par son indice
3. CLe calcul de la longueur d'un tableau de taille fixe
4. DL'accès au 5e élément

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

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

Dans un graphe, qu'est-ce qu'un cycle ?

1. AUn chemin qui commence et se termine au même sommet
2. BUn chemin qui passe par tous les sommets
3. CUn sommet sans arête
4. DUne arête de poids nul

Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :

1. A2i + 1 et 2i + 2
2. Bi + 1 et i + 2
3. C2i et 2i + 1
4. Di/2 et i/2 + 1

Quelle méthode de résolution des collisions stocke les clés en collision dans une liste au sein du même compartiment ?

1. ALe sondage quadratique (quadratic probing)
2. BLe double hachage (double hashing)
3. CLe chaînage séparé (separate chaining)
4. DLe sondage linéaire (linear probing)

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. AUne table plus grande est allouée et chaque clé y est réinsérée
2. BLes clés les plus anciennes sont supprimées pour faire de la place
3. CSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
4. DLes clés existantes sont triées sur place

Comment détecter si une liste simplement chaînée contient un cycle avec O(1) mémoire supplémentaire ?

1. ACompter les nœuds jusqu'à dépasser le champ de longueur de la liste
2. BTrier la liste et chercher des doublons
3. CAvancer un pointeur d'un pas et un autre de deux pas, et vérifier s'ils se rencontrent
4. DStocker chaque nœud visité dans un ensemble haché

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