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

Combien d'arêtes possède un arbre à n nœuds ?

1. An + 1
2. B2n
3. Cn
4. Dn − 1

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

1. ATas (heap)
2. BPile (stack)
3. CArbre binaire
4. DFile (queue)

Quelle structure de données utilise-t-on pour effectuer un parcours en largeur (par niveaux) d'un arbre ?

1. AUne file de priorité
2. BUne table de hachage
3. CUne pile
4. DUne file

Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?

1. AElle est symétrique par rapport à la diagonale principale
2. BChaque ligne contient exactement un 1
3. CElle est toujours triangulaire supérieure
4. DSa diagonale principale contient toujours des 1

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 existantes sont triées sur place
2. BSeules les clés en collision sont déplacées dans une nouvelle liste de débordement à la fin de la table
3. CUne table plus grande est allouée et chaque clé y est réinsérée
4. DLes clés les plus anciennes sont supprimées pour faire de la place

Un trie (arbre de préfixes) est particulièrement efficace pour :

1. ALa recherche des plus courts chemins
2. BLe tri de nombres
3. CLes recherches par préfixe, comme l'autocomplétion
4. DLe stockage de matrices

Quelle garantie les règles des arbres rouge-noir donnent-elles sur la hauteur d'un arbre à n clés ?

1. ALa hauteur est au plus 2 log₂(n + 1)
2. BLa hauteur est au plus log₂ n + 1
3. CLa hauteur vaut exactement log₂ n
4. DLa hauteur est au plus n / 2

Que fait un arbre splay (splay tree) après chaque accès ?

1. AIl reconstruit tout l'arbre sous forme équilibrée
2. BIl déplace le nœud accédé vers une feuille
3. CIl fait remonter le nœud accédé jusqu'à la racine par des rotations
4. DIl recolorie les nœuds du chemin de recherche