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

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. Quel est le résultat du parcours d’un arbre de recherche binaire (BST) dans l’ordre ?

A Une permutation aléatoire des éléments de l’arbre

B Les éléments de l’arbre triés par ordre décroissant

C Les éléments de l’arbre triés par ordre croissant

D Les éléments dans l’ordre où ils ont été insérés

L’exécution du parcours d’un arbre de recherche binaire (BST) dans l’ordre fait que les éléments de l’arbre sont visités dans l’ordre ascendant, en raison du modèle de parcours racine gauche-droite.

2. Comment trouver le sommet d’un arbre binaire ?

A En comptant le nombre d’enfants de gauche

B En comptant le nombre d’enfants de droite

C En calculant la profondeur maximale de la racine à n’importe quelle feuille

D En calculant le nombre total de nœuds

La hauteur d’un arbre binaire est déterminée en calculant la profondeur maximale de la racine à n’importe quelle feuille, ce qui implique de trouver récursivement la hauteur de chaque sous-arbre et de sélectionner la valeur la plus élevée, plus un pour le nœud racine.

3. Vous avez implémenté un arbre, mais vous avez remarqué que les nœuds enfants ne sont pas correctement associés à leurs parents. Quel peut être le problème ?

A L’arbre n’est pas initialisé correctement en tant que graphe

B Les nœuds enfants sont ajoutés au mauvais parent

C La structure de l’arbre ne prend pas en charge la hiérarchie

D Les nœuds ne sont pas correctement liés

Si les nœuds enfants ne sont pas correctement associés à leurs parents, il se peut que les nœuds enfants soient ajoutés au mauvais parent, ce qui indique un problème dans la manière dont les nœuds sont insérés dans l’arbre.

4. Quelle est la complexité temporelle du tri rapide dans le meilleur des cas ?

A O(n log n)

B O(n)

C O(log n)

D O(n^2)

Dans le meilleur des cas, la complexité temporelle du tri rapide est de O(n log n), grâce à une sélection optimale des points centrales qui divise uniformément le tableau.

5. Quel algorithme de tri est fondamentalement stable ?

A Tri rapide

B Tri en tas

C Tri par fusion

D Tri à bulles

Le tri par fusion est stable, il maintient l’ordre d’origine des éléments égaux, ce qui le rend adapté au tri de données complexes.

6. Que signifie « stabilité » dans les algorithmes de tri ?

A La performance sous contrainte

B Maintien de l’ordre relatif des éléments égaux

C Utilisation minimale de la mémoire

D Temps de tri le plus rapide possible

La stabilité signifie que le tri conserve l’ordre relatif des données ayant des clés égales, ce qui est important pour le tri en plusieurs étapes et la préservation des séquences de données.

7. Quelle est la complexité temporelle dans le pire des cas d’une recherche binaire sur un tableau trié de n éléments ?

A O(n log n)

B O(n)

C O(log n)

D O(n^2)

La recherche binaire a une complexité temporelle de O(log n) dans le pire des cas en raison de son approche « diviser pour régner », qui divise l’espace de recherche par deux à chaque étape.

8. Quel algorithme de tri est le plus efficace pour un ensemble de données dont la plage de valeurs entières est connue et limitée ?

A Tri rapide

B Tri comptage

C Tri par fusion

D Tri à bulles

Tri comptage est idéal pour les ensembles de données comportant un nombre limité d’entiers, car il compte les occurrences plutôt que d’effectuer des comparaisons directes, ce qui permet d’effectuer un tri efficace.

9. Quel principe les algorithmes de tri « diviser pour régner » utilisent-ils ?

A Diviser les données en parties plus petites et les trier individuellement

B Sélection aléatoire des éléments

C Traversée linéaire

D Échange direct d’éléments

Les algorithmes de division et de conquête, tels que le tri par fusion et le tri rapide, divisent les données en plusieurs parties, trient ces parties indépendamment les unes des autres, puis les combinent en un tout trié.

10. Pourquoi le tri rapide est-il généralement préféré au tri par fusion pour le tri des tableaux dans la pratique ?

A La complexité de l’espace est plus faible

B Temps de tri moyen plus rapide

C Plus simple à mettre en œuvre

D Stabilité du tri garantie

Le tri rapide est souvent préféré pour les tableaux en raison de sa capacité de tri sur place, offrant une complexité spatiale moindre par rapport au tri par fusion, qui nécessite de l’espace supplémentaire pour la fusion.

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

QCMs qui pourraient vous intéresser :

1. Quel est le résultat du parcours d’un arbre de recherche binaire (BST) dans l’ordre ?

2. Comment trouver le sommet d’un arbre binaire ?

3. Vous avez implémenté un arbre, mais vous avez remarqué que les nœuds enfants ne sont pas correctement associés à leurs parents. Quel peut être le problème ?

4. Quelle est la complexité temporelle du tri rapide dans le meilleur des cas ?

5. Quel algorithme de tri est fondamentalement stable ?

6. Que signifie « stabilité » dans les algorithmes de tri ?

7. Quelle est la complexité temporelle dans le pire des cas d’une recherche binaire sur un tableau trié de n éléments ?

8. Quel algorithme de tri est le plus efficace pour un ensemble de données dont la plage de valeurs entières est connue et limitée ?

9. Quel principe les algorithmes de tri « diviser pour régner » utilisent-ils ?

10. Pourquoi le tri rapide est-il généralement préféré au tri par fusion pour le tri des tableaux dans la pratique ?

Vous pourrez aussi aimer

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

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

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

Laisser un commentaire Annuler la réponse