Numérique et sciences informatiques · term

Implémentation de structures de données en C++ : listes chaînées, piles et files

Ce que tu dois retenir

Chapitre 1 — Structures linéaires et pointeurs en C++

Un pointeur permet de relier dynamiquement des éléments en mémoire.

Chapitre 2 — Implémenter une liste chaînée

L'insertion et la suppression en tête d'une liste chaînée se font en temps constant O(1).

Chapitre 3 — Implémenter une pile

Dans une pile, toutes les opérations se font au sommet, en O(1) avec une liste chaînée.

Chapitre 4 — Implémenter une file

Une file utilise deux pointeurs (tête et queue) pour des opérations en O(1).

Teste-toi

1. Quelle structure suit le principe LIFO ?

AA. File
BB. Pile
CC. Liste chaînée
DD. Tableau
Voir la réponse

Réponse : B — B. Pile

Une pile est LIFO (Last In, First Out) : le dernier élément inséré est le premier retiré.

2. Dans une liste chaînée simple, que contient le champ suivant du dernier nœud ?

AA. nullptr
BB. l'adresse de la tête
CC. zéro
DD. rien
Voir la réponse

Réponse : A — A. nullptr

Le dernier nœud pointe vers nullptr pour indiquer la fin de la liste.

3. Quelle opération n'est pas une opération de pile ?

AA. push
BB. pop
CC. top
DD. enqueue
Voir la réponse

Réponse : D — D. enqueue

enqueue (enfiler) est une opération de file, pas de pile. Les opérations de pile sont push, pop et top.

4. Pour une file implémentée avec une liste chaînée, quels pointeurs sont nécessaires ?

AA. tête seulement
BB. queue seulement
CC. tête et queue
DD. aucun
Voir la réponse

Réponse : C — C. tête et queue

Il faut un pointeur vers la tête pour défiler et un pointeur vers la queue pour enfiler en O(1).

5. L'insertion en tête d'une liste chaînée est en ?

AA. O(n)
BB. O(log n)
CC. O(1)
DD. O(n²)
Voir la réponse

Réponse : C — C. O(1)

On modifie seulement deux pointeurs, indépendamment de la taille de la liste, donc complexité constante O(1).

6. Quel mot-clé C++ alloue dynamiquement un objet ?

AA. malloc
BB. new
CC. create
DD. alloc
Voir la réponse

Réponse : B — B. new

En C++, l'opérateur new alloue dynamiquement de la mémoire et appelle le constructeur si nécessaire. malloc est du C.

7. Que se passe-t-il si on dépile une pile vide ?

AA. rien
BB. erreur ou comportement indéfini
CC. renvoie 0
DD. supprime la pile
Voir la réponse

Réponse : B — B. erreur ou comportement indéfini

Dépiler une pile vide revient à déréférencer un pointeur nul ou accéder hors limites, ce qui provoque une erreur ou un comportement indéfini.

8. Quelle structure est adaptée pour un historique de navigation (bouton retour) ?

AA. File
BB. Pile
CC. Tableau trié
DD. Liste doublement chaînée circulaire
Voir la réponse

Réponse : B — B. Pile

Le bouton retour revient à la page précédente, c'est-à-dire la dernière visitée : comportement LIFO d'une pile.

Retour au cours ruedusavoir.com · Apprendre, c'est avancer.