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

Qu'est-ce que la propriété de tas max ?

1. ALa clé de chaque enfant gauche est supérieure ou égale à celle de son frère droit
2. BLa clé de chaque parent est supérieure ou égale aux clés de ses enfants
3. CToutes les feuilles contiennent la clé maximale
4. DLes clés sont triées de gauche à droite

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

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

Combien d'arêtes possède un arbre à n nœuds ?

1. An − 1
2. Bn + 1
3. C2n
4. Dn

Combien de temps faut-il pour vérifier si l'arête (u, v) existe avec une matrice d'adjacence ?

1. AO(log V)
2. BO(V)
3. CO(1)
4. DO(E)

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

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

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

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

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

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

Quelle structure de données permet un cache LRU (least recently used) avec get et put en O(1) ?

1. AUne table de hachage combinée à une liste doublement chaînée
2. BUn unique tableau trié
3. CUniquement une pile
4. DUniquement un arbre binaire de recherche