QCM Algorithmes, structures de données et complexité – Partie 7
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
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)
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
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
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))
8. La file est une structure de données qui fonctionne sur ______?
A LIFO
B FIFO
C FILO
D Aucune de ces réponses
9. Une liste chaînée est une structure dynamique?
A Vrai
B Faux
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.