QCM : Introduction aux structures de données et algorithmes — 24 questions

Explication

Une structure de données organise et stocke des informations en précisant les valeurs possibles et les opérations associées. Les autres propositions décrivent d’autres notions du cours.

Explication

Un dictionnaire associe des clés à des valeurs et permet notamment la recherche, l’insertion, la modification et la suppression via une clé. Le parcours en largeur et la récursivité appartiennent à d’autres thèmes.

Explication

Un assert vérifie une expression booléenne et produit une erreur si la condition n’est pas satisfaite. Il ne sert pas à gérer les exceptions ni à exécuter des doctests.

Explication

En TDD, on commence par écrire un test qui échoue, puis on implémente le minimum pour le faire réussir. Cela distingue cette méthode d’une écriture du code avant les tests.

Explication

Une pile suit le principe LIFO : le dernier entré est le premier sorti. La propriété FIFO correspond à une file, pas à une pile.

Explication

Une pile se manipule en ajoutant au sommet et en retirant au sommet. Insérer en queue et retirer en tête décrit une file FIFO.

Explication

La programmation orientée objet structure le code autour d’objets qui combinent des données et des méthodes. Les autres propositions ne correspondent pas à ce paradigme.

Explication

L’encapsulation vise à protéger l’état interne et à exposer une interface claire pour interagir avec l’objet. La récursivité et le tri concernent d’autres mécanismes du cours.

Explication

Un arbre libre est un graphe non orienté, connexe et sans cycle. Cette définition le distingue des structures linéaires et des dictionnaires.

Explication

Dans un arbre enraciné, l’orientation implicite va de la racine vers les descendants, donc du père vers le fils. Cela correspond à la représentation adoptée dans le cours.

Explication

Dans un arbre libre, il existe un chemin unique entre deux sommets quelconques. C’est une propriété équivalente au fait d’être connexe et sans cycle.

Explication

Dans un arbre libre, on a bien |E| = |V| - 1. Cette relation découle de la structure connexe sans cycle de l’arbre.

Explication

Le cas de base est la condition d’arrêt de la récursion. Sans lui, les appels pourraient s’enchaîner sans fin.

Explication

Pendant un DFS, rencontrer un sommet déjà visité, en particulier gris, signale une arête de retour et donc un cycle. Le marquage sert précisément à éviter de re-parcourir les mêmes sommets.

Explication

Diviser pour régner consiste à découper le problème, résoudre récursivement les sous-problèmes, puis combiner leurs résultats. La résolution récursive des sous-parties est donc l’étape centrale.

Explication

Le tri fusion découpe le tableau en deux jusqu’à des sous-problèmes de taille unitaire, ce qui crée environ log2 n niveaux, puis fusionne linéairement à chaque niveau. Cela conduit à O(n log2 n).

Explication

Une file FIFO respecte l’ordre d’arrivée : on retire d’abord l’élément en tête, celui qui est arrivé le plus tôt. L’insertion se fait en fin de file.

Explication

Le BFS explore les sommets par distance croissante à partir du sommet de départ, donc niveau par niveau. Il s’appuie sur une file pour traiter d’abord les sommets découverts le plus tôt.

Explication

Pour Fibonacci, différents appels demandent les mêmes sous-problèmes, ce qui crée des branches redondantes dans l’arbre de récursion. C’est précisément ce recoupement qui motive la mémorisation.

Explication

La mémorisation stocke les résultats déjà calculés pour les réutiliser ensuite. Elle évite ainsi les recomputations coûteuses lorsque les sous-problèmes se recoupent.

Explication

Le parcours en largeur utilise une file FIFO : on retire les éléments par la tête et on ajoute les nouveaux en queue. Une pile LIFO correspondrait au parcours en profondeur, pas au BFS.

Explication

Le BFS explore par distance croissante, donc niveau par niveau à partir du sommet de départ. Les couleurs servent justement à éviter de revisiter les sommets déjà découverts.

Explication

N_b(X) désigne le nombre minimum de pièces pour obtenir la somme X, et vaut infini si la somme est impossible à rendre. Ce n’est pas un simple comptage de solutions, mais bien une optimisation.

Explication

La récurrence donnée fixe bien N_b(0)=0, renvoie infini pour les sommes négatives, puis ajoute 1 à la meilleure solution parmi les sous-problèmes restants. Le minimum est essentiel, car on cherche le plus petit nombre de pièces.