QCM Algorithmes, structures de données et complexité – Partie 6
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 cas suivants n’existe pas dans la théorie de la complexité?
A Meilleur cas
B Pire cas
C Moyenne cas
D Cas null
2. Quelle est la pire complexité temporelle du tri par insertion où la position des données à insérer est calculée à l’aide d’une recherche binaire?
A N
B N * logN
C N ^ 2
D N (logN) ^ 2
3. Quelle est la complexité temporelle de la fonction ci-dessous?
void algo(int n, int tab[]) { int i = 0, j = 0; for(; i < n; ++i) while(j < n && tab[i] < tab[j]) j++; }
A O(n)
B O(n^2)
C O(n * logn)
D O(n(logn)^2)
4. Le pire cas se produit dans l’algorithme de recherche linéaire lorsque ________?
A L’élément se trouve au milieu du tableau
B L’élément ne se trouve pas dans le tableau
C L’élément se trouve dans la dernière position du tableau
D L’élément se trouve dans la dernière position du tableau ou il n’existe pas
5. Considérons les boucles for suivantes:
A for(i = 0; i < n; i++)
B for(i = 0; i < n; i += 2)
C for(i = 1; i < n; i *= 2)
D for(i = n; i < -1; i /= 2)
Si n est la taille de l’entrée (positive), quelle boucle est la plus efficace ?
6. Qu’est-ce que cela signifie quand on dit qu’un algorithme X est asymptotiquement plus efficace que Y?
A X sera un meilleur choix pour toutes les entrées
B X sera un meilleur choix pour toutes les entrées sauf les petites entrées
C X sera un meilleur choix pour toutes les entrées sauf les grandes entrées
D Y sera un meilleur choix pour les petits entrées
7. La complexité de l’algorithme de tri à bulles est _____?
A O(n)
B O(log n)
C O(n2)
D O(n * log n)
8. Quelle est la complexité temporelle de l’algorithme de Floyd-Warshall pour calculer tous les chemins les plus courts d’une paire dans un graphe à n sommets?
A O(n ^ 2logn)
B Θ(n ^ 2logn)
C Θ(n ^ 4)
D Θ(n ^ 3)
9. La déclaration log(n!) = Θ(n * log n) est-elle valide?
A Vrai
B Faux
10. Les tableaux sont les meilleures structures de données
A Pour les collections de données relativement permanentes
B Pour les collections de données dont la structure changent constamment
C Tout les réponses sont vrais
D Aucun de ces réponses
Je vous remercie énormement pour votre site . Que le meilleur me soit enseigner par votre site.
oskur c dur