Cuestionario: Algorithmique et structures de données — 33 preguntas

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

A. Un processus infini pouvant produire des sorties imprécises à chaque étape

B. Une transformation continue où les entrées deviennent des sorties sans notion de fin

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

D. Un ensemble de règles logiques sans ordre d’exécution imposé

Answer: (C)

Explicación

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 ?

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

B. Une propriété qui n’est vérifiée qu’à la toute dernière itération

C. Une condition qui dépend uniquement de l’état final souhaité

D. Une affirmation vraie uniquement après l’exécution de la boucle

Answer: (A)

Explicación

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 ?

A. Uniquement les préconditions et les postconditions

B. La correction partielle et la terminaison

C. La correction partielle sans tenir compte de la terminaison

D. La terminaison uniquement, sans préconditions ni postconditions

Answer: (B)

Explicación

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 ?

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

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

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

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

Answer: (C)

Explicación

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

A. O(g) et Ω(g) donnent exactement la même croissance, tandis que Θ(g) est seulement une estimation

B. O(g) est un temps exact, Ω(g) est un temps moyen, et Θ(g) est un pire cas garanti

C. O(g) est une borne inférieure, Ω(g) une borne supérieure, et Θ(g) un pire cas sans constante

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

Answer: (D)

Explicación

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 ?

A. Elle signifie que chaque opération individuelle coûte O(1) même dans tous les redimensionnements

B. Elle indique une croissance exacte à constante près pour chaque exécution d’une opération

C. Elle garantit que le pire cas de chaque opération est identique au coût moyen

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

Answer: (D)

Explicación

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 ?

A. Il n’est pas contigu et l’accès à A[i] dépend de i en O(n)

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

C. Il est indexé de 1 à n et nécessite O(log n) pour accéder à A[i]

D. Il permet l’accès à A[n] et reste défini pour tout i compris entre 0 et n

Answer: (B)

Explicación

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 ?

A. Elle coûte O(log n) car on recherche la position

B. Elle coûte O(1) lors du décalage, car aucune copie n’est requise

C. Elle coûte O(1) amorti car la structure reste toujours contiguë

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

Answer: (D)

Explicación

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 ?

A. Additionner directement A[l] à A[r] en O(n) sans prétraitement

B. Utiliser P[r]−P[l−1] en O(log n) après prétraitement O(log n)

C. Calculer P[r+1]−P[l+1] en O(1) sans prétraitement

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

Answer: (D)

Explicación

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

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

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

C. Les retraits se font toujours au milieu de la structure

D. Les opérations se font indifféremment sur les deux extrémités avec retrait au plus proche de l’entrée

Answer: (A)

Explicación

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 ?

A. Un cas de hachage unique

B. Une recherche binaire imposée

C. Une absence de clé

D. Une collision

Answer: (D)

Explicación

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 ?

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

B. Deux clés égales impliquent toujours des hashes différents

C. Si deux clés ont le même hash alors elles sont certainement égales

D. Si deux clés diffèrent alors elles ne peuvent jamais avoir le même hash

Answer: (A)

Explicación

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

A. Quand on utilise un tri stable avant chaque recherche

B. Quand les données ne sont pas triées et qu’on parcourt linéairement

C. Quand la table de hachage présente un facteur de charge constant

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

Answer: (D)

Explicación

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 ?

A. α = n/m

B. α = m − n

C. α = n + m

D. α = m/n

Answer: (A)

Explicación

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 ?

A. Pour garantir une stabilité de tri des résultats

B. Parce que la récursion terminale est systématiquement optimisée

C. Pour éviter une récursion infinie

D. Parce qu’il faut mémoriser automatiquement tous les sous-problèmes

Answer: (C)

Explicación

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 ?

A. Une technique qui remplace la récursion par une simple boucle sans états

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

C. Une méthode bottom-up qui n’a pas besoin de cas de base

D. Une stratégie qui interdit tout sous-problème chevauchant

Answer: (B)

Explicación

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 ?

A. Définir un ordre de calcul et éventuellement une reconstruction

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

C. Exploiter des sous-problèmes chevauchants et une sous-structure optimale

D. Définir des états, des transitions et des cas de base

Answer: (B)

Explicación

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 ?

A. Graphe quelconque sans cycle, mais pas nécessairement connexe

B. Graphe non connexe avec n−1 arêtes pour n nœuds

C. Graphe connexe avec cycle, avec n arêtes pour n nœuds

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

Answer: (D)

Explicación

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 ?

A. Le plus long chemin d’un nœud vers une feuille

B. Le nombre de feuilles dans le sous-arbre

C. La distance entre deux nœuds quelconques

D. La distance entre la racine et le nœud

Answer: (D)

Explicación

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 ?

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

B. Les clés des deux sous-arbres doivent être non comparables

C. Toutes les clés du sous-arbre droit sont égales à celle du nœud

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

Answer: (A)

Explicación

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 ?

A. O(h²) car la hauteur intervient deux fois

B. O(n log n) pour toute forme d’arbre

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

D. O(1) quel que soit l’équilibrage

Answer: (C)

Explicación

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 ?

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

B. Le graphe contient uniquement des sommets, les arêtes étant implicites

C. Le graphe impose toujours une orientation et un poids sur chaque arête

D. Le graphe ne peut être que pondéré, les arêtes non pondérées étant interdites

Answer: (A)

Explicación

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 ?

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

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

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

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

Answer: (C)

Explicación

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 ?

A. Dans un graphe pondéré avec des poids positifs mais non uniformes

B. Dans un graphe non pondéré

C. Dans un graphe orienté cyclique contenant des poids arbitraires

D. Dans un graphe pondéré avec poids négatifs

Answer: (B)

Explicación

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 ?

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

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

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

D. Temps O(V²) et mémoire O(E)

Answer: (A)

Explicación

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 ?

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

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

C. Ajouter w à toutes les distances sans comparaison

D. Mettre à jour uniquement le prédécesseur de v sans modifier d[v]

Answer: (A)

Explicación

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 ?

A. BFS détecte automatiquement les cycles négatifs atteignables

B. Un tri topologique détecte les cycles négatifs atteignables

C. Dijkstra autorise les poids négatifs et détecte les cycles négatifs atteignables

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

Answer: (D)

Explicación

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 ?

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

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

C. O(VE), O((V+E)log V) et O(V²), avec O(V³) mémoire

D. O((V+E)log V), O(V+E) et O(V³), avec O(V) mémoire

Answer: (B)

Explicación

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

A. Il maximise le poids total tout en empêchant la création de cycles

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

C. Il relie tous les sommets d’un graphe non orienté connexe avec V arêtes et des distances minimales depuis une source

D. Il conserve les plus courtes distances depuis un sommet de départ quelle que soit la pondération

Answer: (B)

Explicación

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 ?

A. Le glouton se limite à des sous-problèmes réutilisés comme en dynamique

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

C. La programmation dynamique ne s’appuie jamais sur la réutilisation de sous-solutions

D. Le diviser-régner fait toujours un choix local irréversible sans preuve

Answer: (B)

Explicación

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 ?

A. Il calcule directement l’optimum sans explorer récursivement

B. Il classe d’abord toutes les solutions possibles avant d’en choisir une

C. Il ne revient jamais sur un choix une fois fait

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

Answer: (D)

Explicación

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 ?

A. O(m log n)

B. O(n log n)

C. O(n+m)

D. O(nm)

Answer: (C)

Explicación

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 ?

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

B. Un tas de taille k trouve le kᵉ élément en O(n log k) et Quickselect trouve le top-k en O(n²)

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

D. Quickselect garantit toujours O(n log k) et un tas garantit toujours O(n²)

Answer: (A)

Explicación

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.