Fiche d’exercices de Structures de données avec corrigé

Comment s'appelle l'opération de pile qui ajoute un élément au sommet ?

1. AEnqueue (enfiler)
2. BPush (empiler)
3. CPop (dépiler)
4. DPeek (consulter)

Que contient chaque nœud d'une liste doublement chaînée ?

1. ADes données, un pointeur vers le nœud suivant et un pointeur vers le nœud précédent
2. BDes données et deux pointeurs, l'un vers le nœud suivant et l'autre vers le nœud d'après
3. CDes données et uniquement un pointeur vers le nœud suivant
4. DDeux copies des données et un pointeur

Comment les éléments d'un tableau sont-ils stockés en mémoire ?

1. ADans un arbre de pages mémoire
2. BÀ des emplacements aléatoires choisis par un hachage
3. CDans un seul bloc contigu, les uns à la suite des autres
4. DDe façon dispersée, reliés par des pointeurs

Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :

1. AToujours l'ordre décroissant
2. BL'ordre par niveaux
3. CL'ordre d'insertion
4. DL'ordre croissant

Quelle structure de données un programme en cours d'exécution utilise-t-il pour suivre les appels de fonction actifs et leurs variables locales ?

1. AUne table de hachage des fonctions
2. BLa file de la mémoire du tas
3. CUn arbre binaire de recherche de cadres
4. DLa pile d'appels

Dans un tas binaire stocké dans un tableau commençant à l'indice 0, où se trouve le parent du nœud d'indice i ?

1. AÀ l'indice 2i + 1
2. BÀ l'indice ⌊(i − 1) / 2⌋
3. CÀ l'indice ⌊i / 2⌋ + 1
4. DÀ l'indice i − 1

La suppression d'un nœud ayant deux enfants dans un arbre binaire de recherche se fait généralement en :

1. AL'échangeant avec la racine
2. BSupprimant tout le sous-arbre
3. CReconstruisant de zéro le sous-arbre situé en dessous et en réinsérant toutes les clés qu'il contenait
4. DLe remplaçant par son successeur infixe (ou prédécesseur) puis en supprimant ce nœud

La complexité temporelle de decrease-key dans un tas binaire (la position de l'élément étant connue) est :

1. AO(n)
2. BO(log n)
3. CO(1)
4. DO(n log n)