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

Dans un graphe, qu'est-ce qu'un cycle ?

1. AUn sommet sans arête
2. BUn chemin qui commence et se termine au même sommet
3. CUn chemin qui passe par tous les sommets
4. DUne arête de poids nul

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

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

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

1. APile (stack)
2. BArbre binaire
3. CTas (heap)
4. DFile (queue)

Les arbres AVL et les arbres rouge-noir garantissent :

1. AQue les clés sont stockées dans l'ordre d'insertion
2. BQu'aucun nœud n'a deux enfants
3. CUne recherche en temps constant dans tous les cas
4. DUne hauteur en O(log n) grâce au rééquilibrage

Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?

1. AO(V²)
2. BO(E²)
3. CO(V + E)
4. DO(V × E)

Un filtre de Bloom peut répondre à la question « cet élément appartient-il à l'ensemble ? » avec :

1. ADes faux négatifs possibles mais aucun faux positif
2. BDes réponses toujours exactes
3. CDes faux positifs possibles mais aucun faux négatif
4. DDes réponses uniquement pour des nombres

Quelle propriété un arbre rouge-noir doit-il respecter ?

1. ATout nœud rouge doit avoir des enfants rouges, si bien que les nœuds rouges forment toujours des chaînes ininterrompues jusqu'aux feuilles
2. BTout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
3. CChaque nœud doit être rouge
4. DLa racine doit être rouge