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

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 est la complexité en temps du code suivant ?

int example(int n) {
    if (n == 1) {
        return 1;
    }
    return n * example(n - 1);
}

A O(1)

B O(n)

C O(n log n)

D O(n²)

2. Que signifie la complexité O(1) dans un algorithme ?

A L’algorithme a une complexité qui dépend du nombre d’éléments traités.

B L’algorithme exécute un nombre constant d’opérations, quel que soit la taille de l’entrée.

C L’algorithme est linéaire et croît proportionnellement à la taille de l’entrée.

D L’algorithme a une complexité qui diminue au fur et à mesure que les éléments sont traités.

3. Quelle est la complexité en temps du code suivant ?

void example(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i % 2 == 0 && j % 2 == 0) {
                printf("%d, %d\n", i, j);
            }
        }
    }
}

A O(n³)

B O(n)

C O(n log n)

D O(n²)

4. Quel est l'algorithme qui permet de résoudre le problème du sac à dos (Knapsack) ?

A Recherche binaire

B Programmation dynamique

C Tri fusion

D Tri à bulles

5. Quelle est la différence entre une liste chaînée simple et une liste chaînée double ?

A Une liste chaînée simple contient un seul pointeur vers le nœud suivant, tandis qu'une liste chaînée double contient un pointeur vers le nœud suivant et un pointeur vers le nœud précédent.

B Une liste chaînée simple contient un pointeur vers un tableau, tandis qu'une liste chaînée double contient un pointeur vers un arbre.

C Une liste chaînée double est plus rapide que la simple, quelle que soit la situation.

D Il n'y a aucune différence; les deux structures fonctionnent de la même manière.

6. Quelle est la complexité en temps du code suivant ?

void example(int n) {
    for (int i = 0; i < n; i++) {
        printf("%d\n", i);
    }

    for (int j = 0; j < n; j++) {
        printf("%d\n", j);
    }
}

A O(n³)

B O(n)

C O(n log n)

D O(n²)

7. Quel est l'algorithme utilisé pour résoudre le problème du plus court chemin dans un graphe avec des poids négatifs ?

A Dijkstra

B A* (A-star)

C Floyd-Warshall

D Bellman-Ford

8. Quelle est la complexité en temps du code suivant ?

void example(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                printf("%d, %d\n", i, j);
            }
        }
    }
}

A O(n³)

B O(n)

C O(n log n)

D O(n²)

9. Quelle est la complexité temporelle de l'algorithme de recherche dans une table de hachage ?

A O(1)

B O(n)

C O(n log n)

D O(n²)

10. Quelle est la principale caractéristique des algorithmes de tri en place ?

A Ils nécessitent de la mémoire supplémentaire pour stocker les éléments triés.

B Ils modifient l'ordre des éléments dans le tableau ou la liste sans utiliser d'espace mémoire supplémentaire significatif.

C Ils sont plus rapides que les autres algorithmes de tri.

D Ils fonctionnent uniquement sur des structures de données comme les tableaux à une dimension.