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

avril 8, 2025avril 8, 2025 Thomas Aucun commentaire

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.

1. Quelle structure de données est idéale pour implémenter un accès rapide à la donnée minimum ?

A Pile (Stack)

B File (Queue)

C Tas (Heap)

D Tableau dynamique

Un tas (Heap) est une structure de données particulièrement adaptée pour accéder rapidement à l’élément minimum (dans un min-heap) ou maximum (dans un max-heap). La racine du tas contient l’élément de plus petite (ou plus grande) valeur, ce qui permet d’y accéder en O(1).

2. Quelle structure de données est la plus appropriée pour représenter un graphe complet ?

A Matrice d’adjacence

B Liste d’adjacence

C Tableau dynamique

D Pile

Une matrice d’adjacence est une structure efficace pour représenter un graphe complet, car elle nécessite une matrice carrée pour stocker les connexions entre tous les nœuds du graphe. Elle est particulièrement adaptée aux graphes avec un grand nombre d’arêtes, car chaque paire de nœuds a une arête.

3. Quel algorithme de tri a une complexité de O(n log n) dans tous les cas ?

A Tri par insertion

B Tri par sélection

C Tri rapide (QuickSort)

D Tri par fusion (MergeSort)

Le tri par fusion (MergeSort) a une complexité de O(n log n) dans tous les cas (meilleur, moyen et pire). Il divise le tableau en sous-tableaux, trie ces sous-tableaux de manière récursive, puis les fusionne.

4. Quelle est la méthode principale utilisée dans l’algorithme Dijkstra ?

A Diviser et conquérir

B Programmation dynamique

C Exploration en profondeur

D Exploration en largeur

L’algorithme Dijkstra utilise une approche de programmation dynamique pour trouver le plus court chemin entre un nœud source et tous les autres nœuds d’un graphe pondéré (sans arêtes de poids négatif). Il met à jour les distances progressivement en utilisant une table des distances minimales.

5. Quel est l’ordre de complexité de l’algorithme de multiplication de matrices naïf pour deux matrices n×n ?

A O(n)

B O(n²)

C O(n³)

D O(n⁴)

L’algorithme naïf de multiplication de matrices nécessite trois boucles imbriquées pour parcourir toutes les lignes et colonnes des matrices, ce qui donne une complexité de O(n³) pour multiplier deux matrices de taille n×n.

6. Quelle est la principale limitation d’un tableau dynamique par rapport à un tableau statique ?

A Les éléments sont indexés de manière non consécutive.

B Le tableau dynamique peut être redimensionné, mais cela prend du temps.

C Le tableau dynamique a une capacité fixe qui ne peut pas être modifiée.

D Le tableau dynamique ne permet pas d’accéder à un élément par son index.

Bien que les tableaux dynamiques puissent être redimensionnés (ils doublent généralement de taille lorsqu’ils sont pleins), ce redimensionnement prend du temps (O(n)) lors de l’ajout de nouveaux éléments. En revanche, un tableau statique a une taille fixe et ne nécessite pas de redimensionnement.

7. Lorsqu’on parle de la « complexité en espace » d’un algorithme, cela fait référence à _______.

A La taille de la sortie de l’algorithme.

B La taille de l’entrée.

C Le temps d’exécution de l’algorithme.

D La quantité de mémoire nécessaire pour stocker les données pendant l’exécution de l’algorithme.

La complexité en espace fait référence à la mémoire supplémentaire que l’algorithme nécessite pour fonctionner, en plus de l’espace nécessaire pour les données d’entrée. Cela peut inclure la mémoire utilisée pour les piles de récursion, les tableaux temporaires, etc.

8. Dans un algorithme de programmation dynamique, quelle est la principale caractéristique des sous-problèmes résolus ?

A Ils sont résolus indépendamment.

B Ils sont résolus de manière gloutonne.

C Ils sont résolus plusieurs fois.

D Ils sont résolus une seule fois et stockés pour éviter les recomputations.

En programmation dynamique, les sous-problèmes sont résolus une seule fois et leurs résultats sont mémorisés dans une table (mémoïsation ou tabulation) pour éviter de les résoudre plusieurs fois, ce qui améliore l’efficacité de l’algorithme.

9. Quelle est la complexité temporelle du code suivant?

int compteur (int n)
{
   int c = 0;
   for(int i = n; i > 0; i/= 2)
      for(int j = 0; j < i; j++)
         c += 1;
   return c;
}

A O(n^2)

B O(n*Logn)

C O(n)

D O(n*Logn*Logn)

Comme « nbr » est un nombre entier en entrée, la déclaration de compteur() est exécutée comme suite: n + n / 2 + n / 4 + … 1
Donc, la complexité temporelle T(n) peut être écrite comme suite:
T (n) = O (n + n / 2 + n / 4 + … 1) = O (n)
La valeur du c est également :
n + n / 2 + n / 4 + .. + 1

10. Quelle est la complexité temporelle du code suivant?

int compteur2(int n)
{
  int c = 0;
  for (int i = 0; i < n; i++)
     for (int j = i; j > 0; j--)
        c = c + 1;
  return c;
}

A O(n)

B O(n^2)

C O(n*Logn)

D O(n*Logn*Logn)

La complexité temporelle peut être calculée en comptant le nombre de fois que l’expression « c = c + 1; » est exécuté. L’expression est exécutée 0 + 1 + 2 + 3 + 4 + …. + (n-1) fois.

Complexité temporelle = O(0 + 1 + 2 + 3 + .. + n-1) = O(n * (n-1) / 2) = O(n ^ 2)

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

QCMs qui pourraient vous intéresser :

1. Quelle structure de données est idéale pour implémenter un accès rapide à la donnée minimum ?

2. Quelle structure de données est la plus appropriée pour représenter un graphe complet ?

3. Quel algorithme de tri a une complexité de O(n log n) dans tous les cas ?

4. Quelle est la méthode principale utilisée dans l’algorithme Dijkstra ?

5. Quel est l’ordre de complexité de l’algorithme de multiplication de matrices naïf pour deux matrices n×n ?

6. Quelle est la principale limitation d’un tableau dynamique par rapport à un tableau statique ?

7. Lorsqu’on parle de la « complexité en espace » d’un algorithme, cela fait référence à _______.

8. Dans un algorithme de programmation dynamique, quelle est la principale caractéristique des sous-problèmes résolus ?

9. Quelle est la complexité temporelle du code suivant?

10. Quelle est la complexité temporelle du code suivant?

Vous pourrez aussi aimer

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

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

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

Laisser un commentaire Annuler la réponse