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

A

 

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 (nLogn) 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.

D
Le tri par tas est une technique de tri basée sur la comparaison et qui repose sur la structure de données du tas binaire. C’est pareil au tri par sélection où nous trouvons d’abord l’élément maximum et plaçons l’élément maximum à la fin. Nous répétons le même processus pour le rest.

 

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

C

 

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

C
La complexité temporelle dans le pire cas est toujours supérieure ou égale à la complexité temporelle moyenne.

 

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

A
L’ordre de croissance de l’option A est n ^ 2.5, ce qui est supérieur à n ^ 2.

 

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

B

 

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) = nLogn
   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
À l’exception de g3(n), tous les autres sont exponentiels. Donc, g3 est définitivement la première en sortie.

 

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

A

 

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

A
Nous pouvons l’obtenir en prenant un exemple du type n = 98765. Après 2 itérations, res = 56 et n = 987.

 

 

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

A N ^ 2

B NlogN

C N

D N (logN) ^ 2

C
Le tri à bulle est optimal si les données d’entrée sont triées. c’est-à-dire si les données d’entrée sont triées dans le même ordre que la sortie attendue. Ceci peut être réalisé en utilisant une variable booléenne. La variable booléenne est utilisée pour vérifier si les valeurs sont échangées au moins une fois dans la boucle interne. Prenez l’extrait de code suivant:

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

Veuillez noter que dans le code ci-dessus, la boucle « for » externe ne s’exécute qu’une seule fois.

 

Partagez cet article

Laisser un commentaire

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