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

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. Quelle opération permet d’ajouter un élément au sommet d’une pile ?

A push

B pop

C enqueue

D dequeue

L’opération « push » est utilisée pour ajouter un élément au sommet d’une pile, selon le principe LIFO (Last In, First Out).

2. Considérons l’implémentation d’une pile. Que fait l’opération suivante ?

stack.pop()

A Ajoute un élément à la pile

B Retire l’élément supérieur de la pile

C Lit l’élément supérieur sans l’enlever

D Vérifie si la pile est vide

L’opération stack.pop() retire l’élément supérieur de la pile, selon le principe LIFO (Last In, First Out) où le dernier élément ajouté est le premier à être retiré.

3. Comment implémenter une file d’attente en utilisant deux piles, pile1 et pile2 ?

A En alternant les éléments entre la pile 1 et la pile 2

B En poussant des éléments dans la pile 1 et en les retirant de la pile 2 pour la mise en file d’attente

C En utilisant la pile 1 pour la mise en file d’attente et la pile 2 pour la mise hors file d’attente

D Aucun des éléments ci-dessus

Pour mettre en œuvre une file d’attente à l’aide de deux piles, la pile 1 est utilisée pour mettre les éléments en file d’attente en les poussant dessus. Pour les opérations de retrait de la file d’attente, les éléments sont extraits de la pile 1 et poussés dans la pile 2 si celle-ci est vide, ce qui garantit que le premier élément entré dans la pile 1 se trouve au sommet de la pile 2 pour le retrait de la file d’attente, maintenant ainsi l’ordre FIFO avec les piles LIFO.

4. Dans une pile, l’opération pop renvoie parfois l’élément correct et parfois l’élément nul. Quelle est l’erreur probable ?

A La pile ne vérifie pas correctement les conditions de underflow.

B L’opération push est incohérente

C La pile écrase des éléments

D Toutes les réponses ci-dessus

Si l’opération pop sur une pile renvoie parfois un résultat nul, cela indique probablement que la pile ne vérifie pas correctement les conditions de underflow, lorsqu’elle tente de retirer un élément d’une pile vide.

5. Quelle est la caractéristique qui distingue les arbres binaires des autres types d’arbres ?

A Chaque nœud a au plus deux enfants

B Chaque nœud a exactement deux enfants

C Les nœuds sont organisés de manière binaire

D Les nœuds contiennent des données binaires

Un arbre binaire est caractérisé par le fait que chaque nœud a au maximum deux enfants, ce qui le distingue des autres types d’arbres qui peuvent autoriser un nombre quelconque d’enfants par nœud.

6. Où se trouve le plus petit élément d’un arbre de recherche binaire (BST) ?

A La feuille la plus à gauche

B La feuille la plus à droite

C Le nœud racine si l’arbre est équilibré

D Directement sous le nœud racine si l’arbre est complet

Le plus petit élément d’un arbre de recherche binaire (BST) se trouve à la feuille la plus à gauche, car les propriétés du BST imposent que tous les nœuds à gauche soient plus petits que leurs nœuds parents.

7. Quelle est la principale différence entre les graphes et les arbres ?

A Les arbres contiennent des cycles, alors que les graphes n’en contiennent pas.

B Les graphes contiennent des cycles, alors que les arbres n’en contiennent pas

C Les arbres ne peuvent avoir qu’une seule racine, alors que les graphes peuvent en avoir plusieurs

D Les graphes sont des structures hiérarchiques, alors que les arbres ne le sont pas.

La principale différence entre les graphes et les arbres est que les graphes peuvent contenir des cycles, ce qui permet à tout nœud d’être potentiellement relié à lui-même par une série de liens, alors que les arbres sont des structures hiérarchiques acycliques.

8. Quelle est la structure de données la mieux adaptée à l’implémentation de la liste d’adjacence d’un graphe ?

A Le tableau

B Liste chaînée

C Table de hachage

D Arbre

Une liste chaînée est la mieux adaptée à l’implémentation de la liste d’adjacence d’un graphe car elle gère efficacement les tailles dynamiques des listes d’adjacence, ce qui permet d’ajouter et de supprimer facilement des liens.

9. Dans un graphe orienté, que représente la ligne reliant un nœud A à un nœud B ?

A Une relation bidirectionnelle

B Une relation unidirectionnelle de A à B

C Une relation hiérarchique

D Une relation entre pairs

Dans un graphe orienté, un arc allant du nœud A au nœud B représente une relation unidirectionnelle, indiquant qu’il existe un chemin de A à B mais pas nécessairement de B à A.

10. Quelle est la propriété d’un arbre de recherche binaire équilibré (BST) ?

A Les hauteurs des sous-arbres gauche et droit diffèrent au maximum d’une unité.

B Chaque sous-arbre est un arbre complet

C Chaque sous-arbre est un arbre binaire complet

D Tous les nœuds feuilles sont au même niveau

Un arbre de recherche binaire équilibré (BST) est défini par la propriété selon laquelle les hauteurs des sous-arbres gauche et droit de tout nœud diffèrent au maximum d’une unité, ce qui garantit l’efficacité d’opérations telles que l’insertion, la suppression et la consultation.

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

QCMs qui pourraient vous intéresser :

1. Quelle opération permet d’ajouter un élément au sommet d’une pile ?

2. Considérons l’implémentation d’une pile. Que fait l’opération suivante ?

3. Comment implémenter une file d’attente en utilisant deux piles, pile1 et pile2 ?

4. Dans une pile, l’opération pop renvoie parfois l’élément correct et parfois l’élément nul. Quelle est l’erreur probable ?

5. Quelle est la caractéristique qui distingue les arbres binaires des autres types d’arbres ?

6. Où se trouve le plus petit élément d’un arbre de recherche binaire (BST) ?

7. Quelle est la principale différence entre les graphes et les arbres ?

8. Quelle est la structure de données la mieux adaptée à l’implémentation de la liste d’adjacence d’un graphe ?

9. Dans un graphe orienté, que représente la ligne reliant un nœud A à un nœud B ?

10. Quelle est la propriété d’un arbre de recherche binaire équilibré (BST) ?

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 11

Laisser un commentaire Annuler la réponse