QCM Algorithmes, structures de données et complexité – Partie 7

mai 1, 2019avril 7, 2025 Amine KOUIS Aucun commentaire algorithmes, correction, corrigé, exercices, pdf, QCM, question, structures de données, test

Les algorithmes, les structures de données et la complexité sont des concepts fondamentaux en informatique, essentiels pour concevoir des systèmes performants et efficaces. Que vous soyez étudiant, professionnel en développement logiciel ou passionné par l’informatique, comprendre ces notions est crucial pour résoudre des problèmes complexes et optimiser les performances des applications. Dans cet article, nous vous proposons un QCM (Questionnaire à Choix Multiples) couvrant ces trois domaines clés. À travers ce test, vous pourrez évaluer vos connaissances en matière de conception d’algorithmes, de choix de structures de données appropriées et d’analyse de la complexité des algorithmes. Que vous soyez débutant ou confirmé, ce QCM vous aidera à tester vos compétences et à améliorer votre compréhension de ces concepts fondamentaux.

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.

1. Lequel des algorithmes de tri suivants présente la plus faible complexité dans le pire des cas?

A Tri par fusion

B Tri à bulles

C Tri rapide

D Tri par sélection

La bonne réponse est: A – Tri par fusion

Explication :

Tri par fusion a une complexité de O(n log n) dans le pire des cas, ce qui en fait un des algorithmes de tri les plus efficaces en termes de complexité temporelle, même dans le pire des cas.
Tri à bulles et tri par sélection ont une complexité de O(n²) dans le pire des cas, ce qui les rend moins efficaces pour de grandes entrées.
Tri rapide a une complexité de O(n log n) dans le cas moyen, mais dans le pire des cas (lorsque la partition choisie est toujours la plus mauvaise), sa complexité peut atteindre O(n²), ce qui le rend moins performant que le tri par fusion dans le pire des cas.

2. Les éléments d’un tableau sont successivement stockés dans des zones de mémoire car _____?

A De cette façon, l’ordinateur ne peut garder trace que de l’adresse du premier élément et les adresses des autres éléments peuvent être calculées

B l’architecture de la mémoire de l’ordinateur ne permet pas aux matrices de stocker autre que série

C Les deux A et B

D Aucun de ces réponses

Les tableaux sont généralement stockés de manière contiguë en mémoire. Cela signifie que les éléments du tableau sont placés successivement dans des zones de mémoire adjacentes. En conservant uniquement l’adresse du premier élément, l’ordinateur peut calculer l’adresse des autres éléments en utilisant un simple calcul basé sur l’index et la taille de chaque élément.

3. Quelle est la complexité temporelle du tri fusion dans le pire des cas ?

A O(n)

B O(n log n)

C O(n²)

D O(log n)

Le tri fusion (Merge Sort) a une complexité en O(n log n) dans tous les cas (meilleur, moyen et pire cas). C’est un algorithme de tri stable qui divise la liste en sous-listes, les trie et les fusionne efficacement.

4. La complexité de l’algorithme de recherche binaire est ______?

A O(n)

B O(log n)

C O(n2)

D O(n log n)

L’algorithme de recherche binaire fonctionne en divisant constamment l’intervalle de recherche par deux à chaque étape, ce qui réduit de moitié le nombre d’éléments à examiner à chaque itération.

Recherche binaire est utilisée sur des tableaux triés, et elle consiste à comparer l’élément cible à l’élément du milieu du tableau, puis à éliminer la moitié du tableau à chaque itération, en réduisant ainsi la taille du problème à chaque étape.
Cette approche donne une complexité logarithmique, c’est-à-dire O(log n), car à chaque itération, la taille du tableau à chercher est divisée par deux.

Par conséquent, la complexité temporelle de l’algorithme de recherche binaire est O(log n).

5. Quelle est la complexité temporelle de la recherche linéaire dans un tableau ?

A O(1)

B O(log n)

C O(n)

D O(n²)

La recherche linéaire consiste à parcourir chaque élément du tableau jusqu’à ce que l’élément recherché soit trouvé. La complexité est donc O(n), car dans le pire des cas, il faut vérifier tous les éléments du tableau.

6. Le résultat de parcours d’une arbre de recherche binaire _____?

A Une liste non triée

B Une inversion de l’entrée

C Une liste triée

D Aucune de ces réponses

Un arbre de recherche binaire (BST) est une structure de données où pour chaque nœud, les éléments à gauche de ce nœud sont inférieurs à l’élément du nœud, et les éléments à droite sont supérieurs.

Lorsque vous effectuez un parcours en ordre (ou in-order traversal) d’un arbre de recherche binaire, vous visitez les nœuds dans l’ordre croissant, c’est-à-dire que vous traversez d’abord le sous-arbre gauche, puis le nœud lui-même, puis le sous-arbre droit. Ce parcours produit donc une liste triée des éléments de l’arbre. Exemple:

Si l’arbre contient les éléments [5, 3, 7, 2, 4, 6, 8], un parcours en ordre produira la liste triée : [2, 3, 4, 5, 6, 7, 8].

Ainsi, le résultat d’un parcours d’un arbre de recherche binaire est toujours une liste triée.

7. Dans la fonction pgcd() suivante, nous avons : n >= m.

int pgcd(n,m)
{
  if (n%m ==0) return m;  
  n = n%m;
  return pgcd(m, n);
}

Combien d’appels récursifs sont effectués par cette fonction?

A Θ(log n)

B Ω(n)

C Θ(log log n)

D Θ(sqrt(n))

La fonction donnée implémente l’algorithme d’Euclide pour calculer le PGCD (plus grand commun diviseur) de deux nombres n et m (avec n >= m). L’algorithme d’Euclide fonctionne en remplaçant l’argument n par n % m à chaque appel récursif jusqu’à ce que n % m == 0.

Lors de chaque appel récursif, la taille de n diminue de manière significative : le reste n % m est toujours plus petit que m, ce qui réduit la taille de l’un des deux nombres de manière rapide. En conséquence, le nombre d’appels récursifs est proportionnel à la logarithme du plus petit nombre, ce qui donne une complexité en Θ(log n) dans le pire des cas.

Pourquoi pas les autres réponses ?

Ω(n) : Ce serait le cas si l’algorithme devait effectuer un grand nombre d’opérations dans le pire des cas, mais ici l’algorithme réduit le problème de façon logarithmique à chaque itération, pas linéairement.
Θ(log log n) : La réduction est logarithmique, mais pas doublement logarithmique. La complexité est donc Θ(log n), pas Θ(log log n).
Θ(sqrt(n)) : Cela serait pertinent si l’algorithme effectuait des recherches en divisant la taille de l’entrée par une racine carrée à chaque étape, mais ici ce n’est pas le cas.

Conclusion: Le nombre d’appels récursifs effectués par la fonction est Θ(log n), car l’algorithme d’Euclide divise la taille du problème de manière logarithmique.

8. Une file est une structure de données qui fonctionne sur ______?

A LIFO

B FIFO

C FILO

D Aucune de ces réponses

Une file (ou queue) est une structure de données qui fonctionne selon le principe FIFO, c’est-à-dire que le premier élément ajouté à la file est le premier à être retiré. Cela ressemble au fonctionnement d’une file d’attente dans la vie réelle, où la première personne à entrer dans la file est la première à être servie.

9. Une liste chaînée est une structure dynamique?

A Vrai

B Faux

Une liste chaînée est une structure de données dynamique car elle permet l’ajout et la suppression d’éléments sans nécessiter de redimensionner ou de réallouer de la mémoire en une seule fois. Chaque élément d’une liste chaînée, appelé un nœud, contient une donnée et un pointeur vers le nœud suivant (et éventuellement vers le nœud précédent dans le cas d’une liste chaînée doublement liée).

L’avantage des listes chaînées par rapport aux tableaux est leur capacité à s’adapter dynamiquement en fonction de l’ajout ou de la suppression d’éléments, car les éléments ne sont pas stockés dans des zones de mémoire contiguës.

10. La récursion utilise plus d’espace mémoire que les itérations car _____?

A Il utilise la pile au lieu de la file.

B Chaque appel récursif doit être stocké.

C Les deux A et B sont vrais.

D Aucune de ces réponses n’est vraie.

Lorsqu’un algorithme utilise la récursion, chaque appel récursif consomme de l’espace mémoire supplémentaire sur la pile d’exécution. En effet, chaque appel récursif crée une nouvelle instance de la fonction avec ses propres variables locales et son état d’exécution, qui doivent être stockés jusqu’à ce que l’appel récursif se termine et que le contrôle retourne à l’appelant.

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.

QCMs qui pourraient vous intéresser :

1. Lequel des algorithmes de tri suivants présente la plus faible complexité dans le pire des cas?

2. Les éléments d’un tableau sont successivement stockés dans des zones de mémoire car _____?

3. Quelle est la complexité temporelle du tri fusion dans le pire des cas ?

4. La complexité de l’algorithme de recherche binaire est ______?

5. Quelle est la complexité temporelle de la recherche linéaire dans un tableau ?

6. Le résultat de parcours d’une arbre de recherche binaire _____?

7. Dans la fonction pgcd() suivante, nous avons : n >= m.

8. Une file est une structure de données qui fonctionne sur ______?

9. Une liste chaînée est une structure dynamique?

10. La récursion utilise plus d’espace mémoire que les itérations car _____?

Vous pourrez aussi aimer

QCM Algorithmes, structures de données et complexité – Partie 22

QCM Algorithmes, structures de données et complexité – Partie 17

QCM Algorithmes – Notions de base – Partie 3

Laisser un commentaire Annuler la réponse