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

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. Considérez le programme suivant pour inverser les chiffres d’un entier afin d’obtenir un nouvel entier. Soit n = P1P2… Pm

int n, res;
res = 0;
while (n > 0) 
{ 
   res = res*10 + n%10; 
   n = n/10; 
}

La condition de la boucle à la fin de l’itération est la suivante:

A n = P1P2… .Pm-i et res = PmPm-1… Pm-i + 1

B n = Pm-i + 1… Pm-1Pm et res = Pm-1… .P2P1

C n = P1P2… .Pm et res = PmPm-1… P2P1

D n! = res

2. Quelle est la meilleure complexité temporelle de l’algorithme de tri à bulles?

A N ^ 2

B N * logN

C N

D N (log * N) ^ 2

int main () {

    int tab[] = {9, 1, 5, 8, 3};
    int i;
    int j;
    int isSwapped;
    int n = sizeof(tab) / sizeof(*tab);

    isSwapped = 1;

    for (i = 0; i < n - 1 && isSwapped; ++ i) {
        isSwapped = 0; 
        for(j = 0; j < n - i - 1; ++ j)
            if (tab[j] > tab[j + 1]) {
                swap (&tab[j], &tab[j + 1]);
                isSwapped = 1;
            }
    } 
    for (i = 0; i < n; ++ i) 
        printf ("%d", tab[i]); 

    return 0; 
}

3. Quelle est la complexité temporelle de la fonction ci-dessous?

void algo(int n, int tab[])
{
    int i = 0, j = 0;
    for(; i < n; ++i)
        while(j < n && tab[i] < tab[j])
            j++;
}

A O(n)

B O(n^2)

C O(n * logn)

D O(n(logn)^2)

void algo2(int n, int tab[]) {
     int i = 0, j = 0;
     for(; i < n; ++i) {
          j = 0; 
          while(j < n && tab[i] < tab[j]) 
               j++; 
     } 
}

4. Considérons la fonction suivante

 int fun(int n) {
    int i, j, k = 0;
    for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;
 }

Quelle est la valeur retournée par la fonction ci-dessus?

A Θ(n^2)

B Θ(n^2Logn)

C Θ(n^3)

D Θ(n^3Logn)

5. La relation de récurrence capturant le temps optimal du problème de la tour de Hanoi avec n disques est. _______?

A T (n) = 2T (n – 2) + 2

B T (n) = 2T (n – 1) + n

C T (n) = 2T (n / 2) + 1

D T (n) = 2T (n – 1) + 1

D

 
Voici les étapes à suivre pour résoudre le problème de la tour de Hanoi de manière récursive.

Soit les trois piquets A, B et C. Le but est de déplacer n disques de A à C.
Pour déplacer n disques de la piquet A à la piquet C:

• déplacez les n-1 disques de A à B. Cela laisse le disque n seul sur la piquet A
• déplacer le disque n de A à C
• déplacez n?1 disques de B en C pour qu’ils soient sur le disque n

La fonction de récurrence T (n) pour la complexité temporelle de la solution récursive ci-dessus peut être écrite comme suit. T (n) = 2T (n-1) + 1

 

6. Quelle est la récurrence pour le pire de cas de l’algorithme du tri rapide et quelle est la complexité temporelle dans le pire des cas?

A La récurrence est T (n) = T (n-2) + O (n) et la complexité temporelle est O (n ^ 2)

B La récurrence est T (n) = T (n-1) + O (n) et la complexité temporelle est O (n ^ 2)

C La récurrence est T (n) = 2T (n / 2) + O (n) et la complexité temporelle est O (n*Logn)

D La récurrence est T (n) = T (n / 10) + T (9n / 10) + O (n) et la complexité temporelle est O (n*Logn)

7. Lequel des éléments suivants n’est pas O (n ^ 2)?

A n ^ 3 / (sqrt (n))

B n ^ 1,78

C (13 ^ 10) * n + 12087

D (2 ^ 40) * n

8. Laquelle des options fournit l’ordre croissant de la complexité asymptotique des fonctions g1, g2, g3 et g4?

   g1 (n) = 2 ^ n
   g2(n) = n ^ (3/2)
   g3(n) = n * Logn
   g4(n) = n ^ (logn)

A g3, g2, g4, g1

B g3, g2, g1, g4

C g2, g3, g1, g4

D g2, g3, g4, g1

B O(n^2)

C O(n*Logn*Logn)

D O(n*Logn)

10. Considérons les trois instructions suivantes

1. (n + m) ^ k = Θ(n ^ m), où k et m sont des constantes
2. 2 ^ (n + 1) = O(2 ^ n)
3. 2 ^ (2n + 1 ) = O(2 ^ n)

Lesquelles de ces affirmations sont correctes?

A 1 et 2

B 1 et 3

C 2 et 3

D 1, 2, et 3