18 — QCM : 100 questions avec réponses

Ce chapitre contient 100 questions à choix multiples réparties en 8 thèmes. Chaque thème est suivi de son corrigé immédiat (lettre + justification). Pour un entraînement honnête : répondez d'abord sans regarder les réponses, puis comparez.

Sommaire

Thème 1 : Complexité (15 questions)
Corrigé du thème 1
Thème 2 : Tris (10 questions)
Corrigé du thème 2
Thème 3 : Structures de données (15 questions)
Corrigé du thème 3
Thème 4 : Graphes (15 questions)
Corrigé du thème 4
Thème 5 : Programmation dynamique (10 questions)
Corrigé du thème 5
Thème 6 : Greedy (8 questions)
Corrigé du thème 6
Thème 7 : Strings (12 questions)
Corrigé du thème 7
Thème 8 : Mathématiques (15 questions)
Corrigé du thème 8
Grille de notation

Thème 1 : Complexité (15 questions)

Q1. Quelle est la complexité temporelle d'une boucle for i in range(n): for j in range(n): ... ?

A. O(n)
B. O(n log n)
C. O(n²)
D. O(2^n)

Q2. La complexité de la recherche binaire dans un tableau trié de taille n est :

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Q3. La complexité spatiale en plus d'un tri fusion (merge sort) est :

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Q4. Si T(n) = 2·T(n/2) + O(n), alors T(n) vaut :

A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)

Q5. Quelle est la complexité d'une recherche séquentielle dans le pire cas ?

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Q6. La notation Θ (thêta) désigne :

A. une borne supérieure asymptotique
B. une borne inférieure asymptotique
C. une borne supérieure et inférieure (croissance exacte)
D. une complexité constante

Q7. Une fonction récursive qui résout deux sous-problèmes de taille n-1 a une complexité :

A. O(n)
B. O(2^n)
C. O(n²)
D. O(log n)

Q8. Quelle structure permet une insertion et une suppression d'un extrémum en O(log n) ?

A. Tableau trié
B. Liste chaînée
C. Tas binaire
D. Hash map

Q9. Le calcul de fibonacci(n) par programmation dynamique itérative a une complexité :

A. O(2^n)
B. O(n)
C. O(n²)
D. O(log n)

Q10. La complexité de l'exponentiation rapide a^b mod m est :

A. O(b)
B. O(b²)
C. O(log b)
D. O(1)

Q11. Le tri par insertion a une complexité dans le pire cas de :

A. O(n log n)
B. O(n²)
C. O(n)
D. O(log n)

Q12. Que signifie "amorti" dans « push/pop amorti O(1) » d'une pile dynamique ?

A. Cas moyen en moyenne sur une séquence d'opérations
B. Pire cas de chaque opération individuelle
C. Complexité garantie constante pour chaque opération
D. Aucune garantie de complexité

Q13. Si une boucle interne s'exécute log₂(n) fois pour chaque itération externe, la complexité totale est :

A. O(n)
B. O(n log n)
C. O(log n)
D. O(n²)

Q14. La complexité de l'opération « accéder au i-ème élément » d'une liste chaînée est :

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Q15. Un algorithme dont le temps d'exécution est indépendant de la taille de l'entrée a une complexité :

A. O(n)
B. O(log n)
C. O(1)
D. O(n²)

Corrigé du thème 1

Q	Réponse	Justification
Q1	C	Deux boucles imbriquées de taille n → O(n²).
Q2	B	La zone de recherche est divisée par 2 à chaque étape → O(log n).
Q3	C	Le tableau auxiliaire de fusion fait O(n) en plus.
Q4	B	Master theorem cas 2 : `a = b = 2` → T(n) = Θ(n log n).
Q5	C	Pire cas : l'élément est en dernière position → n comparaisons.
Q6	C	Θ(f) = O(f) ∩ Ω(f) : croissance exacte.
Q7	B	Deux appels de taille n-1 → T(n) = 2·T(n-1) + O(1) = O(2^n).
Q8	C	Le tas binaire supporte extract-min/insert en O(log n).
Q9	B	Tableau de taille n rempli linéairement → O(n).
Q10	C	Le nombre de bits de b est log₂(b) → O(log b) multiplications.
Q11	B	Tableau inversé → n²/2 comparaisons.
Q12	A	L'analyse amortie étudie le coût moyen sur une séquence.
Q13	B	n itérations × log n étapes internes → O(n log n).
Q14	C	Il faut traverser les nœuds jusqu'à la position i.
Q15	C	Coût constant, indépendant de n.

Thème 2 : Tris (10 questions)

Q16. Le tri rapide (quicksort) a une complexité dans le pire cas de :

A. O(n log n)
B. O(n²)
C. O(n)
D. O(log n)

Q17. Quel tri est stable parmi les suivants ?

A. Tri rapide
B. Tri par tas
C. Tri fusion
D. Tri par sélection

Q18. La complexité du tri par tas (heapsort) dans le meilleur cas est :

A. O(n²)
B. O(n log n)
C. O(n)
D. O(1)

Q19. Le tri par comptage (counting sort) est efficace quand :

A. Les valeurs sont réparties dans un petit intervalle connu
B. Les valeurs sont des nombres flottants
C. La clé est une chaîne très longue
D. Le tableau est presque trié

Q20. Le partitionnement de Hoare (quicksort) a une complexité de :

A. O(n)
B. O(log n)
C. O(n log n)
D. O(n²)

Q21. Quel tri a la plus faible constante multiplicative sur données aléatoires, en moyenne ?

A. Tri par tas
B. Tri rapide
C. Tri fusion
D. Tri à bulles

Q22. Le tri à bulles optimisé sur un tableau déjà trié s'exécute en :

A. O(n)
B. O(n²)
C. O(n log n)
D. O(1)

Q23. Un algorithme de tri en place :

A. n'utilise qu'une quantité constante de mémoire additionnelle
B. trie sans lire les données
C. est toujours plus rapide qu'un tri non en place
D. est toujours stable

Q24. Le tri par sélection effectue exactement combien de permutations (swaps) dans le pire cas ?

A. O(n)
B. O(n²)
C. O(n log n)
D. O(1)

Q25. Le nombre de comparaisons du tri fusion est :

A. O(n) dans tous les cas
B. O(n log n) dans tous les cas
C. O(n²) dans le pire cas
D. O(log n)

Corrigé du thème 2

Q	Réponse	Justification
Q16	B	Pivot toujours minimal/maximal → partition déséquilibrée → O(n²).
Q17	C	Le tri fusion préserve l'ordre relatif des clés égales.
Q18	B	Même sur données triées, heapify + extractions font O(n log n).
Q19	A	Il exploite l'intervalle borné des clés (O(n + k)).
Q20	A	Chaque partition balaie la portion du tableau une fois.
Q21	B	Quicksort à random pivot a la meilleure constante pratique.
Q22	A	Si aucun swap lors d'une passe, on s'arrête → O(n) sur trié.
Q23	A	Seule une mémoire additionnelle constante est utilisée.
Q24	A	n-1 échanges maximum (un par position), donc O(n).
Q25	B	Le tri fusion est stable en Θ(n log n) pour toute entrée.

Thème 3 : Structures de données (15 questions)

Q26. Quelle structure implémente le principe LIFO ?

A. File
B. Pile
C. Tas
D. Hash map

Q27. La complexité de l'insertion en tête d'une liste doublement chaînée est :

A. O(n)
B. O(log n)
C. O(1)
D. O(n²)

Q28. Un hash map avec chaînage (table de hachage à chaînes) a une recherche en moyenne de :

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Q29. Le facteur de charge d'une table de hachage est :

A. le nombre de clés divisé par la taille du tableau
B. la taille du tableau divisée par le nombre de clés
C. le nombre de collisions maximum
D. la taille des clés en octets

Q30. Un arbre AVL garantit une hauteur de :

A. O(n)
B. O(log n)
C. O(√n)
D. O(n log n)

Q31. Une file à double extrémité (deque) permet :

A. d'insérer/supprimer aux deux extrémités
B. uniquement en tête
C. uniquement en queue
D. d'accéder en O(1) à n'importe quel élément

Q32. Un tas min supporte extract-min en :

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Q33. Le min d'un tas min se trouve :

A. à la racine
B. dans la dernière feuille
C. dans une feuille quelconque
D. à l'indice n-1 du tableau

Q34. Un union-find avec compression de chemins et union par rang a une complexité amortie de :

A. O(log n)
B. O(α(n)) (fonction d'Ackermann inverse, quasi constante)
C. O(n)
D. O(n log n)

Q35. Une skip list permet une recherche en moyenne de :

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Q36. Quelle structure convient le mieux pour implémenter une file FIFO ?

A. Liste simplement chaînée avec pointeur tête et queue
B. Hash map
C. Tas binaire
D. Arbre AVL

Q37. Un segment tree permet de répondre à des requêtes de somme de plage en :

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Q38. La complexité d'une recherche dans un arbre binaire de recherche équilibré est :

A. O(n)
B. O(log n)
C. O(1)
D. O(√n)

Q39. Dans un B-tree d'ordre m, chaque nœud interne possède au plus :

A. m-1 clés
B. m clés
C. 2m clés
D. m/2 clés

Q40. La structure la plus adaptée pour implémenter un cache LRU est :

A. hash map + liste doublement chaînée
B. tableau trié
C. tas binaire
D. deque seule

Corrigé du thème 3

Q	Réponse	Justification
Q26	B	LIFO = dernier entré, premier sorti = pile.
Q27	C	Avec les deux pointeurs, insertion en tête est constante.
Q28	A	Avec un bon hash et un facteur de charge raisonnable → O(1) moyen.
Q29	A	load factor = n_k / m.
Q30	B	L'équilibre AVL borne la hauteur à O(log n).
Q31	A	Deque = double-ended queue, opérations aux deux bouts.
Q32	B	Retirer la racine puis sift-down → O(log n).
Q33	A	La racine est toujours le minimum (propriété de tas).
Q34	B	Les deux optimisations donnent O(α(n)) quasi constant.
Q35	B	Multiples niveaux probabilistes → O(log n) en moyenne.
Q36	A	Insertion en queue et retrait en tête en O(1).
Q37	B	La requête combine O(log n) nœuds.
Q38	B	La hauteur logarithmique borne la recherche.
Q39	A	Un nœud interne contient m-1 clés et m enfants.
Q40	A	Hash pour O(1) et liste chaînée pour l'ordre d'accès.

Thème 4 : Graphes (15 questions)

Q41. La complexité de BFS sur un graphe représenté par liste d'adjacence est :

A. O(V)
B. O(E)
C. O(V + E)
D. O(V × E)

Q42. Dijkstra ne fonctionne pas si :

A. le graphe a des poids négatifs
B. le graphe est dense
C. le graphe est non orienté
D. le graphe a plus de 1000 sommets

Q43. La complexité de Dijkstra avec un tas binaire est :

A. O(V²)
B. O((V + E) log V)
C. O(V + E)
D. O(E log V)

Q44. Bellman-Ford détecte :

A. les cycles positifs
B. les cycles négatifs
C. les sommets isolés
D. les ponts

Q45. Kruskal (MST) trie les arêtes : quelle est sa complexité ?

A. O(V + E)
B. O(E log E)
C. O(V²)
D. O(E)

Q46. Pour trouver le plus court chemin dans un graphe non pondéré, le plus efficace est :

A. Dijkstra
B. BFS
C. Bellman-Ford
D. Floyd-Warshall

Q47. Le tri topologique est possible uniquement si le graphe est :

A. connexe
B. un DAG (graphe orienté acyclique)
C. pondéré
D. dense

Q48. Floyd-Warshall calcule tous les plus courts chemins en :

A. O(V + E)
B. O(V²)
C. O(V³)
D. O(E log V)

Q49. Un graphe est biparti si :

A. il contient un cycle
B. il peut être colorié avec 2 couleurs
C. il est connexe
D. il est orienté

Q50. Pour une grille de taille n×m (murs inclus), BFS donne le plus court chemin car :

A. chaque arête a un poids de 1
B. BFS est toujours optimal
C. les murs rendent le graphe pondéré
D. la grille est un arbre

Q51. La complexité de DFS (liste d'adjacence) est :

A. O(V)
B. O(E)
C. O(V + E)
D. O(V²)

Q52. Une composante fortement connexe (SCC) est :

A. un ensemble de sommets mutuellement atteignables
B. un sommet avec un degré élevé
C. un sous-graphe dense
D. un cycle de longueur 2

Q53. Le théorème : dans un MST, pour toute coupe du graphe, l'arête de poids minimum traversant la coupe :

A. n'est jamais dans un MST
B. est toujours dans au moins un MST
C. est toujours dans tous les MST
D. n'existe pas toujours

Q54. A* est une extension de Dijkstra utilisant :

A. une heuristique admissible
B. un tri topologique
C. un tas min sans relaxation
D. une matrice d'adjacence

Q55. Pour détecter un cycle dans un graphe non orienté avec DFS, il faut :

A. mémoriser le parent pour ne pas revenir sur l'arête déjà parcourue
B. compter les sommets
C. utiliser une priority queue
D. vérifier les degrés

Corrigé du thème 4

Q	Réponse	Justification
Q41	C	Chaque sommet est visité une fois, chaque arête une fois.
Q42	A	Les poids négatifs cassent la propriété de la file prioritaire.
Q43	B	V extract-min + E relaxations → O((V+E) log V).
Q44	B	Après V-1 relaxations, une relaxation de plus détecte un cycle négatif.
Q45	B	Le tri des arêtes domine : O(E log E).
Q46	B	Poids uniformes → BFS en O(V + E) suffit et est optimal.
Q47	B	Un tri topologique n'existe que sur les DAG.
Q48	C	Trois boucles imbriquées sur V → O(V³).
Q49	B	Bipartition = coloration à 2 couleurs (pas de cycle impair).
Q50	A	Poids unitaires sur chaque déplacement → BFS optimal.
Q51	C	Parcours de tous les sommets et toutes les arêtes.
Q52	A	u et v sont mutuellement atteignables (u→v et v→u).
Q53	B	Propriété de la coupe (cut property) : garantie dans au moins un MST.
Q54	A	f(n) = g(n) + h(n) avec h admissible (≤ coût réel).
Q55	A	On évite de revisiter le parent immédiat (sauf arête d'arbre).

Thème 5 : Programmation dynamique (10 questions)

Q56. Le principe fondamental de la DP est :

A. diviser pour régner sans recouvrement
B. la sous-structure optimale et le recouvrement de sous-problèmes
C. toujours choisir l'optimum local
D. la randomisation

Q57. La mémorisation (memoization) est une approche :

A. bottom-up (itérative)
B. top-down (récursive avec cache)
C. purement gloutonne
D. diviser pour régner

Q58. Pour le problème de la somme maximale de sous-tableau, l'algorithme de Kadane a une complexité de :

A. O(n²)
B. O(n log n)
C. O(n)
D. O(1)

Q59. La distance de Levenshtein entre deux chaînes de longueurs n et m se calcule en :

A. O(n + m)
B. O(n × m)
C. O(n × m) en temps et O(n × m) en mémoire (ou O(m) en mémoire optimisée)
D. O(2^n)

Q60. Dans le problème du sac à dos 0/1, la DP par poids décroissant (itération sur les objets) sert à :

A. éviter de réutiliser un objet plusieurs fois
B. accélérer le tri
C. gérer les poids négatifs
D. réduire la complexité à O(log n)

Q61. La plus longue sous-séquence commune (LCS) a une complexité de :

A. O(n + m)
B. O(n × m)
C. O(n log m)
D. O(n² log m)

Q62. La LIS (plus longue sous-séquence croissante) optimale se calcule en :

A. O(n²)
B. O(n log n) avec la méthode des piles/binary search
C. O(n)
D. O(n log² n)

Q63. Une solution DP est valide si :

A. le problème a une sous-structure optimale et des sous-problèmes recouvrants
B. le problème est NP-complet
C. la récurrence est linéaire
D. il n'y a qu'un seul état

Q64. Le problème des pièces de monnaie (coin change, nombre minimal) avec un système non canonique :

A. se résout par greedy
B. se résout par DP
C. n'a pas de solution
D. exige un graphe pondéré

Q65. Pour unique paths (grille n×m), la DP avec tableau 1D utilise la relation :

A. dp[j] = dp[j] + dp[j-1] ligne par ligne
B. dp[j] = dp[j] * 2
C. dp[j] = max(dp[j], dp[j-1])
D. dp[j] = dp[j+1] + dp[j-1]

Corrigé du thème 5

Q	Réponse	Justification
Q56	B	Deux conditions : sous-structure optimale + sous-problèmes recouvrants.
Q57	B	Top-down = récursif + cache des résultats.
Q58	C	Une seule passe, deux variables → O(n).
Q59	B	Grille n×m de transitions → O(n×m).
Q60	A	Parcourir les poids en décroissant empêche la réutilisation (0/1).
Q61	B	Grille de taille n×m → O(n×m).
Q62	B	Le tableau `tails` + binary search donne O(n log n).
Q63	A	Ce sont les deux conditions de validité de la DP.
Q64	B	Sans propriété canonique, greedy échoue ; il faut la DP.
Q65	A	`dp[j] += dp[j-1]` en parcourant gauche→droite pour chaque ligne.

Thème 6 : Greedy (8 questions)

Q66. Un algorithme glouton :

A. explore toutes les solutions
B. choisit l'optimum local à chaque étape sans revenir en arrière
C. utilise toujours la programmation dynamique
D. trie systématiquement

Q67. Le rendu de monnaie glouton est optimal pour :

A. tout système de pièces
B. les systèmes canoniques (ex. {1, 5, 10, 25})
C. les sommes multiples de 5
D. les pièces en nombre pair

Q68. Le problème de l'activité (intervalle scheduling) se résout en triant les activités par :

A. durée croissante
B. date de fin croissante
C. date de début croissante
D. profit décroissant

Q69. Pour construire un MST, la stratégie de Prim :

A. ajoute à chaque étape l'arête de poids minimal reliant l'arbre au reste
B. trie toutes les arêtes puis fusionne par union-find
C. ajoute l'arête de poids maximal
D. utilise BFS

Q70. La différence clé entre Prim et Kruskal est :

A. Prim ajoute un arbre ; Kruskal fusionne des composantes
B. Prim trie les arêtes ; Kruskal grandit un seul arbre
C. Prim est O(E log E) ; Kruskal est O(V²) dans tous les cas
D. Aucune : ils sont identiques

Q71. Un problème admet une solution greedy optimale si :

A. il possède une propriété du choix glouton et une sous-structure optimale
B. il est linéaire
C. ses données sont triées
D. il a une solution unique

Q72. Le « jump game II » (saut minimal) se résout en :

A. O(n²)
B. O(n) avec greedy (fenêtres de portée maximale)
C. O(n log n)
D. O(2^n)

Q73. Dans le problème du fractionnement de valeur (fractional knapsack), le greedy trie par :

A. poids croissant
B. valeur/coût décroissant
C. valeur croissante
D. nom des objets

Corrigé du thème 6

Q	Réponse	Justification
Q66	B	Optimum local immédiat, aucune exploration arrière.
Q67	B	Greedy optimal sur les systèmes canoniques (preuves classiques).
Q68	B	Trier par fin croissante maximise le nombre d'activités compatibles.
Q69	A	Prim grandit un arbre par arêtes de poids minimal sortantes.
Q70	A	Prim : un arbre qui grossit ; Kruskal : union de forêts.
Q71	A	Deux conditions nécessaires (choix glouton + sous-structure optimale).
Q72	B	Une passe en tenant les bornes `end` et `farthest` → O(n).
Q73	B	Fractional knapsack : ratio valeur/poids décroissant.

Thème 7 : Strings (12 questions)

Q74. L'algorithme KMP précalcule :

A. une table de hachage des suffixes
B. le tableau π (prefix-function) du motif
C. un arbre de suffixes
D. un tri de la chaîne

Q75. La complexité de la recherche KMP est :

A. O(n × m)
B. O(n + m)
C. O(n log m)
D. O(m)

Q76. Rabin-Karp utilise :

A. un hash roulant modulaire
B. un tri comptage
C. une pile
D. un arbre AVL

Q77. Une trie (arbre de préfixes) permet de :

A. rechercher un préfixe en O(longueur de la clé)
B. trier en O(1)
C. hacher sans collisions
D. compresser sans perte

Q78. L'algorithme de Manacher calcule le plus long palindrome en :

A. O(n²)
B. O(n log n)
C. O(n)
D. O(n³)

Q79. Aho-Corasick est :

A. un automate pour rechercher plusieurs motifs simultanément
B. un tri de suffixes
C. une compression LZ
D. une distance d'édition

Q80. La distance de Hamming entre deux chaînes de longueur égale est :

A. le nombre de positions où les caractères diffèrent
B. le nombre de caractères identiques
C. la longueur de la plus longue sous-chaîne commune
D. le nombre de sous-chaînes distinctes

Q81. Le plus long préfixe commun (LCP) de "algorithm" et "algorithmics" est :

A. "algo"
B. "algorithm"
C. "algorithms"
D. "alg"

Q82. Un suffix array permet de rechercher une sous-chaîne en :

A. O(1)
B. O(m log n) (binary search) après construction
C. O(n)
D. O(n × m)

Q83. Le problème « minimum window substring » se résout optimalement avec :

A. deux pointeurs + compteur de fréquences
B. KMP
C. Manacher
D. un tri lexicographique

Q84. La complexité de la construction naïve (par concaténations successives) d'une chaîne de longueur n est :

A. O(n)
B. O(n²) (si les concaténations copient la chaîne à chaque fois)
C. O(log n)
D. O(1)

Q85. Pour vérifier si deux chaînes sont des anagrammes, la meilleure complexité est :

A. O(n log n) (tri) ou O(n) (comptage)
B. O(n²)
C. O(1)
D. O(2^n)

Corrigé du thème 7

Q	Réponse	Justification
Q74	B	π donne la plus longue bordure propre de chaque préfixe.
Q75	B	Chaque caractère du texte est traité O(1) amorti → O(n + m).
Q76	A	Hash glissant recalculé en O(1) par fenêtre.
Q77	A	La recherche descend le long de la clé, O(len).
Q78	C	Centres expansés + miroirs → O(n) linéaire.
Q79	A	Automate de motifs avec liens de faille pour multi-recherche.
Q80	A	Définition même de la distance de Hamming.
Q81	B	Les deux commencent par les 9 caractères "algorithm".
Q82	B	Binary search sur le tableau trié de suffixes → O(m log n).
Q83	A	Sliding window + compteurs ; O(n) en temps.
Q84	B	Chaque concaténation recopie → somme des copies = O(n²).
Q85	A	Tri O(n log n) ou comptage de lettres O(n).

Thème 8 : Mathématiques (15 questions)

Q86. L'algorithme d'Euclide calcule :

A. le PPCM
B. le PGCD
C. la factorielle
D. l'inverse modulaire

Q87. La complexité de l'algorithme d'Euclide est :

A. O(n)
B. O(log min(a, b))
C. O(√n)
D. O(min(a, b))

Q88. lcm(a, b) s'exprime comme :

A. a + b
B. |a × b| / gcd(a, b)
C. a × b
D. gcd(a, b) / (a × b)

Q89. Le crible d'Ératosthène liste les premiers ≤ n en :

A. O(n)
B. O(n log log n)
C. O(n log n)
D. O(√n)

Q90. Pour tester la primalité d'un entier n, il suffit de tester les diviseurs jusqu'à :

A. n
B. n/2
C. √n
D. log n

Q91. Le petit théorème de Fermat affirme que si p est premier et a non multiple de p :

A. aᵖ ≡ a (mod p)
B. aᵖ⁻¹ ≡ 1 (mod p)
C. a² ≡ 1 (mod p)
D. a ≡ p (mod p)

Q92. L'inverse modulaire de a modulo m (premier) se calcule par :

A. exponentiation rapide : aᵐ⁻² mod m
B. division simple
C. crible d'Ératosthène
D. tri fusion

Q93. La factorielle de n comporte combien de zéros terminaux ?

A. ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …
B. n/2
C. ⌊n/10⌋
D. n - 1

Q94. La complexité de la multiplication naïve de deux matrices n×n est :

A. O(n²)
B. O(n³)
C. O(n log n)
D. O(2^n)

Q95. L'algorithme de Strassen réduit la complexité de la multiplication matricielle à environ :

A. O(n³)
B. O(n^2.807)
C. O(n²)
D. O(n log n)

Q96. Le coefficient binomial C(n, k) vérifie la relation :

A. C(n, k) = C(n-1, k-1) + C(n-1, k)
B. C(n, k) = C(n, k-1) × 2
C. C(n, k) = n × k
D. C(n, k) = C(n-1, k-1) × C(n-1, k)

Q97. Le théorème des restes chinois s'applique à :

A. des systèmes de congruences
B. des graphes bipartis
C. des chaînes de caractères
D. des tas binaires

Q98. La probabilité que deux éléments sur m tombent dans le même compartiment (hash) est liée à :

A. l'anniversaire (paradoxe des anniversaires)
B. la loi de Benford
C. le théorème de Bayes
D. la distribution de Poisson

Q99. La somme 1 + 2 + 4 + … + 2^(n-1) vaut :

A. 2^n - 1
B. 2^n
C. n²
D. n

Q100. Pour un calcul a^b mod m avec b = 10^18, le nombre d'opérations de l'exponentiation modulaire rapide est :

A. environ 60 multiplications
B. environ 10^18 multiplications
C. environ 10^9 multiplications
D. 1 multiplication

Corrigé du thème 8

Q	Réponse	Justification
Q86	B	Euclide calcule le PGCD par soustractions/modulos successifs.
Q87	B	Chaque étape divise au moins par 2 → O(log min(a, b)).
Q88	B	PPCM = produit / PGCD (avec valeurs absolues).
Q89	B	Somme harmonique des marquages → O(n log log n).
Q90	C	Si n = a×b avec a ≤ b, alors a ≤ √n.
Q91	B	aᵖ⁻¹ ≡ 1 (mod p) pour p premier et a non divisible par p.
Q92	A	a·aᵐ⁻² ≡ 1 (mod m) par Fermat.
Q93	A	Chaque facteur 5 apporte un zéro : somme des divisions par 5.
Q94	B	n³ produits/sommes pour la multiplication classique.
Q95	B	Récurrence 7 multiplications → O(n^log₂7) ≈ O(n^2.807).
Q96	A	Formule de Pascal.
Q97	A	Résolution de x ≡ aᵢ (mod mᵢ) pour modules premiers entre eux.
Q98	A	Les collisions de hash suivent la probabilité de coïncidence d'anniversaire.
Q99	A	Somme géométrique de raison 2 → 2^n - 1.
Q100	A	log₂(10^18) ≈ 60 bits → ~60 carrés modulaires.

Grille de notation

Score	Niveau
90 – 100	Excellent — prêt pour entretien senior.
75 – 89	Très bien — quelques lacunes ciblées à revoir.
50 – 74	Passable — reprendre les chapitres concernés.
< 50	Insuffisant — refaire les chapitres 01 à 16 avant de reprendre.

Les réponses détaillées et les démonstrations se trouvent dans les chapitres correspondants (01 à 16) et les corrigés du chapitre 19.