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

mai 1, 2019février 9, 2020 Amine KOUIS Aucun commentaire algorithmes, correction, corrigé, exercices, pdf, QCM, question, structures de données, test

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. Lequel des algorithmes de tri suivants présente la plus faible complexité dans le pire des cas?

A Tri par fusion

B Tri à bulles

C Tri rapide

D Tri par sélection

Les pires de cas pour les algorithmes de tri ci-dessus sont les suivants:

Tri par fusion : n Logn
Tri à bulle de nLogn : n ^ 2
Tri rapide : n ^ 2
Tri par sélection : n ^ 2

2. Les éléments d’un tableau sont successivement stockés dans des zones de mémoire car _____?

A De cette façon, l’ordinateur ne peut garder trace que de l’adresse du premier élément et les adresses des autres éléments peuvent être calculées

B l’architecture de la mémoire de l’ordinateur ne permet pas aux matrices de stocker autre que série

C Les deux A et B

D Aucun de ces réponses

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

La boucle externe s’exécute n / 2 ou Θ(n) fois.
La boucle interne exécute Θ(Logn) fois (notez que j est multiplié par 2 à chaque itération).
Donc, la déclaration « k = k + n / 2; » exécute Θ(nLogn) fois.
L’instruction augmente la valeur de k de n / 2. Donc, la valeur de k devient n / 2 * Θ(nLogn) qui est Θ(n ^ 2Logn)

4. La complexité de l’algorithme de recherche binaire est ______?

A O(n)

B O(log)

C O(n2)

D O(n log n)

5. Considérons les trois instructions suivantes

(n + m) ^ k = Θ(n ^ m), où k et m sont des constantes
2 ^ (n + 1) = O(2 ^ n)
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

(1) (n + m) ^ k = n ^ k + c1 * n ^ (k – 1) + … k ^ m = Θ(n ^ k)
(2) 2 ^ (n + 1) = 2 * 2 ^ n = O( 2 ^ n)

6. Le résultat de parcours d’une arbre de recherche binaire _____?

A Une liste non triée

B Une inversion de l’entrée

C Une liste triée

D Aucune de ces réponses

L’arbre de recherche binaire donne une liste triée lorsqu’il est traversé dans l’ordre.

7. Dans la fonction pgcd() suivante, nous avons : n >= m.

int pgcd(n,m)
{
  if (n%m ==0) return m;  
  n = n%m;
  return pgcd(m, n);
}

Combien d’appels récursifs sont effectués par cette fonction?

A Θ(logn)

B Ω(n)

C Θ(loglogn)

D Θ(sqrt(n))

Le code ci-dessus est l’implémentation de l’algorithme euclidien de recherche du plus grand commun diviseur (PGCD).

8. La file est une structure de données qui fonctionne sur ______?

A LIFO

B FIFO

C FILO

D Aucune de ces réponses

Dans la file, l’élément inséré en premier sera disponible en premier et l’élément inséré en dernier sera disponible dans le dernier. FIFO signifie First In First Out.

9. Une liste chaînée est une structure dynamique?

A Vrai

B Faux

Une liste chaînée est une structure dynamique, elle peut être réduite et augmentée à la demande du programme.

10. La récursion utilise plus d’espace mémoire que les itérations car _____?

A Il utilise la pile au lieu de la file.

B Chaque appel récursif doit être stocké.

C Les deux A et B sont vrais.

D Aucune de ces réponses n’est vraie.

La récursivité utilise la pile, mais la raison principale est que chaque appel récursif doit être stocké séparément dans la mémoire.

QCMs qui pourraient vous intéresser :