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

Questions pratiques pour testez vos connaissances sur la complexité en espace et en temps des algorithmes et des structures de données courants. Testez votre connaissance et travaillez sur les questions que vous trompez le plus souvent.

1. La complexité du cas moyen d’un algorithme est _______?

A Beaucoup plus compliqué à analyser que celui du pire des cas

B Beaucoup plus simple à analyser que celle du pire des cas

C Parfois plus compliqué et parfois plus simple que celui du pire des cas

D Aucun de ces réponses

2. Lequel des énoncés suivants n’est pas vrai en ce qui concerne les algorithmes de tri basés sur la comparaison?

A La complexité temporelle minimale possible d’un algorithme de tri basé sur la comparaison est O (n * Logn) pour un tableau d’entrée aléatoire.

B Tout algorithme de tri basé sur la comparaison peut être rendu stable en utilisant la position comme critère lorsque deux éléments sont comparés

C Le tri comptage n’est pas un algorithme de tri basé sur la comparaison

D Le tri par tas n’est pas un algorithme de tri basé sur la comparaison.

3. Deux mesures principales pour l’efficacité d’un algorithme sont _______?

A Processeur et mémoire

B Complexité et capacité

C Temps et espace

D Données et espace

 
4. Soit w(n) et V(n), respectivement, le pire des cas et le temps moyen d’exécution d’un algorithme exécuté sur une entrée de taille n. Lequel des énoncés suivants est TOUJOURS VRAI?
 
A V(n) = Θ(w(n))

B V(n) = Ω(w(n))

C V(n) = O(w(n))

D V(n) = o(w(n))

5. 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

6. Les listes chaînées sont les mieux adaptées pour ____?

A La collecte de données relativement permanentes

B La taille et les données qui changent constamment

C Tout les réponses sont vrais

D Aucun de ces réponses

7. 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

8. Le facteur d’espace est mesuré par ____?

A La taille de la mémoire maximale requise par l’algorithme

B La taille de la mémoire minimale requise par l’algorithme

C La taille de la mémoire moyenne requise par l’algorithme

D La taille de l’espace disque maximum requis par l’algorithme

9. 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

10. 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; 
}