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

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

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

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

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

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

1. AEnqueue (enfiler)
2. BPop (dépiler)
3. CPeek (consulter)
4. DPush (empiler)

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

1. AUne file de priorité min
2. BUne file FIFO
3. CUn ensemble sans ordre
4. DUne pile

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(1)
3. CO(E)
4. DO(V)

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

1. Ai + 1
2. B(i − 1) mod n
3. C2i + 1
4. D(i + 1) mod n

Quelle affirmation sur le tri par tas (heapsort) est correcte ?

1. AIl s'exécute en O(n) sur toute entrée
2. BIl est stable et nécessite O(n) mémoire supplémentaire
3. CIl nécessite un arbre binaire de recherche comme stockage supplémentaire, donc il utilise O(n) de mémoire en plus
4. DIl trie sur place en O(n log n) dans le pire cas, mais n'est pas stable

Quelle structure permet de calculer le maximum de chaque fenêtre de taille k dans un tableau en O(n) au total ?

1. AUn tas min reconstruit pour chaque fenêtre
2. BUn tableau trié mis à jour par décalage
3. CUne liste simplement chaînée des éléments de la fenêtre
4. DUn deque contenant des indices par ordre décroissant de valeur