Quiz: Introduction aux structures de données et algorithmes — 24 Fragen

1. Quelle description correspond le mieux à une structure de données ?

A. Un programme qui exécute automatiquement des tests d’exemples

B. Une façon d’organiser et de stocker des informations avec des opérations de manipulation

C. Une suite d’instructions qui gère une erreur d’exécution

D. Une méthode de parcours des graphes par niveaux

Answer: (B)

Erklärung

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.

2. Dans un dictionnaire tableau associatif, quelle opération fait partie de l’interface de base ?

A. Accéder à une valeur à partir d’une clé

B. Appeler récursivement une fonction sur un sous-problème

C. Supprimer systématiquement les doublons d’un résultat

D. Parcourir les sommets niveau par niveau

Answer: (A)

Erklärung

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.

3. Quel est le rôle principal de l’instruction assert ?

A. Trier les résultats d’une requête SQL

B. Attraper une exception pour continuer l’exécution

C. Exécuter automatiquement des exemples d’une docstring

D. Vérifier une condition et déclencher une erreur si elle est fausse

Answer: (D)

Erklärung

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.

4. Dans le développement piloté par les tests, quelle étape vient en premier ?

A. Optimiser le programme avant de définir les spécifications

B. Écrire tout le code puis ajouter les tests ensuite

C. Écrire un test censé échouer avant d’implémenter le code

D. Corriger les erreurs après exécution sans écrire de test

Answer: (C)

Erklärung

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.

5. Quelle propriété caractérise une pile ?

A. Le dernier élément ajouté est le premier retiré

B. Les éléments sont toujours triés par valeur

C. Le premier élément ajouté est le premier retiré

D. Les éléments sont accessibles directement par clé

Answer: (A)

Erklärung

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

6. Quel couple d’opérations correspond à l’usage classique d’une pile ?

A. Filtrer puis trier

B. Empiler puis dépiler

C. Insérer en queue puis retirer en tête

D. Rechercher puis modifier

Answer: (B)

Erklärung

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.

7. Quelle affirmation décrit le mieux la programmation orientée objet ?

A. Elle consiste uniquement à écrire des requêtes de base de données

B. Elle organise un programme autour d’objets qui regroupent données et comportements

C. Elle interdit toute forme d’abstraction

D. Elle impose de n’utiliser que des tableaux indicés de taille fixe

Answer: (B)

Erklärung

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.

8. Quel concept permet de masquer les détails internes d’un objet et de ne montrer qu’une interface d’utilisation ?

A. Le tri croissant

B. La composition de requêtes

C. La récursivité

D. L’encapsulation

Answer: (D)

Erklärung

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.

9. Quelle caractéristique définit un arbre libre ?

A. Un graphe orienté avec un sommet racine

B. Un graphe non orienté connexe sans cycle

C. Une collection de couples clé:valeur

D. Une structure linéaire dynamique

Answer: (B)

Erklärung

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

10. Dans un arbre enraciné, comment sont orientées implicitement les arêtes ?

A. Elles convergent vers la racine, du fils vers le père

B. Elles s’éloignent de la racine, du père vers le fils

C. Elles n’ont aucune direction

D. Elles sont toujours orientées dans les deux sens

Answer: (B)

Erklärung

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.

11. Dans un arbre libre, quelle propriété caractérise un couple de sommets quelconques ?

A. Ils ne peuvent pas toujours être reliés

B. Ils sont reliés par au moins deux chemins

C. Ils sont reliés par exactement un chemin

D. Ils sont reliés uniquement s’ils sont voisins

Answer: (C)

Erklärung

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.

12. Que représente la relation |E| = |V| - 1 dans un arbre libre ?

A. Le nombre d’arêtes dépend uniquement de la racine

B. Le nombre d’arêtes vaut le double du nombre de sommets

C. Le nombre d’arêtes est toujours inférieur d’une unité au nombre de sommets

D. Le nombre d’arêtes est égal au nombre de sommets

Answer: (C)

Erklärung

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

13. Qu’est-ce qu’un cas de base dans une définition récursive ?

A. Le premier appel effectué par la fonction

B. La valeur finale renvoyée par toute fonction récursive

C. La condition d’arrêt qui empêche la récursion de continuer indéfiniment

D. La partie du calcul qui se répète sur chaque sous-problème

Answer: (C)

Erklärung

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

14. Pourquoi la détection d’un cycle par parcours en profondeur repose-t-elle sur un sommet déjà visité ?

A. Parce qu’un sommet gris indique qu’il est rencontré à nouveau pendant l’exploration

B. Parce qu’un sommet déjà visité garantit qu’il n’y a pas de cycle

C. Parce qu’un sommet noir correspond toujours à une arête de retour

D. Parce qu’un sommet blanc prouve l’existence d’un cycle

Answer: (A)

Erklärung

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.

15. Dans un algorithme de diviser pour régner, quelle étape correspond à la résolution des sous-problèmes ?

A. Résoudre récursivement les parties plus petites du problème

B. Parcourir tous les cas possibles sans découpage

C. Conserver uniquement le résultat final sans calcul intermédiaire

D. Trier les données sans séparation préalable

Answer: (A)

Erklärung

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.

16. Pourquoi le tri fusion a-t-il une complexité en O(n log2 n) ?

A. Parce qu’il ne fait qu’un seul passage sur le tableau

B. Parce qu’il effectue une fusion linéaire à chaque niveau sur log2 n niveaux

C. Parce qu’il utilise une structure de file FIFO pour trier

D. Parce qu’il compare chaque paire d’éléments exactement une fois

Answer: (B)

Erklärung

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).

17. Dans une file FIFO, quel élément est supprimé en premier lors d’une opération de retrait ?

A. L’élément ajouté en dernier

B. L’élément choisi au hasard

C. L’élément situé au milieu de la file

D. L’élément placé en tête depuis le plus longtemps

Answer: (D)

Erklärung

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.

18. Quel énoncé décrit correctement le parcours en largeur BFS ?

A. Il suit uniquement les arêtes d’un arbre enraciné

B. Il descend d’abord jusqu’au plus profond avant de remonter

C. Il explore un graphe niveau par niveau à partir d’un sommet de départ

D. Il ignore les sommets déjà découverts sans les marquer

Answer: (C)

Erklärung

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.

19. Dans l’arbre de récursion de fib(n), pourquoi certaines valeurs comme fib(4) apparaissent-elles plusieurs fois ?

A. Parce que l’arbre de récursion supprime automatiquement les doublons

B. Parce que les sous-problèmes se recoupent et sont recalculés dans plusieurs branches

C. Parce que chaque appel récursif modifie la définition de la suite

D. Parce que les feuilles de l’arbre ne correspondent pas aux cas de base

Answer: (B)

Erklärung

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.

20. Quel est l’effet principal de la mémorisation dans un calcul récursif avec sous-problèmes qui se recoupent ?

A. Rendre inutile le stockage des résultats intermédiaires

B. Éviter de recalculer plusieurs fois les mêmes valeurs déjà obtenues

C. Transformer automatiquement toute récursion en parcours en largeur

D. Supprimer la nécessité d’un cas de base

Answer: (B)

Erklärung

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.

21. Dans un parcours en largeur, quelle structure permet de traiter d’abord les sommets découverts le plus tôt ?

A. Une pile LIFO

B. Une file FIFO

C. Un arbre binaire

D. Un dictionnaire associatif

Answer: (B)

Erklärung

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.

22. Quelle affirmation décrit correctement le parcours en largeur sur un graphe non orienté ?

A. Il calcule directement le plus court chemin sans mémoriser les couleurs

B. Il explore les sommets niveau par niveau à partir d’un sommet de départ

C. Il suit un seul chemin jusqu’au bout avant de revenir en arrière

D. Il trie les sommets selon leur degré décroissant

Answer: (B)

Erklärung

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.

23. Dans le problème du rendu de monnaie, que représente la valeur N_b(X) ?

A. Le nombre de sous-problèmes déjà résolus pour X

B. Le nombre minimum de pièces nécessaires pour rendre la somme X

C. La plus grande pièce inférieure ou égale à X

D. Le nombre total de solutions possibles pour rendre X

Answer: (B)

Erklärung

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.

24. Quelle récurrence correspond au calcul du nombre minimum de pièces pour rendre une somme X ?

A. N_b(0)=1, N_b(X)=0 si X<0, et pour X>0 : N_b(X)=min N_b(X-p_i)

B. N_b(0)=0, N_b(X)=∞ si X<0, et pour X>0 : N_b(X)=1+min N_b(X-p_i)

C. N_b(0)=0, N_b(X)=∞ si X>0, et pour X<0 : N_b(X)=1+min N_b(X-p_i)

D. N_b(0)=1, N_b(X)=∞ si X<0, et pour X>0 : N_b(X)=1+max N_b(X-p_i)

Answer: (B)

Erklärung

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.