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

Quelle structure de données fonctionne selon le principe « premier entré, premier sorti » (FIFO) ?

1. ATas (heap)
2. BArbre binaire
3. CPile (stack)
4. DFile (queue)

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. BDe façon dispersée, reliés par des pointeurs
3. CDans un arbre de pages mémoire
4. DDans un seul bloc contigu, les uns à la suite des autres

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

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

Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?

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

Que se passe-t-il lorsqu'une table de hachage est rehachée après que son facteur de charge a dépassé un seuil ?

1. ALes clés les plus anciennes sont supprimées pour faire de la place
2. BLes clés existantes sont triées sur place
3. CUne table plus grande est allouée et chaque clé y est réinsérée
4. DSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table

Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?

1. A2^h+1 − 1
2. B2^h
3. Ch²
4. D2h + 1

Un arbre de Fenwick (binary indexed tree) sur un tableau de n nombres permet quelles opérations en O(log n) ?

1. ALa recherche de la médiane en O(1)
2. BL'insertion d'éléments à n'importe quelle position
3. CLes requêtes de sommes préfixes et les mises à jour d'un seul élément
4. DLe tri du tableau et la recherche dichotomique

Quelle paire de parcours détermine toujours un arbre binaire unique à clés distinctes ?

1. APar niveaux seul
2. BPréfixe et postfixe
3. CPréfixe seul
4. DPréfixe et infixe