WayToLearnX

qcm-algorithmes-et-structures-de-donnees-analyse-1
QCM Algorithmes

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

Thomas

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.
 
[wx_adsense]  

1. Quel algorithme est le mieux adapté pour résoudre un problème de recherche de chemin le plus court avec des obstacles dans un graphe ?

A Dijkstra

B Bellman-Ford

C Tri rapide

D A* (A-star)

D
L’algorithme A* est un algorithme de recherche de chemin qui utilise à la fois les coûts des chemins et une estimation (heuristique) de la distance restante pour trouver le chemin le plus court. C’est un algorithme très efficace pour des graphes avec des obstacles.

 

 

2. Dans un graphe dirigé acyclique (DAG), quel algorithme permet de trouver un ordre topologique des sommets ?

A Algorithme de Dijkstra

B Algorithme de Bellman-Ford

C Algorithme de Kruskal

D Recherche en profondeur (DFS) avec un tri topologique

D
Dans un graphe dirigé acyclique (DAG), l’ordre topologique des sommets peut être obtenu par un parcours en profondeur (DFS). Lors du parcours, on empile les sommets et, à la fin de l’exécution de DFS, on les sort dans l’ordre inverse de leur « fin de traitement ».

 

 

3. Quelle est la complexité en temps du code suivant ?
void example(int n) {
    for (int i = 0; i < n; i++) {
        // Première boucle imbriquée
        for (int j = 0; j < n / 2; j++) {
            printf("%d, %d\n", i, j);
        }

        // Deuxième boucle
        for (int k = 0; k < n; k++) {
            printf("%d, %d\n", i, k);
        }
    }
}

A O(n)

B O(n²)

C O(n log n)

D O(n³)

B
La première boucle s'exécute n fois. La deuxième boucle s'exécute n/2 fois pour chaque itération de la première boucle, et la troisième boucle s'exécute n fois pour chaque itération de la première boucle. Donc, la complexité totale est O(n × n/2 + n × n), ce qui donne O(n²).

 

 
[wx_adsense]  

4. Quelle est la complexité en temps du code suivant ?
void example(int n) {
    // Première boucle imbriquée
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d, %d\n", i, j);
        }
        for (int k = 0; k < n; k++) {
            printf("%d, %d\n", i, k);
        }
    }

    // Seconde boucle
    for (int l = 0; l < n; l++) {
        printf("%d\n", l);
    }
}

A O(n)

B O(n²)

C O(n log n)

D O(n³)

B
La première partie du code (deux boucles imbriquées) a une complexité de O(n²), et la troisième boucle a une complexité de O(n). La complexité totale est donc O(n² + n), ce qui donne O(n²).

 

 

5. Quel est le rôle de la fonction de hachage dans une table de hachage ?

A Elle permet de trier les éléments avant de les insérer dans la table.

B Elle permet de calculer la position à laquelle un élément sera stocké dans la table.

C Elle permet de créer des sous-tableaux pour organiser les éléments.

D Elle permet de maintenir un ordre strict entre les éléments de la table.

B
Une fonction de hachage prend une clé et calcule un index dans la table où la valeur associée à cette clé sera stockée. Elle permet un accès rapide aux éléments dans la table de hachage.

 

 

6. Quel est l'algorithme utilisé pour résoudre le problème de la somme des sous-ensembles ?

A Programmation dynamique

B Tri rapide

C Recherche binaire

D Recherche par dichotomie

A
Le problème de la somme des sous-ensembles, où l'on cherche à déterminer s'il existe un sous-ensemble d'un ensemble donné dont la somme est égale à une valeur cible, peut être résolu efficacement avec un algorithme de programmation dynamique.

 

 
[wx_adsense]  

7. Quelle est la complexité en temps du code suivant ?
void example(int n) {
    int i = 1;
    while (i < n) {
        printf("%d\n", i);
        i *= 2;
    }
}

A O(n)

B O(n²)

C O(n log n)

D O(log n)

D
La valeur de i est multipliée par 2 à chaque itération, donc la boucle s'exécute en fonction du logarithme de n. La complexité est donc O(log n).

 

 

8. Qu'est-ce qu'un graphe connexe ?

A Un graphe dans lequel tous les sommets sont reliés entre eux par une arête.

B Un graphe dans lequel tous les sommets ont le même nombre d'arêtes.

C Un graphe dans lequel il existe un chemin entre chaque paire de sommets.

D Un graphe dans lequel tous les sommets sont directement connectés.

C
Un graphe est connexe si, pour chaque paire de sommets, il existe un chemin qui les relie. Cela signifie qu'il est possible de se déplacer entre n'importe quels deux sommets du graphe.

 

 

9. Quel algorithme est le plus adapté pour trier une petite quantité d'éléments ?

A Tri rapide (Quicksort)

B Tri par sélection

C Tri fusion (Merge Sort)

D Tri par tas (Heapsort)

B
Le tri par sélection est simple et souvent plus efficace pour des petites quantités d'éléments, malgré sa complexité de O(n²). Cependant, pour des tableaux de grande taille, des algorithmes comme le tri rapide (Quicksort) ou le tri fusion sont plus performants.

 

 
[wx_adsense]  

10. Quelle est la principale caractéristique de la programmation dynamique ?

A Elle divise un problème en sous-problèmes indépendants et les résout en parallèle.

B Elle résout un problème en réutilisant les solutions des sous-problèmes déjà résolus pour éviter de les recalculer.

C Elle repose sur une approche gloutonne pour résoudre un problème.

D Elle utilise une approche de recherche exhaustive pour trouver toutes les solutions possibles.

B
La programmation dynamique consiste à résoudre un problème en découpant ce dernier en sous-problèmes, puis en mémorisant leurs résultats afin d'éviter de recalculer plusieurs fois les mêmes sous-problèmes.

 

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.
[wx_amazon]
QCMs qui pourraient vous intéresser :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *