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

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. Le facteur temps pour déterminer l’efficacité de l’algorithme est mesuré par _____?

A Compter les microsecondes

B Compter le nombre d’opérations

C Compter le nombre de déclarations

D Compter les kilo-octets d’algorithme

B

 

2. Quelle est la complexité temporelle du code suivant?
int compteur2(int n)
{
  int c = 0;
  for (int i = 0; i < n; i++)
     for (int j = i; j > 0; j--)
        c = c + 1;
  return c;
}

A O(n)

B O(n^2)

C O(n*Logn)

D O(nLognLogn)

B
La complexité temporelle peut être calculée en comptant le nombre de fois que l’expression « c = c + 1; » est exécuté. L’expression est exécutée 0 + 1 + 2 + 3 + 4 + …. + (n-1) fois.

Complexité temporelle = O(0 + 1 + 2 + 3 + .. + n-1) = O(n * (n-1) / 2) = O(n ^ 2)

 

 

3. Laquelle des structures de données suivantes n’est pas une structure de données linéaire?

A Tableaux

B Liste chaînée

C Les deux A et B

D Aucune des réponses ci-dessus

D
Différence entre structure de données linéaire et non linéaireDifférence entre structure de données linéaire et non linéaireLes structures de données linéaire organisent les données dans une séquence et suivent une sorte d’ordre. Alors que les structures de données non linéaire n’organisent…Lire plus
4. Quelle est la complexité temporelle du code suivant?
int compteur (int n)
{
   int c = 0;
   for(int i = n; i > 0; i/= 2)
      for(int j = 0; j < i; j++)
         c += 1;
   return c;
}

A O(n^2)

B O(nLogn)

C O(n)

D O(nLognLogn)

C
Comme « nbr » est un nombre entier en entrée, la déclaration de compteur() est exécutée comme suite: n + n / 2 + n / 4 + … 1
Donc, la complexité temporelle T(n) peut être écrite comme suite:
T (n) = O (n + n / 2 + n / 4 + … 1) = O (n)
La valeur du c est également :
n + n / 2 + n / 4 + .. + 1

 

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. La complexité de l’algorithme Recherche Linéaire est _____?

A O(n)

B O(log n)

C O(n2)

D O(n log n)

A

 

 

7. La complexité en moyenne se produit dans l’algorithme Recherche Linéaire. Quand l’élément recherché _______?

A Se trouve au milieu du tableau

B Ne se trouve pas dans le tableau

C Est le dernier élément du tableau

D Est le dernier élément du tableau ou n’y est pas du tout

A

 

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

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

B
Le pire de cas de l’algorithme du tri rapide se produit lorsque l’élément clé sélectionné se trouve à la fin du tableau. Dans le pire des cas, l’algorithme du tri rapide appelle de manière récursive un sous-problème de taille 0 et un autre sous-problème de taille (n-1). La récurrence est donc T (n) = T (n-1) + T (0) + O (n) L’expression peut être réécrite sous la forme T (n) = T (n-1) + O (n)

 

9. Laquelle des structures de données suivantes est une structure de données linéaire?

A Arbres

B Graphes

C Tableaux

D Aucun de ces réponses

C
Différence entre structure de données linéaire et non linéaireDifférence entre structure de données linéaire et non linéaireLes structures de données linéaire organisent les données dans une séquence et suivent une sorte d’ordre. Alors que les structures de données non linéaire n’organisent…Lire plus
 
10. Supposons que nous ayons un algorithme de temps O (n) qui trouve la médiane d’un tableau non trié. Considérons maintenant une implémentation de l’algorithme du tri rapide où nous trouvons d’abord la médiane en utilisant l’algorithme du tri rapide, puis utilisons la médiane comme pivot. Quelle sera la pire complexité temporelle de cet algorithme modifié?
 
A O(n^2 Logn)

B O(n^2)

C O(n Logn Logn)

D O(nLogn)

D
Si nous utilisons la médiane comme élément pivot, la récurrence dans tous les cas devient alors T (n) = 2T (n / 2) + O (n).

 

Partagez cet article

Une réflexion sur “QCM Algorithmes, structures de données et complexité – Partie 4

Laisser un commentaire

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