QCM : Algorithmique et structures de données — 33 questions

Questions et réponses du QCM

1. Quel énoncé décrit correctement un algorithme ?

Un processus infini pouvant produire des sorties imprécises à chaque étape
Une transformation continue où les entrées deviennent des sorties sans notion de fin
Une suite finie, ordonnée et non ambiguë d’instructions qui transforme des entrées en sorties
Un ensemble de règles logiques sans ordre d’exécution imposé

Une suite finie, ordonnée et non ambiguë d’instructions qui transforme des entrées en sorties

Explication

Un algorithme est défini comme une suite finie, ordonnée et non ambiguë d’instructions qui transforme des entrées en sorties. Les autres propositions manquent de finitude, d’ordre ou de caractère non ambigu.

2. Lors de la conception d’une preuve par invariants, que doit être un invariant de boucle ?

Une propriété qui reste vraie à chaque itération de la boucle
Une propriété qui n’est vérifiée qu’à la toute dernière itération
Une condition qui dépend uniquement de l’état final souhaité
Une affirmation vraie uniquement après l’exécution de la boucle

Une propriété qui reste vraie à chaque itération de la boucle

Explication

Un invariant est une propriété qui reste vraie à chaque itération d’une boucle. Vérifier seulement la fin correspond à une autre notion et ne suffit pas pour l’invariant.

3. Que combine la correction totale d’un algorithme ?

Uniquement les préconditions et les postconditions
La correction partielle et la terminaison
La correction partielle sans tenir compte de la terminaison
La terminaison uniquement, sans préconditions ni postconditions

La correction partielle et la terminaison

Explication

La correction totale combine la correction partielle (via préconditions, postconditions et invariants) avec la terminaison. Les autres réponses oublient soit la correction partielle, soit la terminaison.

4. Quel est l’ordre croissant usuel des classes de complexité mentionnées ?

O(log n), O(1), O(n log n), O(n), O(n²), O(n³), O(2ⁿ), O(n!)
O(1), O(n), O(log n), O(n log n), O(n²), O(2ⁿ), O(n³), O(n!)
O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!)
O(n!), O(2ⁿ), O(n³), O(n²), O(n log n), O(n), O(log n), O(1)

O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!)

Explication

La progression croissante usuelle donnée va de O(1) à O(log n), puis O(n), O(n log n), O(n²), O(n³), O(2ⁿ) puis O(n!). Les autres ordres inversent ou mélangent des catégories.

5. Quelle interprétation correcte relie O(g), Ω(g) et Θ(g) ?

O(g) et Ω(g) donnent exactement la même croissance, tandis que Θ(g) est seulement une estimation
O(g) est un temps exact, Ω(g) est un temps moyen, et Θ(g) est un pire cas garanti
O(g) est une borne inférieure, Ω(g) une borne supérieure, et Θ(g) un pire cas sans constante
O(g) est une borne supérieure, Ω(g) une borne inférieure, et Θ(g) une croissance précise à constante près

O(g) est une borne supérieure, Ω(g) une borne inférieure, et Θ(g) une croissance précise à constante près

Explication

Le cours indique qu'O(g) fournit une borne supérieure, Ω(g) une borne inférieure et Θ(g) une croissance précise à constante près. Les distracteurs inversent ces rôles ou attribuent une notion trop exacte.

6. Dans quel contexte l’idée de complexité amortie est-elle correcte ?

Elle signifie que chaque opération individuelle coûte O(1) même dans tous les redimensionnements
Elle indique une croissance exacte à constante près pour chaque exécution d’une opération
Elle garantit que le pire cas de chaque opération est identique au coût moyen
Elle garantit un coût moyen sur une séquence d’opérations, par exemple append en O(1) amorti pour un tableau dynamique

Elle garantit un coût moyen sur une séquence d’opérations, par exemple append en O(1) amorti pour un tableau dynamique

Explication

La complexité amortie correspond à un coût moyen sur une suite d’opérations (comme append en O(1) amorti pour un tableau dynamique). Les autres réponses confondent amorti avec un coût individuel constant ou un pire cas strict.

7. Quelles caractéristiques décrivent correctement un tableau dans ce modèle ?

Il n’est pas contigu et l’accès à A[i] dépend de i en O(n)
Il est contigu, indexé de 0 à n−1 et permet l’accès A[i] en O(1)
Il est indexé de 1 à n et nécessite O(log n) pour accéder à A[i]
Il permet l’accès à A[n] et reste défini pour tout i compris entre 0 et n

Il est contigu, indexé de 0 à n−1 et permet l’accès A[i] en O(1)

Explication

Un tableau est décrit comme contigu, indexé de 0 à n−1, avec un accès A[i] en O(1). L’indice A[n] est hors limites pour une taille n, et les autres options contredisent la propriété de contiguïté/accès.

8. Quel énoncé reflète correctement le coût d’une insertion au milieu dans un tableau dynamique ?

Elle coûte O(log n) car on recherche la position
Elle coûte O(1) lors du décalage, car aucune copie n’est requise
Elle coûte O(1) amorti car la structure reste toujours contiguë
Elle coûte O(n) à cause des décalages nécessaires

Elle coûte O(n) à cause des décalages nécessaires

Explication

Dans un tableau dynamique, une insertion ou suppression au milieu coûte O(n) du fait des décalages. Le cas O(1) amorti correspond plutôt à l’ajout en fin, pas au milieu.

9. Comment calculer efficacement la somme A[l..r] dans un tableau avec préfixes cumulés P ?

Additionner directement A[l] à A[r] en O(n) sans prétraitement
Utiliser P[r]−P[l−1] en O(log n) après prétraitement O(log n)
Calculer P[r+1]−P[l+1] en O(1) sans prétraitement
Calculer P[r+1]−P[l], après un prétraitement O(n) donnant un calcul en O(1)

Calculer P[r+1]−P[l], après un prétraitement O(n) donnant un calcul en O(1)

Explication

Avec P[0]=0 et P[i+1]=P[i]+A[i], on a somme A[l..r] = P[r+1]−P[l] et le calcul devient O(1) après un prétraitement O(n). Les autres formules utilisent des indices faux ou ne donnent pas O(1).

10. Quel comportement correspond à une pile (stack) ?

Le dernier élément arrivé est le premier à être retiré
Le premier élément arrivé est le premier à être retiré
Les retraits se font toujours au milieu de la structure
Les opérations se font indifféremment sur les deux extrémités avec retrait au plus proche de l’entrée

Le dernier élément arrivé est le premier à être retiré

Explication

Une pile suit la discipline LIFO : le dernier élément arrivé est le premier retiré. Les files sont FIFO et les autres propositions ne décrivent pas correctement le modèle de pile.

11. Quel phénomène se produit lorsque plusieurs clés aboutissent au même indice de hachage dans une table de hachage ?

Un cas de hachage unique
Une recherche binaire imposée
Une absence de clé
Une collision

Une collision

Explication

Une collision survient lorsque plusieurs clés produisent le même indice de hachage ; elle se gère notamment par chaînage ou adressage ouvert. Les autres propositions ne correspondent pas à la définition d’une collision.

12. Deux clés peuvent produire le même hash sans que cela implique qu’elles soient identiques : laquelle des affirmations suivantes exprime correctement cette idée ?

Deux hashes égaux n’impliquent pas que les clés soient égales
Deux clés égales impliquent toujours des hashes différents
Si deux clés ont le même hash alors elles sont certainement égales
Si deux clés diffèrent alors elles ne peuvent jamais avoir le même hash

Deux hashes égaux n’impliquent pas que les clés soient égales

Explication

La propriété importante est que des hashes égaux ne garantissent pas l’égalité des clés. L’inverse est faux, puisque l’égalité des hashes peut provenir du même indice de hachage.

13. Dans quelle situation la recherche binaire permet-elle de garantir une complexité en O(log n) ?

Quand on utilise un tri stable avant chaque recherche
Quand les données ne sont pas triées et qu’on parcourt linéairement
Quand la table de hachage présente un facteur de charge constant
Quand le tableau est trié et qu’un accès direct permet de consulter le milieu

Quand le tableau est trié et qu’un accès direct permet de consulter le milieu

Explication

La recherche binaire exige un tableau trié et un accès direct au milieu pour fonctionner en O(log n). La recherche linéaire reste en O(n) dans le pire cas même si le tableau n’est pas trié.

14. Quel est le facteur de charge d’une table de hachage si elle contient n clés et que sa capacité est m ?

α = n/m
α = m − n
α = n + m
α = m/n

α = n/m

Explication

Le facteur de charge est défini par α = n/m, où n est le nombre de clés et m la capacité. Les autres formules inversent ou changent la relation.

15. Pourquoi une fonction récursive doit-elle comporter un cas de base et une progression vers celui-ci ?

Pour garantir une stabilité de tri des résultats
Parce que la récursion terminale est systématiquement optimisée
Pour éviter une récursion infinie
Parce qu’il faut mémoriser automatiquement tous les sous-problèmes

Pour éviter une récursion infinie

Explication

Sans progression vers le cas de base, la récursion peut être infinie. Les autres choix ne sont pas des exigences générales de la définition de la récursion.

16. La mémoïsation correspond à quelle approche de résolution ?

Une technique qui remplace la récursion par une simple boucle sans états
Une approche top-down qui mémorise les résultats des sous-problèmes déjà calculés
Une méthode bottom-up qui n’a pas besoin de cas de base
Une stratégie qui interdit tout sous-problème chevauchant

Une approche top-down qui mémorise les résultats des sous-problèmes déjà calculés

Explication

La mémoïsation est une approche top-down qui mémorise les résultats déjà obtenus pour éviter de recalculer. Les autres options contredisent la notion de mémorisation des sous-problèmes calculés.

17. Quel élément n’est pas indispensable pour concevoir une programmation dynamique selon l’idée générale donnée ?

Définir un ordre de calcul et éventuellement une reconstruction
Refuser de définir des cas de base afin de forcer la terminaison
Exploiter des sous-problèmes chevauchants et une sous-structure optimale
Définir des états, des transitions et des cas de base

Refuser de définir des cas de base afin de forcer la terminaison

Explication

En programmation dynamique, on définit des cas de base (avec états et transitions) ; les éliminer contredit la démarche. Les autres choix correspondent bien aux composantes attendues.

18. Quelles propriétés caractérisent un arbre au sens des graphes ?

Graphe quelconque sans cycle, mais pas nécessairement connexe
Graphe non connexe avec n−1 arêtes pour n nœuds
Graphe connexe avec cycle, avec n arêtes pour n nœuds
Graphe connexe sans cycle avec n−1 arêtes pour n nœuds

Graphe connexe sans cycle avec n−1 arêtes pour n nœuds

Explication

Un arbre est un graphe connexe sans cycle et possède n−1 arêtes pour n nœuds. Les distracteurs proposent des manques de connexité ou la présence de cycles.

19. Dans un arbre, que mesure la profondeur d’un nœud ?

Le plus long chemin d’un nœud vers une feuille
Le nombre de feuilles dans le sous-arbre
La distance entre deux nœuds quelconques
La distance entre la racine et le nœud

La distance entre la racine et le nœud

Explication

La profondeur est la distance entre la racine et le nœud. La hauteur, elle, correspond au plus long chemin d’un nœud vers une feuille, ce qui n’est pas la profondeur.

20. Dans un arbre binaire de recherche (ABR), quelles relations doivent respecter les clés autour du nœud, selon la convention choisie ?

Les clés du sous-arbre gauche sont inférieures à la clé du nœud
Les clés des deux sous-arbres doivent être non comparables
Toutes les clés du sous-arbre droit sont égales à celle du nœud
Les clés du sous-arbre gauche sont supérieures à la clé du nœud

Les clés du sous-arbre gauche sont inférieures à la clé du nœud

Explication

Dans un ABR, les clés du sous-arbre gauche sont inférieures à la clé du nœud et celles du sous-arbre droit lui sont supérieures selon la convention. Les autres choix inversent la relation ou imposent une contrainte absurde (égalité totale).

21. Pour un ABR, quelle complexité de coût s’applique aux opérations de recherche, insertion et suppression, en fonction de la hauteur h ?

O(h²) car la hauteur intervient deux fois
O(n log n) pour toute forme d’arbre
O(h), soit O(log n) si l’arbre est équilibré et O(n) s’il est dégénéré
O(1) quel que soit l’équilibrage

O(h), soit O(log n) si l’arbre est équilibré et O(n) s’il est dégénéré

Explication

Le coût de recherche, insertion et suppression est O(h) ; il devient O(log n) si l’arbre est équilibré et O(n) s’il est dégénéré. Les autres options ne correspondent pas à cette dépendance à la hauteur.

22. Un graphe G=(V,E) peut être orienté ou non orienté, et éventuellement pondéré : que décrit précisément cette représentation ?

Le graphe contient des sommets et des arêtes ou arcs, et peut être orienté ou non orienté, pondéré ou non pondéré
Le graphe contient uniquement des sommets, les arêtes étant implicites
Le graphe impose toujours une orientation et un poids sur chaque arête
Le graphe ne peut être que pondéré, les arêtes non pondérées étant interdites

Le graphe contient des sommets et des arêtes ou arcs, et peut être orienté ou non orienté, pondéré ou non pondéré

Explication

La définition précise que G contient des sommets et des arêtes (ou arcs) et qu’il peut être orienté/non orienté et pondéré/non pondéré. Les autres choix imposent des contraintes (orientation ou pondération) qui ne sont pas nécessaires.

23. Pour choisir une représentation de graphe, quel couple mémoire/coût de test d’arête correspond à la matrice d’adjacence ?

Mémoire O(V+E) et test d’une arête en O(1)
Mémoire O(V²) et test d’une arête en O(V)
Mémoire O(V²) et test d’une arête en O(1)
Mémoire O(V+E) et test d’une arête en O(V)

Mémoire O(V²) et test d’une arête en O(1)

Explication

Une matrice d’adjacence utilise O(V²) de mémoire et permet de tester une arête en O(1). La liste d’adjacence est plutôt associée à O(V+E) et mieux adaptée aux graphes clairsemés.

24. Dans quel cas la propriété « BFS garantit les plus courts chemins » est-elle correcte ?

Dans un graphe pondéré avec des poids positifs mais non uniformes
Dans un graphe non pondéré
Dans un graphe orienté cyclique contenant des poids arbitraires
Dans un graphe pondéré avec poids négatifs

Dans un graphe non pondéré

Explication

L’énoncé associe la garantie des plus courts chemins à BFS uniquement pour un graphe non pondéré (propriété évoquée comme confusion). Les autres cas ne satisfont pas le cadre requis (pondérations variées ou négatives).

25. Avec une liste d’adjacence, quelle estimation correspond aux coûts en temps et en mémoire de BFS et DFS ?

Temps O(V+E) et mémoire O(V)
Temps O(E log V) et mémoire O(E+V)
Temps O(V) et mémoire O(V+E)
Temps O(V²) et mémoire O(E)

Temps O(V+E) et mémoire O(V)

Explication

Avec une liste d’adjacence, BFS et DFS coûtent O(V+E) en temps et O(V) en mémoire. Les autres estimations ne correspondent pas aux coûts indiqués pour ces deux parcours.

26. Que se passe-t-il lors du relâchement d’une arête (u,v,w) dans un algorithme de plus courts chemins ?

Mettre à jour d[v] et le prédécesseur si d[u]+w<d[v]
Mettre à jour d[u] et le prédécesseur si d[v]+w<d[u]
Ajouter w à toutes les distances sans comparaison
Mettre à jour uniquement le prédécesseur de v sans modifier d[v]

Mettre à jour d[v] et le prédécesseur si d[u]+w<d[v]

Explication

Le relâchement met à jour la distance d[v] et le prédécesseur si l’on trouve un chemin plus court via u : d[u]+w<d[v]. Les autres réponses inversent la condition ou n’effectuent pas la mise à jour de distance.

27. Quel énoncé relie correctement le type de poids admis et la capacité de détection de cycles négatifs ?

BFS détecte automatiquement les cycles négatifs atteignables
Un tri topologique détecte les cycles négatifs atteignables
Dijkstra autorise les poids négatifs et détecte les cycles négatifs atteignables
Bellman-Ford autorise les poids négatifs et détecte les cycles négatifs atteignables

Bellman-Ford autorise les poids négatifs et détecte les cycles négatifs atteignables

Explication

Bellman-Ford gère les poids négatifs et peut détecter les cycles négatifs atteignables. L’idée « Dijkstra échoue avec des poids négatifs » correspond précisément à la confusion à éviter.

28. Parmi les algorithmes suivants, quelles complexités correspondent respectivement à Dijkstra (avec tas), Bellman-Ford et Floyd-Warshall ?

O(V³), O(VE) et O((V+E)log V), avec O(V²) mémoire uniquement pour Bellman-Ford
O((V+E)log V), O(VE) et O(V³), avec O(V²) mémoire pour Floyd-Warshall
O(VE), O((V+E)log V) et O(V²), avec O(V³) mémoire
O((V+E)log V), O(V+E) et O(V³), avec O(V) mémoire

O((V+E)log V), O(VE) et O(V³), avec O(V²) mémoire pour Floyd-Warshall

Explication

Les complexités indiquées sont O((V+E)log V) pour Dijkstra, O(VE) pour Bellman-Ford et O(V³) pour Floyd-Warshall, avec O(V²) mémoire pour Floyd-Warshall. Les autres propositions permutent ou modifient des ordres de grandeur.

29. Quel critère décrit correctement un arbre couvrant minimal (MST) ?

Il maximise le poids total tout en empêchant la création de cycles
Il relie tous les sommets d’un graphe non orienté connexe avec V−1 arêtes et un poids total minimal
Il relie tous les sommets d’un graphe non orienté connexe avec V arêtes et des distances minimales depuis une source
Il conserve les plus courtes distances depuis un sommet de départ quelle que soit la pondération

Il relie tous les sommets d’un graphe non orienté connexe avec V−1 arêtes et un poids total minimal

Explication

Un MST relie tous les sommets d’un graphe non orienté connexe avec V−1 arêtes et minimise le poids total. La confusion typique consiste à croire qu’il minimise des distances depuis une source.

30. Quel énoncé caractérise correctement le glouton par rapport au diviser-régner et à la programmation dynamique ?

Le glouton se limite à des sous-problèmes réutilisés comme en dynamique
Le glouton choisit localement de manière irréversible, et sa correction nécessite une preuve dédiée
La programmation dynamique ne s’appuie jamais sur la réutilisation de sous-solutions
Le diviser-régner fait toujours un choix local irréversible sans preuve

Le glouton choisit localement de manière irréversible, et sa correction nécessite une preuve dédiée

Explication

Le glouton choisit localement de façon irréversible, et il faut fournir une preuve de correction (contrairement à une intuition seule). Les autres choix attribuent au glouton ou aux autres paradigmes des caractéristiques qui ne sont pas celles décrites.

31. Comment le backtracking explore-t-il l’espace de recherche ?

Il calcule directement l’optimum sans explorer récursivement
Il classe d’abord toutes les solutions possibles avant d’en choisir une
Il ne revient jamais sur un choix une fois fait
Il construit un choix, explore récursivement, puis annule lorsqu’une impasse est atteinte

Il construit un choix, explore récursivement, puis annule lorsqu’une impasse est atteinte

Explication

Le backtracking construit un choix, avance récursivement, puis revient en arrière quand une impasse est détectée. Le branch and bound est un autre cadre : l’énoncé mis en confusion attire l’attention sur cette différence.

32. Quel ordre de grandeur correspond à la complexité de KMP pour traiter un texte de longueur n et un motif de longueur m ?

O(m log n)
O(n log n)
O(n+m)
O(nm)

O(n+m)

Explication

KMP a une complexité O(n+m). Les autres choix correspondent à des ordres de grandeur associés à des problèmes ou algorithmes différents (par exemple LCS/L’édit O(nm)).

33. Quelle affirmation relie correctement un problème « top-k » à une méthode de sélection par tas ou par sélection directe ?

Un tas de taille k trouve un top-k en O(n log k), tandis que Quickselect trouve le kᵉ élément en O(n) moyen
Un tas de taille k trouve le kᵉ élément en O(n log k) et Quickselect trouve le top-k en O(n²)
Quickselect trouve un top-k en O(n log k), tandis qu’un tas de taille k trouve le kᵉ élément en O(n) moyen
Quickselect garantit toujours O(n log k) et un tas garantit toujours O(n²)

Un tas de taille k trouve un top-k en O(n log k), tandis que Quickselect trouve le kᵉ élément en O(n) moyen

Explication

La correspondance indiquée est : tas de taille k pour top-k en O(n log k), et Quickselect pour le kᵉ élément en O(n) moyen (avec O(n²) possible au pire). Les autres choix inversent les rôles ou citent de mauvais ordres de grandeur.

Révisez avec les flashcards

Mémorisez les réponses avec 69 flashcards sur Algorithmique et structures de données.

Qu'est-ce qu'un algorithme ?

Une suite finie, ordonnée et non ambiguë d’instructions transformant des entrées en sorties.

Qu'est-ce qui différencie une affectation d'une égalité mathématique ?

L'affectation modifie la valeur d'une variable, contrairement à une égalité mathématique.

Qu'est-ce qu'un invariant dans une boucle ?

Une propriété qui reste vraie à chaque itération de la boucle.

Voir les flashcards →

Approfondir avec la fiche

Consultez la fiche de révision complète sur Algorithmique et structures de données.

Voir la fiche →

Cours similaires

Gestion des fichiers en PHP

Programmation

Identification utilisateur en PHP

Programmation

Automated PCB Fault Diagnosis

Intelligence Artificielle

Rôle d'un système d'exploitation

Questions techniques projet Compawgnon

Bases de Python pour débutants

Programmation

Crée tes propres QCM

Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.

Générateur de QCM