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

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é temporelle de l’algorithme de recherche en profondeur (DFS) dans un graphe ?

A O(n)

B O(n + m)

C O(n²)

D O(m)

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

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

A O(1)

B O(n)

C O(n²)

D O(2^n)

3. Quelle structure de données est idéale pour implémenter un tableau associatif ?

A Tableau

B Liste chaînée

C Table de hachage

D Tas

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

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

A O(n)

B O(n²)

C O(n³)

D O(n⁴)

5. Dans quelle situation un algorithme de recherche par dichotomie (ou recherche binaire) ne peut-il pas être utilisé ?

A Lorsque la liste est triée

B Lorsque la liste est triée mais contient des éléments dupliqués

C Lorsque la liste n'est pas triée

D Lorsque la liste contient des nombres entiers uniquement

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

void example(int n) {
    int i = 1;
    while (i < n) {
        printf("%d\n", i);
        i *= 3;
    }
}

A O(n)

B O(log n)

C O(n log n)

D O(3^n)

7. Quel est le principal avantage des algorithmes de tri stables ?

A Ils n'ont pas besoin de mémoire supplémentaire.

B Ils conservent l'ordre des éléments égaux dans le tableau après le tri.

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

D Ils sont plus faciles à implémenter.

8. Qu'est-ce que la complexité O(n log n) représente ?

A Un algorithme qui se comporte linéairement par rapport à la taille des entrées.

B Un algorithme dont la durée d'exécution augmente proportionnellement au logarithme de la taille des entrées.

C Un algorithme qui se comporte à la fois de manière linéaire et logarithmique par rapport à la taille des entrées.

D Un algorithme qui est plus rapide qu'un algorithme de complexité O(n).

9. 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);
        }
    }

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

A O(n)

B O(n²)

C O(n log n)

D O(n³)

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

int example(int n) {
    if (n <= 1) {
        return n;
    }
    
    // Affiche les valeurs de i de 0 à n-1
    for (int i = 0; i < n; i++) {
        printf("%d\n", i);
    }
    
    // Appel récursif
    return example(n - 1);
}

A O(n)

B O(n²)

C O(n log n)

D O(2^n)