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

Que fait l'opération peek (ou top) sur une pile ?

1. AElle retire l'élément du sommet et le renvoie
2. BElle retire tous les éléments de la pile
3. CElle renvoie l'élément du fond de la pile
4. DElle renvoie l'élément du sommet sans le retirer

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

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

Quelle est la caractéristique essentielle d'un ensemble en tant que type abstrait de données ?

1. AIl stocke des paires clé–valeur
2. BIl stocke des éléments sans doublons
3. CIl stocke des éléments dans l'ordre trié
4. DIl ne permet l'accès qu'à une seule extrémité

Une file est implémentée avec deux piles : on empile sur une pile « in » et on dépile depuis une pile « out », remplie à partir de « in » lorsqu'elle est vide. Quel est le coût amorti par opération ?

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

Combien de temps prend la recherche d'un mot de longueur L dans un trie à alphabet fixe ?

1. AO(L), quel que soit le nombre de mots stockés
2. BO(L × n)
3. CO(n), où n est le nombre de mots
4. DO(log n), où n est le nombre de mots

Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?

1. AUne file FIFO
2. BUne file de priorité min
3. CUne pile
4. DUn ensemble sans ordre

Quelle propriété maintient tout B-arbre parfaitement équilibré ?

1. ALes clés ne sont stockées que dans la racine
2. BToutes les feuilles sont à la même profondeur
3. CChaque nœud a exactement deux enfants
4. DChaque nœud stocke une seule clé

Dans un tampon circulaire, front == rear peut signifier vide ou plein. Quelle est une manière courante de les distinguer ?

1. ATenir un compteur d'éléments séparé, ou toujours laisser une case inutilisée
2. BStocker front et rear dans la même variable
3. CChoisir une taille de tampon égale à une puissance de deux
4. DToujours vider le tampon dès que front est égal à rear, si bien que l'état est vide