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

juillet 6, 2024juillet 6, 2024 Thomas Aucun commentaire

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.

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.

1. Lequel des énoncés suivants décrit le mieux la complexité temporelle de l’insertion d’un élément dans un arbre de recherche binaire ?

A O(1)

B O(log n)

C O(n)

D O(n log n)

La complexité du temps moyen pour l’insertion d’un élément dans un arbre de recherche binaire est O(log n), en supposant que l’arbre soit équilibré.

2. Quelle est la complexité temporelle du tri sélectif dans le pire des cas ?

A O(n^2)

B O(log n)

C O(n)

D O(n log n)

Dans le pire des cas, la complexité temporelle du tri sélectif est de O(n^2), ce qui se produit lorsque la sélection du point central est insuffisante, par exemple lorsque le plus petit ou le plus grand élément est sélectionné comme point central à chaque étape de la partition.

3. Comment la complexité spatiale d’une solution itérative se compare-t-elle à celle d’une solution récursive pour le même problème ?

A Les solutions itératives utilisent toujours plus d’espace

B Les solutions récursives utilisent toujours plus d’espace

C Dépend du problème spécifique

D Elles utilisent la même quantité d’espace

La comparaison de la complexité spatiale entre les solutions itératives et récursives dépend du problème spécifique et des détails de la mise en œuvre. Dans certains cas, les solutions récursives peuvent utiliser plus d’espace de pile, tandis que les solutions itératives peuvent utiliser plus d’espace de tas, ou vice versa.

4. Quelle est la complexité temporelle de l’algorithme suivant ?

Pour i de 1 jusqu'à N faire 
    Ecrire i
FinPour

A O(n^2)

B O(log n)

C O(n)

D O(n log n)

L’extrait de code a une complexité temporelle de O(n) car il affiche chaque nombre de 0 à n-1, ce qui rend le nombre d’opérations directement proportionnel à n.

5. Quelle est la complexité temporelle de l’algorithme suivant ?

Pour i de 1 jusqu'à N faire 
    Pour j de 1 jusqu'à N faire 
        Ecrire i,j
    FinPour
FinPour

A O(n^2)

B O(log n)

C O(n)

D O(n log n)

Les boucles imbriquées entraînent une complexité temporelle de O(n^2), car pour chaque élément de la première boucle, la deuxième boucle s’exécute n fois, ce qui donne n*n opérations.

6. Analysez la complexité temporelle de la fonction suivante:

function func(n):
if n <= 1:
return else func(n/2) + func(n/2)

A O(n^2)

B O(log n)

C O(n)

D O(n log n)

Cette fonction fait deux appels à elle-même avec la moitié de n, ce qui conduit à une complexité temporelle de O(n log n) en raison de la division de n et de la profondeur de la récursion.

7. Un algorithme qui devrait s'exécuter en O(n log n) s'exécute beaucoup plus lentement. La cause probable est:

A Un cas de base incorrect dans la récursion

B Allocation de mémoire excessive

C Mauvais choix du point central dans le tri

D Toutes ces réponses

Un mauvais choix du point central (pivot) dans les algorithmes de tri comme le tri sélectif peut dégrader les performances jusqu'à O(n^2), ce qui est nettement plus lent que la valeur attendue de O(n log n).

8. Une fonction conçue pour être de complexité O(n) prend plus de temps lorsque n augmente. Qu'est-ce qui pourrait être négligé ?

A Les boucles imbriquées

B Les facteurs constants

C Opérations linéaires

D Aucune de ces réponses

Les boucles imbriquées peuvent involontairement augmenter la complexité temporelle d'un algorithme, faisant en sorte qu'une fonction supposée de complexité O(n) s'exécute en O(n^2) ou avec une complexité plus élevée.

9. Un algorithme récursif censé avoir une complexité temporelle de O(log n) s'exécute plus lentement. Le problème probable est:

A Ne pas diviser par deux l'entrée à chaque appel récursif

B Condition de terminaison incorrecte

C Débordement de la pile

D Toutes les réponses ci-dessus

Si l'algorithme récursif ne divise pas l'entrée par deux à chaque appel, il n'atteindra pas la complexité temporelle O(log n) attendue, ce qui se traduira par des performances plus lentes.

10. Quelle structure de données doit être utilisée pour stocker une collection de caractères dans une séquence ?

A Tableau

B Pile

C File d'attente

D Graphe

Un tableau est la structure de données la plus appropriée pour stocker une séquence de caractères car il permet l'indexation, ce qui est efficace pour accéder aux caractères à des positions spécifiques.

Voir aussi 100 Exercices Corrigés En Algorithme avec les Organigrammes.

QCMs qui pourraient vous intéresser :

1. Lequel des énoncés suivants décrit le mieux la complexité temporelle de l’insertion d’un élément dans un arbre de recherche binaire ?

2. Quelle est la complexité temporelle du tri sélectif dans le pire des cas ?

3. Comment la complexité spatiale d’une solution itérative se compare-t-elle à celle d’une solution récursive pour le même problème ?

4. Quelle est la complexité temporelle de l’algorithme suivant ?

5. Quelle est la complexité temporelle de l’algorithme suivant ?

6. Analysez la complexité temporelle de la fonction suivante:

7. Un algorithme qui devrait s'exécuter en O(n log n) s'exécute beaucoup plus lentement. La cause probable est:

8. Une fonction conçue pour être de complexité O(n) prend plus de temps lorsque n augmente. Qu'est-ce qui pourrait être négligé ?

9. Un algorithme récursif censé avoir une complexité temporelle de O(log n) s'exécute plus lentement. Le problème probable est:

10. Quelle structure de données doit être utilisée pour stocker une collection de caractères dans une séquence ?

Vous pourrez aussi aimer

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

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

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

Laisser un commentaire Annuler la réponse